A sequência binária quadrada-diagonal é construída da seguinte maneira:
- 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, ...
Converta cada número em binário:
1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, ...
Concatene-os:
11011100101110111100010011010101111001101111011111000010001 ...
Começando por
n=1
, gere quadrados com o comprimento lateral crescente,n
que 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
...
Pegue a diagonal (canto superior esquerdo para canto inferior direito) de cada quadrado:
1, 11, 100, 1011, 00111, ...
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 primeirosi
elementos da sequência. - Com a entrada
i
, retorne ou imprima oi
elemento th da sequência (0 ou 1 indexado).
Indique na sua resposta qual formato de saída você escolhe.
Este é o código-golfe , 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
3m
comn
?°
mas muito mais rápidos: PCasca , 15 bytes
Isso leva uma abordagem um pouco diferente à resposta de Martin
Experimente online!
Explicação:
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...]
fonte
Java (OpenJDK 8) ,
215212206202197 bytesExperimente online!
fonte
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);}
( 197 bytes )Python 2 , 91 bytes
Experimente online!
imprime a sequência infinitamente
fonte
Gelatina , 16 bytes
Experimente online!
Explicação
fonte
Mathematica, 96 bytes
Produz o
i
elemento th da sequência (indexado 1)Experimente online!
fonte
Perl 5 , 92 + 1 (
-p
) = 93 bytesExperimente online!
fonte
Gelatina , 18 bytes
Abordagem completamente diferente em comparação com a solução da Erik .
Experimente online!
Como funciona
Guardado 1 byte graças a Jonathan Allan !
fonte
³
:Ḷ²S‘ɓ*3B€Fṫ
Gelatina , 22 bytes
Experimente online!
fonte
Pitão ,
2720 bytesVerifique os primeiros casos de teste.
Obtém o i- ésimo termo da sequência, 1 indexado.
Como funciona?
fonte