Tome um número inteiro positivo n como entrada e dê saída (alguns dos) números decimais que podem ser criados usando n bits, ordenados da seguinte maneira:

Primeiro, liste todos os números que podem ser criados com apenas um 1e o restante 0na representação binária (classificada), depois todos os números que podem ser criados com dois consecutivos 1 , o restante 0, depois três consecutivos 1 e assim por diante.

Vamos ver como é isso para n = 4 :

0001  -  1
0010  -  2
0100  -  4
1000  -  8
0011  -  3
0110  -  6
1100  -  12
0111  -  7
1110  -  14
1111  -  15

Portanto, a saída para n = 4 é: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (formato de saída opcional).

Casos de teste:

n = 1
1

n = 2
1 2 3

n = 3
1, 2, 4, 3, 6, 7

n = 8
1, 2, 4, 8, 16, 32, 64, 128, 3, 6, 12, 24, 48, 96, 192, 7, 14, 28, 56, 112, 224, 15, 30, 60, 120, 240, 31, 62, 124, 248, 63, 126, 252, 127, 254, 255

n = 17
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 7, 14, 28, 56, 112, 224, 448, 896, 1792, 3584, 7168, 14336, 28672, 57344, 114688, 15, 30, 60, 120, 240, 480, 960, 1920, 3840, 7680, 15360, 30720, 61440, 122880, 31, 62, 124, 248, 496, 992, 1984, 3968, 7936, 15872, 31744, 63488, 126976, 63, 126, 252, 504, 1008, 2016, 4032, 8064, 16128, 32256, 64512, 129024, 127, 254, 508, 1016, 2032, 4064, 8128, 16256, 32512, 65024, 130048, 255, 510, 1020, 2040, 4080, 8160, 16320, 32640, 65280, 130560, 511, 1022, 2044, 4088, 8176, 16352, 32704, 65408, 130816, 1023, 2046, 4092, 8184, 16368, 32736, 65472, 130944, 2047, 4094, 8188, 16376, 32752, 65504, 131008, 4095, 8190, 16380, 32760, 65520, 131040, 8191, 16382, 32764, 65528, 131056,16383, 32766, 65532, 131064, 32767, 65534, 131068, 65535, 131070, 131071

Isso é código-golfe , então o código mais curto em cada idioma vence!

Boas explicações são altamente encorajadas , também para soluções em "idiomas regulares"!

Python , 53 bytes

f=lambda n,i=1:n*[f]and[i]+f(n-1,2*i)+i%2*f(n-1,i-~i)

Experimente online!

A função recursiva gera a lista classificada como uma pré-ordem percorrida nesta árvore (exemplo com n=4):

      1
     / \
    2   3
   /   / \
  4   6   7
 /   /   / \
8   12  14  15

1 2 4 8 3 6 12 7 14 15

As ramificações esquerdas dobram o valor, e as ramificações direitas i->i*2+1existem e existem apenas para ímpares i. Portanto, a caminhada de pré-encomenda para não-folhas é T(i)=[i]+T(i*2)+i%2*T(i*2+1).

A árvore termina em profundidade n, onde nestá a entrada. Isso é obtido decrementando na cada passo e parando quando é 0.

Uma estratégia alternativa seria terminar com valores que iexcedam 2**n, em vez de rastrear a profundidade. Eu achei que esse fosse um byte a mais:

f=lambda n,i=1:2**n/i*[f]and[i]+f(n,2*i)+i%2*f(n,i-~i)
f=lambda n,i=1:[f][i>>n:]and[i]+f(n,2*i)+i%2*f(n,i-~i)

Gelatina , 6 bytes

Ḷ2*ẆS€

Isso se qualifica para o bônus imaginário .

Experimente online!

Como funciona

Ḷ2*ẆS€  Main link. Argument: n

Ḷ       Unlength; yield [0, ..., n-1].
 2*     Yield [2**0, ..., 2**(n-1)].
   Ẇ    Sliding window; yield all subarrays of consecutive elements.
        The subarrays are sorted by length, then from left to right.
    S€  Map the sum atom over the substrings.

Mathematica, 40 bytes

Join@@Table[2^j(2^i-1),{i,#},{j,0,#-i}]&

Cada número na lista desejada é a diferença de duas potências de 2; portanto, simplesmente as geramos em ordem, usando Tablee achatando a lista. Eu acho que isso ganha o bônus imaginário de Stewie Griffin :)

Mathematica, 35 bytes

Tr/@Rest@Subsequences[2^Range@#/2]&

Uma porta do algoritmo Jelly de Dennis . Eu não sabia Subsequencesantes disso! (Também não vi que as milhas haviam postado essa resposta exata ... vá com uma votação!)

JavaScript (ES6), 59 58 55 bytes

for(q=prompt(n=1);p=q--;n-=~n)for(m=n;p--;m*=2)alert(m)

Um programa completo que recebe informações por meio de um prompt e alerta cada número em sucessão. Isso também se qualifica para o bônus imaginário .

Snippet de teste

(Nota: usa em console.logvez de alert)

for(q=prompt(n=1);p=q--;n-=~n)for(m=n;p--;m*=2)console.log(m)

JavaScript (ES6), 55 51 bytes

Retorna uma lista separada por espaços de números inteiros.

n=>(F=k=>k>>n?--j?F(k>>j|1):'':k+' '+F(k*2))(1,j=n)

Bônus imaginário amigável.

Formatado e comentado

n => (                    // main function, takes n as input
  F = k =>                // recursive function, takes k as input
    k >> n ?              // if k is greater or equal to 1 << n:
      --j ?               //   decrement j ; if j is > 0:
        F(k >> j | 1)     //     do a recursive call with an additional bit set
      :                   //   else
        ''                //     stop recursion
    :                     // else
      k + ' ' + F(k * 2)  //   append k to output and do a recursive call with k * 2
  )(1, j = n)             // start the recursion with k = 1 and j = n

Casos de teste

let f =

n=>(F=k=>k>>n?--j?F(k>>j|1):'':k+' '+F(k*2))(1,j=n)

console.log(f(1))
console.log(f(2))
console.log(f(3))
console.log(f(8))
console.log(f(17))

Python 2 , 64 61 bytes

^{-3 bytes graças a Dennis}

n=2**input()
j=i=1
while j<n:
 print i;i*=2
 if i/n:i=j=2*j+1

Experimente online!

Mathematica, 35 bytes

Tr/@Rest@Subsequences[2^Range@#/2]&

Python 2 , 65 63 58 bytes

lambda n:[(2<<k/n)-1<<k%n for k in range(n*n)if k/n+k%n<n]

Experimente online!

Haskell , 37 bytes

f n=[2^b-2^(b-a)|a<-[1..n],b<-[a..n]]

Experimente online!

Haskell, 47 bytes

f n=[1..n]>>= \b->take(n-b+1)$iterate(2*)$2^b-1

Exemplo de uso: f 4-> [1,2,4,8,3,6,12,7,14,15]. Experimente online! .

Como funciona: para cada número bem [1..n], comece com 2^b-1e repetidamente dobrar o valor e tomar n-b+1elementos desta lista.

05AB1E , 6 bytes

L<oΎO

Experimente online! ou como um conjunto de testes

Explicação

Usa o truque de soma de sub-listas, como mostrado na resposta de Dennis 'Jelly

L       # range [1 ... input]
 <      # decrement each
  o     # raise 2 to each power
   Π   # get all sublists
    é   # sort by length
     O  # sum

Groovy, 90 89 bytes

{(0..<2**it).collect{0.toBinaryString(it)}.sort{it.count("1")}.collect{0.parseInt(it,2)}}

A conversão binária é tão burra no groovy.

-1 graças a Gurupad Mamadapur

Pitão, 7 bytes

sM.:^L2

Experimente online.

Usa o algoritmo de Dennis.

Utilitários Bash + Unix, 51 bytes

dc<<<2i`seq -f%.f $[10**$1-1]|grep ^1*0*$|sort -r`f

Experimente online!

A entrada n é passada em um argumento.

Use seq para imprimir todos os números com n ou menos dígitos. (Estes são os números da base 10, portanto, existem muitos números extras aqui. É um desperdício e consome tempo, mas isso é código de golfe!)

A chamada para grep mantém apenas os números que consistem precisamente em 1s seguidos por 0s.

Em seguida, use sort -r para classificá-los em ordem lexicográfica reversa.

Por fim, dc está definido como entrada de base 2 - empurra os números classificados em uma pilha e depois imprime a pilha de cima para baixo. (Isso imprime o último item enviado primeiro, etc., e é por isso que estou usando sort -r em vez de apenas sort.)

Corrigido um erro: eu havia omitido a opção -f% .f para seq, necessária para contagens de números inteiros a partir de 1000000 em diante. (Agradecemos a @TobySpeight por apontar que havia um problema.)

Mathematica / Mathics , 69 bytes

{0,1}~Tuples~#~SortBy~Count@1/.n:{a=0...,1..,a}:>Print@Fold[#+##&,n]&

Experimente online!

Perl 6 , 38 bytes

->\n{map {|(2**$_-1 X+<0..n-$_)},1..n}

Como funciona

->\n{                                }  # A lambda with argument n.
                                 1..n   # Numbers from 1 to n.
     map {                     },       # Replace each one with a list:
            2**$_-1                     #   2 to that power minus 1,
                    X+<                 #   bit-shifted to the left by each element of
                       0..n-$_          #   the range from 0 to n minus the number.
          |(                  )         #   Slip the list into the outer list.

Ou seja, constrói os números assim:

1 2 4 8 = (2^1)-1 bit-shifted to the left by 0 1 2 3 places
3 6 12  = (2^2)-1 bit-shifted to the left by 0 1 2   places
7 14    = (2^3)-1 bit-shifted to the left by 0 1     places
15      = (2^4)-1 bit-shifted to the left by 0       places     ← n rows
             ↑                                     ↑
             n                                     n-1

O código:

Perl 6 , 44 bytes

->\n{map {|(2**$_-1,* *2...^*>2**n-1)},1..n}

Essa foi a minha primeira abordagem antes de pensar na solução de mudança de bits (na verdade mais simples) acima.

Como funciona

->\n{                                      }  # A lambda with argument n.
                                       1..n   # Numbers from 1 to n.
     map {                           }        # Replace each one with:
            2**$_-1                              # 2 to that power minus 1,
                   ,* *2                         # followed by the result of doubling it,
                        ...^                     # repeated until (but not including)
                            *>2**n-1             # it's larger than 2^n-1.
          |(                        )            # Slip the list into the outer list.

Ou seja, constrói os números assim:

1 2 4 8 = (2^1)-1, times 2, times 2, times 2
3 6 12  = (2^2)-1, times 2, times 2
7 14    = (2^3)-1, times 2
15      = (2^4)-1                                ← n rows
             ↑                       ↑
             n                       as many columns as possible in
                                     each row without exceeding (2^n)-1

Haskell 59 46 Bytes

Eu comecei com f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]

da resposta de nimi acima ganhou o insight que sum.map(2^)$[0..x]pode ser condensado até2^x-1

Terminando com

e n=[1..n]>>= \x->map(\y->2^y*(2^x-1))[0..n-x]

[1..n] - lista com o número de bits consecutivos que queremos percorrer`

>> = - traduzido aproximadamente para cada elemento da lista à esquerda, passe-o para a função à direita e concatene todos os resultados

\ x -> - declaração da função lambda com um argumento

map xy - aplica a função x a todos os membros da lista y

No nosso caso x = (\ y-> 2 ^ y * (2 ^ x-1)) - outra função lambda 2 ^ y * (2 ^ x-1)). Essa fórmula surge da multiplicação por duas adicionando um zero à direita em binário (exemplo 0001 a 0010). 2 ^ x - 1 é o número de bits com os quais estamos trabalhando. portanto, para 11, temos 2 ^ 0 * 3 (isto é, não mude nada) == 0011, então 2 ^ 1 * 3 = 0110 e, em seguida, 2 ^ 2 * 3-1100.

[0..nx] Cria a lista de quantas vezes podemos mudar os bits. Se estivermos trabalhando com um único 1, olhando para 0001, queremos mudar 3 vezes (4-1). Se estamos trabalhando com dois 11, queremos 4-2 e assim por diante.

Python 3, 59 bytes

Nota: isso foi feito independentemente das soluções de ovs e de Dennis , embora seja muito semelhante a ambas.

lambda n:[(2<<i)-1<<j for i in range(n)for j in range(n-i)]

Como funciona:

for i in range(n)for j in range(n-i)  # Iterate over number of ones, then number of places
                                      # shifted over. i = ones, j = shifts

(2<<i)                                # Create a one followed by i zeroes
      -1                              # Subtract one from above to get i ones.
        <<j                           # Shift j places.

Experimente online!

Dicas (codificação e dinheiro) são sempre bem-vindas!

Japonês , 11 bytes

o@o!²ãXÄ mx

Teste online!

Explicação

Isso praticamente usa a abordagem de @ Dennis:

o@ o!²  ãXÄ  mx
oX{o!p2 ãX+1 mx}
                  // Implicit: U = input integer
oX{            }  // Create the range [0...U) and map each item X by this function:
   o              //   Create the range [0...U)
    !p2           //     and map each item Z to 2.p(Z); that is, 2**Z.
                  //     (p2 would map each item Z to Z.p(2); ! reverses the arguments.)
        ãX+1      //   Get all overlapping slices of length X + 1.
             mx   //   Map each of these slices Z through Z.x(); that is, sum each slice.
                  // Implicit: output result of last expression

Python , 61 59 bytes

lambda n:[2**-~i-1<<j for i in range(n)for j in range(n-i)]

Experimente online!

PHP, 59 56 53 bytes

for(;$p>($k*=2)?:($p=1<<$argn)>$k=$i+=$i+1;)echo$k,_;

recebe entrada do STDIN; corra com -R.

demolir

for(;$p>($k*=2)         // 3. inner loop: shift-0 $k while $k<$p (false in first iteration)
    ?:
    ($p=1<<$argvn)      // 1. init $p=2^N, outer loop:
    >$k=$i+=$i+1        // 2. shift-1 $i while $i<$p, init $k to new $i
;)
    echo$k,_;           // 4. print $k

J , 19 bytes

(0-.~&,>:+/\2&^)@i.

Isso usa o mesmo método na solução @Dennis ' .

Experimente online!

Explicação

(0-.~&,>:+/\2&^)@i.  Input: integer n
                 i.  Range [0, 1, ..., n-1]
(              )@    Operate on that range
            2&^        Compute 2^x for each x in that range
       >:              Increment each in that range
           \           For each overlapping sublist of size (previous) in powers of 2
         +/              Reduce by addition
 0                     The constant 0
     &,                Flatten each
  -.~                  Remove zeroes

Python 3, 91 bytes

a=int(input())
print(*[int('1'*-~b,2)<<c for b in range(a)for c in range(a-b)],sep=', ')

Programa completo, com saída separada por vírgula + espaço, conforme especificado.

Explicação:

A notação em estrela descompacta as listas. Então print(*[1,2,3])é o mesmo que print(1,2,3). Passe ao int()construtor uma sequência de '1's consecutivos.

-~bavalia como b+1, mas você não precisa cercá-lo entre colchetes ao multiplicar uma sequência.

Bitshift o número inteiro produzido um número crescente de vezes. print()possui o argumento sep opcional, especificando a sequência a ser inserida entre cada item em uma lista descompactada.

Java 7, 108 bytes

static void x(int i){int a=0,t=1<<i,b;while((a=(a<<1)+1)<t){b=a;do System.out.println(b);while((b<<=1)<t);}}

Dobra o valor inicial desde que o resultado seja menor que 2^n. Posteriormente, atualiza o valor inicial a ser (initial_value * 2) + 1e inicia novamente a partir daí até que finalmente chegue (2^n)-1.

por exemplo, para n=4:

0001 -> init
0010
0100
1000
return, double init and add one
0011 -> init
0110
1100
return, double init and add one
0111 -> init
1110
return, double init and add one
1111 -> init
done

Experimente online!

Ruby, 50 bytes

->r{1.upto(r){|x|p a=2**x-1;p a while(a*=2)<2**r}}

Tentei algumas abordagens "inteligentes", mas essa parece ser a mais curta (literalmente, siga as instruções)

Explicação:

Cada iteração começa com 2 ^ n-1 e multiplica por 2 até que o limite superior seja atingido. Nada extravagante, apenas matemática básica.

QBIC , 37 bytes - bônus imaginário = ainda 37 bytes ...

:[a|e=2^b-1┘while e<2^a┘?e┘e=e*2┘wend

Pena que ainda não while-wendintegrei o QBIC ... Explicação:

:       Get N from the command line
[a|     For b = 1 to N; The sequence is reset N times
e=2^b-1 Set the first number of this sub-sequence (yields 1, 3, 7, 15 ...)
┘       Line-break - syntactic separation of commands because there's no command for WHILE yet.
while   Pure QBasic code - lower-case is not (really) interpreted by QBIC
e<2^a   Continue as long as we don't exceed the maximum value
┘?e     Print the number in the sequence
┘e=e*2  Double the number
┘wend   And loop as long as we're not exceeding maximum, reset the sequence otherwise.
        FOR loop auto-closed by QBIC

EDIT: QBIC agora tem suporte para WHILE:

:[a|e=2^b-1≈e<2^a|?e┘e=e*2

Isso é apenas 26 bytes! Aqui está o WHILE:

≈e<2^a|          ≈ = WHILE, and the TRUE condition is everything up to the |
       ...       Loop code goes here
          ]      Close construct: adds a WEND instruction
                 In the program above, this is done implicitly because of EOF.

MATL, 19 18 bytes

1 byte salvo graças a @Luis

:q2w^XJfP"J@YC2&sv

Experimente Online

R , 69 48 46 bytes

n=scan();for(i in 1:n)print((2^i-1)*2^(i:n-i))

Cada número decimal correspondente aos do i in 1..nsistema binário é multiplicado por 2^(0..n-i), ou seja, primeiras n-i+1potências de dois (1, 2, 4, ...).

Experimente online!

Stax , 9 bytes

übg▓}╥é►╪

Execute e depure online!

Explicação

Bônus imaginário se alguém fizer isso sem nenhuma forma de conversão básica (usando simples matemática antiga).

Bem, não há conversão básica aqui.

Usa a versão descompactada (10 bytes) para explicar.

m|2vx_-DQH
m             For input=`n`, loop over `1..n`
 |2v          Power of two minus one
    x_-D      Do `n-j` times, where `j` is the current 1-based loop index
        Q     Output the current value
         H    And double it

Lote, 92 - 0 = 92 bytes

@for /l %%i in (1,1,%1)do @for /l %%j in (%%i,1,%1)do @cmd/cset/a"(1<<%%i)-1<<%%j-%%i"&echo(

Subtraindo 0 para o bônus imaginário de @ StewieGriffin.