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

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 , so the shortest code in each language wins!

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

• Commented Feb 7, 2017 at 17:53
• @zeppelin I thought so too at first, but this one is very different. Commented Feb 7, 2017 at 17:54
• Related. (Slightly.) Commented Feb 7, 2017 at 18:01
• Imaginary bonus if someone does this without any form of base conversion (using plain old maths). Commented Feb 7, 2017 at 18:13
• Wrote this which is a mix between the two I guess Try it online! Commented Mar 7, 2018 at 19:13

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


# Perl 5, 51 bytes

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


Try it online!