Pares ainda não utilizados

21

Vamos definir uma sequência de números inteiros positivos. Definiremos a sequência em números pares para ser o dobro do termo anterior. Os índices ímpares da sequência serão o menor número inteiro positivo ainda não aparecendo na sequência.

Aqui estão os dois primeiros termos.

1,2,3,6,4,8,5,10,7,14,9,18,11,22,12,24,13,26,15,30

Você também pode pensar nisso como a lista de pares concatenados (n, 2n) em que n é o número inteiro positivo menos usado até o momento.

Tarefa

Dado um número n como calcular entrada o n ésimo termo nesta sequência.

Isso é código-golfe, então você deve tentar minimizar o tamanho do seu código-fonte medido em bytes.

OEIS A036552

code-golf sequence Assistente de Trigo
fonte
O fato de que Os índices ímpares da sequência será o menor número inteiro positivo ainda não aparecendo na sequência. é irrelevante, certo?
Adám
1
Além disso, quais pares ?
Adám
@ Adám Não, este não é o caso. Não sei ao certo o que lhe dá essa impressão, talvez eu tenha falado mal sobre isso.
Assistente de trigo
1
@ Adám outra maneira de pensar na sequência é que ela consiste em pares concatenados (n,2n)e cada número aparece apenas uma vez. Cada par é escolhido para ser o menor possível enquanto adere à última restrição.
Martin Ender
3
A avaliação 2-adic de elementos ímpares da série é sempre par. Pode ser útil para alguém.
CalculatorFeline

Respostas:

11

Haskell, 40 bytes

l(a:r)=a:2*a:l[x|x<-r,x/=2*a]
(l[1..]!!)

Baseado em zero. lincrementalmente cria a sequência a partir de uma lista lenta de números inteiros restantes.

Peneiradores cristãos
fonte
7

JavaScript (ES6), 92 82 69 67 65 bytes

n=>(F=i=>i^n?F(a[b=i&1?2*b:(g=k=>a[k]?g(k+1):k)(1)]=-~i):b)(a={})

Quão?

Nós acompanhamos:

  • O último valor inserido b .
  • Todos os valores encontrados anteriormente na tabela de pesquisa a .

Internamente, estamos usando um índice baseado em 0 i . Portanto, comportamentos ímpares e pares são invertidos:

  • Em posições ímpares, o próximo valor é simplesmente 2 * b.

  • Em posições pares, usamos a função recursiva g () e a tabela de pesquisa a para identificar o menor valor correspondente:

    (g = k => a[k] ? g(k + 1) : k)(1)

Para salvar alguns bytes, i é inicializado em {}vez de 0. Isso nos obriga a usar:

  • i^ncomparar i com n porque ({}) ^ n === nConsiderando que ({}) - navalia para NaN.
  • -~iincrementar i , porque ({}) + 1geraria uma string.

Demo

Mostrar snippet de código

Arnauld
fonte
60 bytes
Shaggy
5

Python 3 , 80 72 69 bytes

-7 bytes graças ao Sr. Xcoder !

f=lambda n:n and[f(n-1)*2,min({*range(n+1)}-{*map(f,range(n))})][n%2]

Experimente online!

notjagan
fonte
1
Você pode substituir set(...)com `{* ...} por 78 bytes
Mr. Xcoder
@ Zacharý Você estava se referindo ao meu comentário? Nesse caso, um conjunto no Python 3 pode ser em {*...}vez de set(...).
Mr. Xcoder
Eu estava comentando sem pensar, percebi alguns momentos depois que {...for...in...}haveria mais adeus.
Zacharý
Na verdade, ele iria salvar 4 bytes, porque você usá-lo duas vezes
Mr. Xcoder
69 bytes. (e ele não usa Truepara 1)
Assistente de trigo
3

Matemática , 56 53 bytes

-3 bytes obrigado JungHwan Min !

(w={};Do[w~FreeQ~k&&(w=w~Join~{k,2k}),{k,#}];w[[#]])&

Experimente online!

Com base na expressão do Mathematica fornecida no link OEIS.

notjagan
fonte
1
Também 53 bytes:Nest[k=0;If[#~FreeQ~++k,#~Join~{k,2k},#]&,{},#][[#]]&
JungHwan Min
3

PHP , 64 bytes

for(;$argn-$i++;)if($i&$$e=1)for(;${$e=++$n};);else$e*=2;echo$e;

Experimente online!

PHP , 77 bytes

for(;$argn-$i++;$r[]=$e)if($i&1)for(;in_array($e=++$n,$r););else$e*=2;echo$e;

Experimente online!

PHP , 78 bytes

for(;$argn-$i++;)$e=$r[]=$i&1?end(array_diff(range($i,1),$r?:[])):2*$e;echo$e;

Experimente online!

Jörg Hülsermann
fonte
3

PHP, 56 bytes

while($$n=$i++<$argn)for($n*=2;$i&$$k&&$n=++$k;);echo$n;

PHP, 75 72 bytes

for($a=range(1,$argn);$i++<$argn;)$a[~-$n=$i&1?min($a):2*$n]=INF;echo$n;

Experimente online

Titus
fonte
3

05AB1E , 16 15 14 bytes

1 indexado.
Usa o fato de que a representação binária de elementos em índices ímpares na sequência termina em um número par de zeros: A003159 .

Lʒb1¡`gÈ}€x¹<è

Experimente online!

Explicação

L                 # range [1 ... input]
 ʒ      }         # filter, keep only elements whose
  b               # ... binary representation
   1¡             # ... split at 1's
     `gÈ          # ... ends in an even length run
         €x       # push a doubled copy of each element in place
           ¹<è    # get the element at index (input-1)
Emigna
fonte
3

Python 2 , 59 51 49 bytes

f=lambda n,k=2:2/n%-3*(1-k)or f(n+~(k&-k)%-3,k+1)

Experimente online!

fundo

Todo n positivo positivo pode ser expresso exclusivamente como n = 2 o (n) c (n) , onde c (n) é ímpar.

Vamos ⟨a n ⟩ n> 0 é a sequência desde a especificação desafio.

Afirmamos que, para todos os números inteiros positivos n , o (a 2n-1 ) é par. Como o (a 2n ) = o (2a 2n-1 ) = o (a 2n-1 ) + 1 , isso equivale a afirmar que o (a 2n ) é sempre ímpar.

Suponha que a afirmação seja falsa e seja 2m-1 o primeiro índice ímpar da sequência, de modo que o (a 2m-1 ) seja ímpar. Observe que isso faz com que 2m seja o primeiro índice par da sequência, de modo que o (a 2m-1 ) seja par.

O (um 2m-1 ) é ímpar e 0 é ainda, de modo a 2m-1 é divisível por 2 . Por definição, um 2m-1 é o menor número inteiro positivo ainda não aparecendo na sequência , o que significa que um 2m-1 /2 deve ter aparecido antes. Seja k o (primeiro) índice de a 2m-1 /2 em a .

Como o (a k ) = o (a 2m-1 /2) = o (a 2m-1 ) - 1 é par, a minimalidade de n implica que k é ímpar. Por sua vez, isto significa que um k + 1 = 2- k = um 2m-1 , em contradição com a definição de um 2m-1 .

Como funciona

ainda está por vir

Dennis
fonte
3

R , 70 69 65 bytes

function(n){for(i in 2*1:n)F[i-1:0]=which(!1:n%in%F)[1]*1:2
F[n]}

Experimente online!

Uma função anônima que recebe um argumento. Fassume como padrão FALSEou 0para que o algoritmo avalie corretamente que nenhum número inteiro positivo ainda está na sequência.

O algoritmo gera os pares em um forloop da seguinte maneira (de onde ipassa de 2para 2npor 2):

           which(!1:n%in%l)[1]     # the missing value
                              *1:2 # keep one copy the same and double the next
l[i-1:0]=                         # store into l at the indices i-1 and i
Giuseppe
fonte
2

Haskell , 63 bytes

g x=[2*g(x-1),[a|a<-[1..],a`notElem`map g[1..x-1]]!!0]!!mod x 2

Experimente online!

Este abuso da avaliação preguiçosa de Haskell ao máximo.

Assistente de Trigo
fonte
2

Perl 6 , 50 bytes

{(1,{@_%2??2*@_[*-1]!!first *∉@_,1..*}...*)[$_]}

Experimente online!

  • 1, { ... } ... *é uma sequência infinita gerada preguiçosamente em que cada termo após o primeiro é fornecido pelo bloco de códigos delimitado por colchetes. Como o bloco faz referência à @_matriz, ele recebe toda a sequência atual nessa matriz.
  • Se o número atual de elementos é estranho ( @_ % 2), nós estamos gerando um elemento ainda indexado, então o próximo elemento é o dobro do último elemento que temos até agora: 2 * @_[*-1].
  • Caso contrário, ficamos com o primeiro número inteiro positivo que ainda não aparecem na sequência: first * ∉ @_, 1..*.
  • $_é o argumento para a função externa. Ele indexa na sequência infinita, fornecendo o valor de retorno da função.
Sean
fonte
1

Mathematica, 82 bytes

(s={};a=1;f=#;While[f>0,If[s~FreeQ~a,s~AppendTo~{a,2a}];a++;f--];Flatten[s][[#]])&

Experimente online!

J42161217
fonte
58 bytes no Mathematica (embora eu deva provavelmente postar uma resposta separada, já que a idéia é bem diferente).
precisa saber é
Você copiou isso do link OEIS?
J42161217
Modifiquei-o para se adequar à tarefa e jogar mais, mas mais ou menos é o mesmo que o link OEIS.
notjagan
1
@not postar uma nova resposta se você quiser e de crédito o autor
J42161217
1

k , 27 bytes

*|{x,*(&^x?!y;|2*x)2!y}/!2+

1 indexado. Experimente online!

Usando em (!y)^xvez de &^x?!yfunciona também.

zgrep
fonte
1

C # (compilador interativo do Visual C #) , 82 bytes

x=>{int y=1;for(var s="";x>2;x-=2)for(s+=2*y+":";s.Contains(++y+""););return x*y;}

Experimente online!

-6 bytes graças a @ASCIIOnly!

dana
fonte
O C # 8 pode ser novo demais para ser comum em intérpretes on-line por enquanto, adicionado ao fato de que csi é uma coisa do Mono, então você terá que esperar o Mono implementá-lo e adicioná-lo a uma compilação estável (se não tiver ' já)
somente ASCII
infelizmente não é fácil verificar isso em c #
ASCII-only
Use isso para começar? Mas sim, não parece algo direto. docs.microsoft.com/en-us/dotnet/api/…
dana
1
86? - não pense que os :são necessários, pois será o maior número da lista
somente ASCII
Também 2.0=>2f
dana
0

Clojure, 102 bytes

#(nth(loop[l[0 1 2 3]i %](if(= i 0)l(recur(conj l(*(last l)2)(nth(remove(set l)(range))0))(dec i))))%)

Repete as nvezes para criar a sequência e retorna o nitem 1, indexado em 1.

NikoNyrh
fonte
0

Ruby, 60 bytes

->n,*a{eval"v+=1while a[v];a[v]=a[2*v]=v+v*n%=2;"*(n/2+v=1)}

Indexado a 0. Fazemos loop de n/2+1tempos, gerando dois valores de cada vez e armazenando-os preenchendo uma matriz em seus índices. v+v*n%2fornece a saída, vou v*2dependendo da paridade de n.

histocrata
fonte
0

Ruby , 49 bytes

->n{*s=t=0;s|[t+=1]==s||s<<t<<t*2until s[n];s[n]}

Comece com [0], adicione pares ao array até termos pelo menos n + 1 elementos e, em seguida, pegue o n + 1º (baseado em 1)

Experimente online!

GB
fonte
0

JavaScript (ES6), 60 65 bytes

Uma solução iterativa.

n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

Menos golfe

n=>{
  s = {}; //hashtable for used values
  for(i=0; n; )
  {
    if ( ! s[++i] )
    {
      s[i*2] = 1; // remember i*2 is already used
      if (--n)
        if (--n)
          0;
        else
          result = i*2;
      else
        result = i;
    }
  }
  return result;  
}

Teste

F=
n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

for (a=1; a < 50; a++)
  console.log(a,F(a))
Expandir snippet

edc65
fonte
0

Gelatina , 13 12 10 bytes

ḤRọ2ḂĠZFị@

Isso usa a observação da minha resposta Python .

Experimente online!

Como funciona

ḤRọ2ḂĠZFị@  Main link. Argument: n

Ḥ           Unhalve; yield 2n.
 R          Range; yield [1, ... , 2n].
  ọ2        Compute the order of 2 in the factorization of each k in [1, ..., 2n].
    Ḃ       Bit; compute the parity of each order.
     G      Group the indices [1, ..., 2n] by the corresponding values.
      Z     Zip/transpose the resulting 2D array, interleaving the indices of 0
            with the indices of 1, as a list of pairs.
       F    Flatten. This yields a prefix of the sequence.
        ị@  Take the item at index n.
Dennis
fonte