Output numbers up to 2^n-1, "sorted"

Question

Take a positive integer n as input, and output (some of the) decimal numbers that can be created using n bits, ordered in the following way:

First list all the numbers that can be created with only one 1, and the rest 0 in the binary representation (sorted), then all the numbers that can be created with two consecutive 1, the rest 0, then three consecutive 1 and so on.

Let's see what this looks like for n=4:

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

So, the output for n=4 is: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (optional output format).

Test cases:

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

This is code-golf, so the shortest code in each language wins!

Good explanations are highly encouraged, also for solutions in "regular languages"!

Answer 1

Python, 53 bytes

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

Try it online!

The recursive function generates the sorted list as a pre-order walk down this tree (example with n=4):

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

1 2 4 8 3 6 12 7 14 15

Left branches double the value, and right branches do i->i*2+1 and exist only for odd i. So, the pre-order walk for non-leaves is T(i)=[i]+T(i*2)+i%2*T(i*2+1).

The tree terminates at depth n, where n is the input. This is achieved by decrementing n with each step down and stopping when it is 0.

An alternative strategy would be to terminate on values that i exceeds 2**n, rather than tracking depth. I found this to be one byte longer:

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)

Answer 2

Jelly, 6 bytes

Ḷ2*ẆS€

This qualifies for the imaginary bonus.

Try it online!

How it works

Ḷ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.

Answer 3

Mathematica, 40 bytes

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

Every number in the desired list is the difference of two powers of 2, so we simply generate them in order using Table and then flatten the list. I think this earns Stewie Griffin's imaginary bonus :)

Mathematica, 35 bytes

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

A port of Dennis's Jelly algorithm. I didn't know about Subsequences before this! (I also didn't see that miles had posted this exact answer ... go upvote it!)

Answer 4

JavaScript (ES6), 59 58 55 bytes

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

A full program that takes input through a prompt and alerts each number in succession. This also qualifies for the imaginary bonus.

Test snippet

(Note: uses console.log instead of alert)

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

Answer 5

JavaScript (ES6), 55 51 bytes

Returns a space-separated list of integers.

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

Imaginary bonus friendly.

Formatted and commented

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

Test cases

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

Answer 6

Python 2, 64 61 bytes

^{-3 bytes thanks to Dennis}

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

Try it online!

Answer 7

Mathematica, 35 bytes

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

Answer 8

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]

Try it online!

Answer 9

Haskell, 37 bytes

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

Try it online!

Answer 10

Groovy, 90 89 bytes

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

Binary conversion is so dumb in groovy.

-1 thanks to Gurupad Mamadapur

Answer 11

Haskell, 47 bytes

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

Usage example: f 4 -> [1,2,4,8,3,6,12,7,14,15]. Try it online!.

How it works: for each number b in [1..n], start with 2^b-1 and repeatedly double the value and take n-b+1 elements from this list.

Answer 12

05AB1E, 6 bytes

L<oΎO

Try it online! or as a Test suite

Explanation

Uses the sublist-sum trick as shown in Dennis' Jelly answer

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

Answer 13

Pyth, 7 bytes

sM.:^L2

Try it online.

Uses Dennis's algorithm.

Answer 14

Bash + Unix utilities, 51 bytes

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

Try it online!

The input n is passed in an argument.

Use seq to print all numbers with n or fewer digits. (These are base-10 numbers, so there are lots of extra numbers here. It's wasteful and time-consuming, but this is code golf!)

The call to grep keeps only those numbers that consist precisely of 1s followed by 0s.

Then use sort -r to sort these in reverse lexicographical order.

Finally, dc is set to base 2 input -- it pushes the sorted numbers on a stack and then prints the stack from top to bottom. (This prints the last item pushed first, etc., which is why I'm using sort -r instead of just sort.)

Corrected a bug: I had omitted the option -f%.f to seq, which is required for integer counts from 1000000 on. (Thanks to @TobySpeight for pointing out that there was a problem.)

Answer 15

Mathematica/Mathics, 69 bytes

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

Try it online!

Answer 16

Python, 61 59 bytes

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

Try it online!

Answer 17

Japt, 11 bytes

o@o!²ãXÄ mx

Test it online!

Explanation

This pretty much uses @Dennis's approach:

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

Answer 18

Perl 6, 38 bytes

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

How it works

->\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.

I.e. it constructs the numbers like this:

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

The code:

---

Perl 6, 44 bytes

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

This was my first approach before I thought of the (actually simpler) bit-shift solution above.

How it works

->\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.

I.e. it constructs the numbers like this:

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

Answer 19

Haskell 59 46 Bytes

I started out with f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]

from nimi's answer above gained the insight that sum.map(2^)$[0..x] can be condensed down to 2^x-1

Ending up with

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

[1..n] -- list with number of consecutive bits we want to cycle through`

>>= --roughly translated for each element in list on left pass it into the function on right and concatenate all results

\x -> -- lambda function declaration with one argument

map x y-- applies function x to all members of the list y

In our case x = (\y->2^y*(2^x-1)) -- another lambda function 2^y*(2^x-1)). This formula arises from multiplication by two adding a zero to right in binary(example 0001 to 0010). 2^x - 1 is the number of bits we are working with. so for 11 we have 2^0*3(i.e. dont shift at all) == 0011, then 2^1*3 = 0110 then 2^2*3 - 1100.

[0..n-x] Builds the list of how many times we can shift the bits. If we are working with a single 1 then looking at 0001 we want to shift 3 times (4-1). If we are working two 11 we want 4-2 and so on.

Answer 20

Python 3, 59 bytes

Note: this was made independently of ovs's and Dennis's solutions, even though it is very similar to both.

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

How it works:

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.

Try it online!

Tips (both coding and cash) are always welcome!

Answer 21

PHP, 59 56 53 bytes

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

takes input from STDIN; run with -R.

breakdown

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

Answer 22

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=', ')

Full program, with comma+space separated output, as specified.

Explanation:

Star notation unpacks lists. So print(*[1,2,3]) is the same as print(1,2,3). Pass the int() constructor a string of consecutive '1's.

-~b evaluates to b+1, but you don't have to surround it with brackets when multiplying a string.

Bitshift the produced integer an increasing number of times. print() has the optional sep argument, specifying the string to put in between each item in an unpacked list.

Answer 23

J, 19 bytes

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

This uses the same method in @Dennis' solution.

Try it online!

Explanation

(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

Answer 24

MATL, 19 18 bytes

1 byte saved thanks to @Luis

:q2w^XJfP"J@YC2&sv

Try it Online

Answer 25

QBIC, 37 bytes - imaginary bonus = still 37 bytes...

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

Shame I haven't built while-wend into QBIC yet... Explanation:

:       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 now has support for WHILE:

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

This is only 26 bytes! Here's the 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.

Answer 26

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

Doubles the initial value as long as the result is smaller than 2^n. Afterwards, updates the initial value to be (initial_value * 2) + 1 and starts again from there until it eventually reaches (2^n)-1.

e.g. for 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

Try it online!

Answer 27

Ruby, 50 bytes

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

I tried some "clever" approaches, but this seems to be the shortest (literally follow the instructions)

Explanation:

Each iteration starts with 2^n-1 and multiplies by 2 until the upper limit is reached. Nothing fancy, just basic math.

Answer 28

R, 69 48 46 bytes

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

Each decimal number corresponding to i in 1..n ones in binary system is multiplied by 2^(0..n-i), i.e first n-i+1 powers of two (1, 2, 4, ...).

Try it online!

Answer 29

Stax, 9 bytes

übg▓}╥é►╪

Run and debug online!

Explanation

Imaginary bonus if someone does this without any form of base conversion (using plain old maths).

Well, there are no base conversion here.

Uses the unpacked version (10 bytes) to explain.

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

Answer 30

Batch, 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(

Subtracting 0 for @StewieGriffin's imaginary bonus.

Answer 31

C, 69 bytes

New way:

m;s;f(n){for(m=1;m<<=1<=1<<n;)for(s=m-1;s<1<<n;s*=2)printf("%d ",s);}

previous 72 bytes solution:

i;s;f(n){for(i=1;i<=n;++i){for(s=(1<<i)-1;s<1<<n;s*=2)printf("%d ",s);}}

Answer 32

Perl 5, 51 bytes

map{$_=2**$_-1;do{say}while($_*=2)<2**$l}1..($l=<>)

Try it online!