A seqüência diagonal do quadrado binário

20

A sequência binária quadrada-diagonal é construída da seguinte maneira:

  1. Tome a sequência de números naturais positivos:
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...
  2. Converta cada número em binário:

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

  3. Concatene-os:

    11011100101110111100010011010101111001101111011111000010001 ...

  4. Começando por n=1, gere quadrados com o comprimento lateral crescente, nque são preenchidos da esquerda para a direita, de cima para baixo com os elementos da sequência acima:

    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. Pegue a diagonal (canto superior esquerdo para canto inferior direito) de cada quadrado:

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

  6. Converta em decimal (ignorando zeros à esquerda):

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

Tarefa

Escreva um programa ou função que produza a sequência de uma das seguintes maneiras:

  • Retorne ou imprima a sequência infinitamente.
  • Com a entrada i, retorne ou imprima os primeiros ielementos da sequência.
  • Com a entrada i, retorne ou imprima o ielemento th da sequência (0 ou 1 indexado).

Indique na sua resposta qual formato de saída você escolhe.

Este é o , a resposta mais curta em cada idioma vence.

Casos de teste

Aqui estão os 50 primeiros elementos da sequência:

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
fonte

Respostas:

10

Casca , 15 14 bytes

zȯḋm←CtNCİ□ṁḋN

Experimente online!

Imprime continuamente os resultados como uma lista infinita.

Explicação

Gostaria de saber se existe uma maneira melhor de obter cada n- ésimo elemento de uma lista do que dividir a lista em partes de comprimento n e recuperar a cabeça de cada parte.

      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 ficar claro, extraímos a diagonal de um quadrado nxn dividindo sua forma linear em pedaços de comprimento n + 1 e recuperando o primeiro elemento de cada pedaço:

[[1 , 0 , 1 , 0
  0],[1 , 0 , 1
  1 , 0],[1 , 0
  0 , 1 , 0],[1]]
Martin Ender
fonte
5

Python 2 , 137 85 bytes

lambda n:int(''.join(bin(x+1)[2:]for x in range(n**3))[n*~-n*(2*n-1)/6:][:n*n:n+1],2)

Experimente online!

Felipe Nardi Batista
fonte
4

05AB1E , 19 17 16 bytes

°LbJsLn£θs>ô€нJC

°é substituído por 3mnos links, pois °tende a ficar muito lento.

Experimente online! ou como um conjunto de testes

Explicação

°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
fonte
Você não pode substituir 3mcom n?
Erik the Outgolfer
@EriktheOutgolfer: Sim, eu posso, obrigado! Eu tinha certeza de que não funcionou, mas isso pode ter sido causado por distorções em uma solução anterior. Contagem de bytes iguais, °mas muito mais rápidos: P
Emigna 16/10
Os números de 1 à entrada ^ 2 não são suficientes . 1 para inserir ^ 3 como nas respostas python parece ser suficiente.
ovs 16/10
@ovs: Ah sim, é por isso que não o usei anteriormente. Só verifiquei os dois primeiros itens dessa vez. Eu vou reverter para a solução anterior (felizmente, ao mesmo contagem de bytes)
Emigna
3

Casca , 15 bytes

Isso leva uma abordagem um pouco diferente à resposta de Martin

moḋz!NCNCṘNNṁḋN

Experimente online!

Explicação:

              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

Em ação

ṁḋ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
fonte
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);}

Experimente online!

Roberto Graham
fonte
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

Experimente online!

imprime a sequência infinitamente

ovs
fonte
2

Gelatina , 16 bytes

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

Experimente online!

Explicação

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
milhas
fonte
1

Mathematica, 96 bytes

Produz o ielemento th da sequência (indexado 1)

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


Experimente online!

J42161217
fonte
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..$_

Experimente online!

Xcali
fonte
1

Gelatina , 18 bytes

Abordagem completamente diferente em comparação com a solução da Erik .

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

Experimente online!

Como funciona

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

Range - Faixa reduzida, gera [0, N).
 ² - Quadrado vetorizado (quadrado cada).
  S - soma.
   '- Incremento, para contabilizar a indexação 1 do Jelly.
     ɓ - Inicia uma cadeia diádica separada.
     * 3 - A entrada para a potência de 3.
       B € - Converta cada um em binário.
         F - Achatar.
          Tail - Cauda. Retorne x [y - 1:] (indexado 1).

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

Ç - Último link como mônada.
 m '- Entrada modular + 1. Obtenha cada elemento "entrada + 1" da lista.
   Head - Cabeça. Retorne o acima com elementos em índice superior ao da entrada cortada.
    µḄ - Converte de binário para inteiro.

Guardado 1 byte graças a Jonathan Allan !

Mr. Xcoder
fonte
Salve um usando uma corrente diádica para remover o ³:Ḷ²S‘ɓ*3B€Fṫ
Jonathan Allan
@ JonathanAllan Claro, obrigado! Eu realmente deve aprender esse truque
Mr. Xcoder
0

Gelatina , 22 bytes

²Rµ²Ṭ€Ẏ0;œṗBẎ$³ịs³ŒDḢḄ

Experimente online!

Erik, o Outgolfer
fonte
0

Pitão ,  27  20 bytes

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

Verifique os primeiros casos de teste.

Obtém o i- ésimo termo da sequência, 1 indexado.

Como 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.
Mr. Xcoder
fonte