La secuencia diagonal cuadrada binaria

20

La secuencia diagonal cuadrada binaria se construye de la siguiente manera:

  1. Tome la secuencia de números naturales positivos:
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...
  2. Convierta cada número a binario:

    1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, ...

  3. Concatenarlos:

    11011100101110111100010011010101111001101111011111000010001 ...

  4. Comenzando con n=1, genere cuadrados con una longitud lateral creciente nque se llenen de izquierda a derecha, de arriba a abajo con los elementos de la secuencia anterior:

    1
    1 0
    1 1
    1 0 0 
    1 0 1
    1 1 0
    1 1 1 1
    0 0 0 1
    0 0 1 1 
    0 1 0 1
    0 1 1 1 1
    0 0 1 1 0
    1 1 1 1 0
    1 1 1 1 1
    0 0 0 0 1
    ...

  5. Tome la diagonal (superior izquierda a inferior derecha) de cada cuadrado:

    1, 11, 100, 1011, 00111, ...

  6. Convierte a decimal (ignorando los ceros iniciales):

    1, 3, 4, 11, 7, ...

Tarea

Escriba un programa o función que genere la secuencia de una de las siguientes maneras:

  • Devuelve o imprime la secuencia infinitamente.
  • Dada la entrada i, devuelve o imprime los primeros ielementos de la secuencia.
  • Dada la entrada i, devuelve o imprime el ielemento th de la secuencia (0 o 1 indexado).

Indique en su respuesta qué formato de salida elige.

Este es el , gana la respuesta más corta en cada idioma.

Casos de prueba

Aquí están los primeros 50 elementos de la secuencia:

1,3,4,11,7,29,56,141,343,853,321,3558,8176,3401,21845,17129,55518,134717,151988,998642,1478099,391518,7798320,8530050,21809025,61485963,66846232,54326455,221064493,256373253,547755170,4294967295,1875876391,2618012644,24710258456,6922045286,132952028155,217801183183,476428761596,51990767390,687373028085,1216614609441,7677215985062,15384530216172,22714614479340,15976997237789,0,256145539974868,532024704777005,601357273478135
Laikoni
fuente

Respuestas:

10

Casco , 15 14 bytes

zȯḋm←CtNCİ□ṁḋN

Pruébalo en línea!

Imprime continuamente los resultados como una lista infinita.

Explicación

Me pregunto si hay una mejor manera de conseguir cada n -ésimo elemento de una lista de dividir la lista en trozos de longitud n y recuperar la cabeza de cada trozo.

      tN          Get a list of all natural numbers except 1. (A)

             N    Get a list of all natural numbers.
           ṁḋ     Convert each to its binary representation and join them 
                  all into a single list.
         İ□       Get a list of squares of all natural numbers.
        C         Cut the list of bits into chunks of corresponding sizes. (B)

zȯ                Zip (A) and (B) together with the following function.
     C            Split the bit list (from B) into chunks of the given length
                  (from A).
   m←             Get the head of each chunk. This is the diagonal of the
                  bit list arranged as a square.
  ḋ               Interpret the resulting bits as binary digits and return
                  the result.

Para ser claros, extraemos la diagonal de un cuadrado nxn dividiendo su forma lineal en trozos de longitud n + 1 y recuperando el primer elemento de cada fragmento:

[[1 , 0 , 1 , 0
  0],[1 , 0 , 1
  1 , 0],[1 , 0
  0 , 1 , 0],[1]]
Martin Ender
fuente
4

05AB1E , 19 17 16 bytes

°LbJsLn£θs>ô€нJC

°se reemplaza por 3men los enlaces, ya que °tiende a ser muy lento.

Pruébalo en línea! o como un conjunto de pruebas

Explicación

°L                 # push the range [1 ... 10^input]
  bJ               # convert each to binary and join to string
    sLn            # push the range [1 ... input]^2
       £θ          # split the binary string into pieces of these sizes and take the last
         s>ô       # split this string into chunks of size (input+1)
            €н     # get the first digit in each chunk
              JC   # join to string and convert to int
Emigna
fuente
¿No puedes reemplazar 3mcon n?
Erik the Outgolfer
@EriktheOutgolfer: Sí, gracias. Estaba bastante seguro de que no funcionó, pero eso puede deberse a problemas en una solución anterior. El mismo número de bytes °pero mucho más rápido: P
Emigna
Los números del 1 al ingreso ^ 2 no son suficientes . 1 para ingresar ^ 3 como en las respuestas de Python parece ser suficiente.
ovs
@ovs: Ah, sí, por eso no lo usé anteriormente. Esta vez solo revisé los primeros dos elementos. Volveré a la solución anterior (afortunadamente en el mismo recuento de bytes)
Emigna
3

Casco , 15 bytes

Esto toma un enfoque algo diferente a la respuesta de Martin

moḋz!NCNCṘNNṁḋN

Pruébalo en línea!

Explicación:

              N   List of all natural numbers
            ṁḋ    Convert each to it's binary representation and flatten
         ṘNN      Repeat the list of natural numbers according the natural numbers:
                  [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5...]
        C         Cut the list of bits into lists of lengths corresponding to the above
      CN          Cut that list into lists of lengths corresponding to the natural numbers
moḋz!N            For each in the list, get the diagonals and convert from binary.
m                   For each list in the list
   z!N              Zip it with natural numbers, indexing.
 oḋ                 Convert to binary

En acción

ṁḋN : [1,1,0,1,1,1,0,0,1,0,1,1,1,0,1,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1...]

ṘNN : [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8...]

C : [[1],[1,0],[1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1,1],[0,0,0,1]...]

CN : [[[1]],[[1,0],[1,1]],[[1,0,0],[1,0,1],[1,1,0]]...]

m z!N : [[1],[1,1],[1,0,0],[1,0,1,1],[0,0,1,1,1],[0,1,1,1,0,1]...]

oḋ : [1,3,4,11,7,29,56,141,343,853,321,3558,8176,3401,21845...]

H.PWiz
fuente
3

Java (OpenJDK 8) , 215 212 206 202 197 bytes

i->{String b="",t;int s=0,x=++i,j;for(;--x>0;s+=x*x);while(b.length()<s)b+=i.toString(++x,2);for(j=1,s=0;j<i;System.out.println(i.valueOf(t,2)),s+=j*j++)for(t="",x=s;x<s+j*j;x+=j+1)t+=b.charAt(x);}

Pruébalo en línea!

Roberto Graham
fuente
2

Python 2 , 91 bytes

i=n=1;s=''
while 1:
 s+=bin(i)[2:];i+=1
 if s[n*n:]:print int(s[:n*n:n+1],2);s=s[n*n:];n+=1

Pruébalo en línea!

imprime la secuencia infinitamente

ovs
fuente
2

Jalea , 16 bytes

RBFṁ
R²SÇṫ²C$m‘Ḅ

Pruébalo en línea!

Explicación

RBFṁ  Helper link. Input: integer k
R     Range, [1, 2, ..., k]
 B    Convert each to a list of its binary digits
  F   Flatten
   ṁ  Mold to length k

R²SÇṫ²C$m‘Ḅ  Main link. Input: integer n
R            Range, [1, 2, ..., n]
 ²           Square each
  S          Sum
   Ç         Call helper link on the sum of the first n squares
       $     Monadic chain
     ²         Square n
      C        Complement, 1-n^2
    ṫ        Tail, take the last n^2 elements
        m    Modular indexing, take each
         ‘   (n+1)th element
          Ḅ  Convert from list of binary digits to decimal
millas
fuente
1

Mathematica, 96 bytes

Emite el ielemento th de la secuencia (1 indexado)

Diagonal@Partition[TakeList[Flatten@IntegerDigits[Range[#^3],2],Range@#^2][[#]],#]~FromDigits~2&


Pruébalo en línea!

J42161217
fuente
1

Perl 5 , 92 + 1 ( -p) = 93 bytes

$s.=sprintf'%b',++$"for 1..$_**3;map{say oct"0b".(substr$s,0,$_*$_,'')=~s/.\K.{$_}//gr}1..$_

Pruébalo en línea!

Xcali
fuente
1

Jalea , 18 bytes

Enfoque completamente diferente en comparación con la solución de Erik .

Ḷ²S‘ɓ*3B€Fṫ
Çm‘ḣµḄ

Pruébalo en línea!

Cómo funciona

Ḷ²S'ɓ * 3B € Fṫ - Enlace auxiliar (monádico).

Ḷ - Rango reducido, genera [0, N).
 ² - Cuadrado vectorizado (cuadrado cada uno).
  S - Suma.
   '- Incremento, para tener en cuenta la indexación 1 de Jelly.
     ɓ - Inicia una cadena diádica separada.
     * 3 - La entrada a la potencia de 3.
       B € - Convierte cada uno a binario.
         F - Acoplar.
          ṫ - Cola. Devuelve x [y - 1:] (1 indexado).

Çm'ḣµḄ - Enlace principal (monádico).

Ç - Último enlace como mónada.
 m '- Entrada modular + 1. Obtenga cada elemento "entrada + 1" de la lista.
   ḣ - Cabeza. Devuelva lo anterior con elementos en un índice más alto que la entrada recortada.
    µḄ - Convertir de binario a entero.

¡Salvado 1 byte gracias a Jonathan Allan !

Sr. Xcoder
fuente
Ahorre uno usando una cadena diádica para eliminar el ³:Ḷ²S‘ɓ*3B€Fṫ
Jonathan Allan
@ JonathanAllan Por supuesto, ¡gracias! Realmente debería aprender ese truco
Sr. Xcoder
0

Pyth ,  27  20 bytes

i<%hQ>s.BS^Q3s^R2QQ2

Verifique los primeros casos de prueba.

Obtiene el I ésimo término de la sucesión, 1 indexado.

¿Cómo funciona?

i<%hQ>s.BS^Q3s^R2QQ2   - Full program. Q represents the input.

         S^Q3          - Generate the (inclusive) range [1, Q ^ 3].
       .B              - Convert each to binary.
      s                - Join into a single string.
     >                 - Trim all the elements at indexes smaller than:
               ^R2Q      - The elements of the range [0, Q) squared.
              s          - And summed.
  %hQ                  - Get each Q + 1 element of the list above.
 <                     - Trim all the elements at indexes higher than:
                   Q   - The input.
i                   2  - Convert from binary to integer.
Sr. Xcoder
fuente