Pares sin usar

21

Definamos una secuencia de enteros positivos. Definiremos la secuencia en números pares para que sea el doble del término anterior. Los índices impares de la secuencia serán el número entero positivo más pequeño que aún no aparece en la secuencia.

Aquí están los primeros dos términos.

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

También puede pensar en esto como la lista de pares concatenados (n, 2n) donde n es el entero positivo menos utilizado hasta ahora.

Tarea

Dado un número n como calcular entrada de la n º término en esta secuencia.

Este es el código de golf, por lo que debe intentar minimizar el tamaño de su código fuente medido en bytes.

OEIS A036552

code-golf sequence Asistente de trigo
fuente
El hecho de que los índices impares de la secuencia serán los enteros positivos más pequeños que aún no aparecen en la secuencia. es irrelevante, ¿verdad?
Adám
1
Además, ¿qué pares ?
Adám
@ Adám No, este no es el caso. No estoy seguro de qué te da esa impresión, tal vez lo he redactado mal.
Wheat Wizard
1
@ Adám, otra forma de pensar en la secuencia es que consiste en pares concatenados (n,2n)y cada número aparece solo una vez. Cada par se elige para ser el más pequeño posible mientras se adhiere a la última restricción.
Martin Ender
3
La valoración 2-adic de elementos impares de la serie es siempre par. Puede ser útil para alguien.
CalculatorFeline

Respuestas:

11

Haskell, 40 bytes

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

De base cero. lconstruye incrementalmente la secuencia a partir de una lista perezosa de enteros restantes.

Christian Sievers
fuente
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={})

¿Cómo?

Hacemos un seguimiento de:

  • El último valor insertado b .
  • Todos los valores encontrados anteriormente en la tabla de búsqueda a .

Internamente, estamos usando un índice basado en 0 i . Por lo tanto, los comportamientos pares e impares se invierten:

  • En posiciones impares, el siguiente valor es simplemente 2 * b.

  • En las posiciones pares, utilizamos la función recursiva g () y la tabla de búsqueda a para identificar el valor de coincidencia más pequeño:

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

Para ahorrar unos pocos bytes, i se inicializa en {}lugar de 0. Esto nos obliga a usar:

  • i^ncomparar i con n porque ({}) ^ n === nmientras se ({}) - nevalúa a NaN.
  • -~ipara incrementar i , porque ({}) + 1generaría una cadena.

Manifestación

Mostrar fragmento de código

Arnauld
fuente
60 bytes
Shaggy
5

Python 3 , 80 72 69 bytes

-7 bytes gracias al Sr. Xcoder !

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

Pruébalo en línea!

notjagan
fuente
1
Puede reparar set(...)con `{* ...} para 78 bytes
Mr. Xcoder
@ Zacharý ¿Se refería a mi comentario? Si es así, un conjunto en Python 3 puede ser en {*...}lugar de set(...).
Sr. Xcoder
Estaba comentando sin pensar, me di cuenta unos momentos más tarde que {...for...in...}sería más adiós.
Zacharý
En realidad, ahorraría 4 bytes, porque lo usa dos veces
Mr. Xcoder
69 bytes. (y no sirve Truepara 1)
Wheat Wizard
3

Matemáticas , 56 53 bytes

-3 bytes gracias JungHwan Min !

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

Pruébalo en línea!

Basado en la expresión de Mathematica dada en el enlace OEIS.

notjagan
fuente
1
También 53 bytes:Nest[k=0;If[#~FreeQ~++k,#~Join~{k,2k},#]&,{},#][[#]]&
JungHwan Min
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;

Pruébalo en línea

Tito
fuente
3

05AB1E , 16 15 14 bytes

1 indexado.
Utiliza el hecho de que la representación binaria de elementos en índices impares en la secuencia termina en un número par de ceros: A003159 .

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

Pruébalo en línea!

Explicación

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
fuente
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)

Pruébalo en línea!

Fondo

Cada entero n positivo puede expresarse únicamente como n = 2 o (n) c (n) , donde c (n) es impar.

Deje ⟨a n ⟩ n> 0 ser la secuencia de la especificación desafío.

Afirmamos que, para todos los enteros positivos , n , o (a 2n-1 ) es par. Como o (a 2n ) = o (2a 2n-1 ) = o (a 2n-1 ) + 1 , esto es equivalente a afirmar que o (a 2n ) siempre es impar.

Suponga que la afirmación es falsa y deje que 2m-1 sea ​​el primer índice impar de la secuencia de manera que o (a 2m-1 ) sea ​​impar. Tenga en cuenta que esto hace que 2m sea ​​el primer índice par de la secuencia de manera que o (a 2m-1 ) sea ​​par.

o (a 2m-1 ) es impar y 0 es par, por lo que un 2m-1 es divisible por 2 . Por definición, un 2m-1 es el número entero positivo más pequeño que aún no aparece en la secuencia , lo que significa que un 2m-1 /2 debe haber aparecido antes. Deje k ser el (primer) índice de un 2m-1 /2 en a .

Como o (a k ) = o (a 2m-1 /2) = o (a 2m-1 ) - 1 es par, la minimidad de n implica que k es impar. A su vez, esto significa que a k + 1 = 2a k = a 2m-1 , contradiciendo la definición de a 2m-1 .

Cómo funciona

está por venir

Dennis
fuente
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]}

Pruébalo en línea!

Una función anónima que toma un argumento. FEl valor predeterminado es FALSEo 0para que el algoritmo evalúe correctamente que todavía no hay enteros positivos en la secuencia.

El algoritmo genera los pares en un forbucle de la siguiente manera (en el que iva desde 2a 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
fuente
2

Haskell , 63 bytes

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

Pruébalo en línea!

Éste abusa de la evaluación perezosa de Haskell en toda su extensión.

Asistente de trigo
fuente
2

Perl 6 , 50 bytes

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

Pruébalo en línea!

  • 1, { ... } ... *es una secuencia infinita generada perezosamente donde cada término después del primero es proporcionado por el bloque de código delimitado por llaves. Como el bloque hace referencia a la @_matriz, recibe toda la secuencia actual en esa matriz.
  • Si el número actual de elementos es impar (@_ % 2 ), estamos generando un elemento aún indexada, por lo que el siguiente elemento es el doble del último elemento que tenemos hasta ahora: 2 * @_[*-1].
  • De lo contrario, obtenemos el primer entero positivo que aún no aparece en la secuencia: first * ∉ @_, 1..* .
  • $_es el argumento de la función externa. Se indexa en la secuencia infinita, dando el valor de retorno de la función.
Sean
fuente
1

Mathematica, 82 bytes

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

Pruébalo en línea!

J42161217
fuente
58 bytes en Mathematica (aunque probablemente debería publicar una respuesta por separado ya que la idea es bastante diferente).
notjagan
¿Copiaste eso del enlace OEIS?
J42161217
Lo modifiqué para ajustarse a la tarea y jugar más al golf, pero más o menos es lo mismo que el enlace OEIS.
notjagan
1
@no publique una nueva respuesta si lo desea y acredite al autor
J42161217
1

k , 27 bytes

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

1 indexado. Pruébalo en línea!

Usando en (!y)^xlugar de &^x?!yobras también.

zgrep
fuente
1

C # (compilador interactivo de 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;}

Pruébalo en línea!

-6 bytes gracias a @ASCIIOnly!

dana
fuente
C # 8 puede ser demasiado nuevo para ser común en los intérpretes en línea por ahora, sumado al hecho de que csi es algo Mono, por lo que tendría que esperar a que Mono lo implemente y lo agregue a una compilación estable (si no lo ha hecho) t ya)
solo ASCII
lamentablemente no es fácil verificar esto en C #
solo ASCII
Use esto para comenzar? Pero sí, no parece algo sencillo. docs.microsoft.com/en-us/dotnet/api/…
dana
1
86? - No creo que :se necesiten los s, ya que será el número más grande en la lista
Solo ASCII
También 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))))%)

Itera los ntiempos para construir la secuencia y devuelve el nelemento th, indexado 1.

NikoNyrh
fuente
0

Rubí, 60 bytes.

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

0 indexado. Hacemos un bucle de n/2+1tiempos, generando dos valores cada vez y almacenándolos al completar una matriz en sus índices. v+v*n%2da la salida, ya sea vo v*2dependiendo de la paridad de n.

histocrat
fuente
0

Ruby , 49 bytes

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

Comience con [0], agregue pares a la matriz hasta que tengamos al menos n + 1 elementos, luego tome el n + 1 (basado en 1)

Pruébalo en línea!

GB
fuente
0

JavaScript (ES6), 60 65 bytes

Una solución iterativa.

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

Menos golf

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;  
}

Prueba

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 fragmento

edc65
fuente
0

Jalea , 13 12 10 bytes

ḤRọ2ḂĠZFị@

Esto usa la observación de mi respuesta de Python .

Pruébalo en línea!

Cómo 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
fuente