Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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"!

share|improve this question
    
A dup of codegolf.stackexchange.com/q/98322/61904 ? – zeppelin 16 hours ago
2  
@zeppelin I thought so too at first, but this one is very different. – ETHproductions 16 hours ago
1  
Related. (Slightly.) – Martin Ender 16 hours ago
4  
Imaginary bonus if someone does this without any form of base conversion (using plain old maths). – Stewie Griffin 15 hours ago

25 Answers 25

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)
share|improve this answer
2  
Wow. Not only is that a really cool/clever trick, but it's extremely effective. +1, really nice answer! – DJMcMayhem 11 hours ago
2  
The [f] is an amusing touch, can't say I've seen that before. – FryAmTheEggman 10 hours ago

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.
share|improve this answer
1  
is an ideal built-in for this challenge, and it's implemented so that the results are in just the right order for this challenge. Well done :-) – ETHproductions 15 hours ago

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

share|improve this answer

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

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

share|improve this answer

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

share|improve this answer
1  
Note: This solution is identical to @mile 's Mathematica code, posted 5 hours before @GregMartin 's edit. However, per meta consensus, this answer is still valid. – JungHwan Min 7 hours ago
    
Ugh, I didn't see that—thanks for pointing it out. – Greg Martin 7 hours ago

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!

share|improve this answer
1  
I just spent an hour coming up with that formula (2<<i)-1<<j ... and you've already figured it out. Great job! Also, good job at getting rid of the double ranges – TheNumberOne 4 hours ago

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!

share|improve this answer

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.

share|improve this answer

Groovy, 90 bytes

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

Binary conversion is so dumb in groovy.

share|improve this answer
2  
28 bytes binary conversion boilerplate, so painful. – carusocomputing 15 hours ago

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
share|improve this answer

Mathematica, 35 bytes

Tr/@Rest@Subsequences[2^Range@#/2]&
share|improve this answer

Mathematica/Mathics, 69 bytes

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

Try it online!

share|improve this answer

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.

share|improve this answer
2  
You can just print the list. The output format isn't so strict. – mbomb007 14 hours ago

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
share|improve this answer

Pyth, 7 bytes

sM.:^L2

Try it online.

Uses Dennis's algorithm.

share|improve this answer

Python 3, 61 bytes

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

Try it online!

share|improve this answer

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
share|improve this answer

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.

share|improve this answer

Haskell, 37 bytes

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

Try it online!

share|improve this answer

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!

share|improve this answer

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.

share|improve this answer

MATL, 19 bytes

:q2w^XJn:P"J@YC2&sv

Try it Online

share|improve this answer

Japt, 11 bytes

o@o!²ãXÄ mx

Test it online!

Explanation

This pretty much uses @Dennis's approach:

o@o!²ãXÄ mx  // Implicit: U = input integer
o@           // Create the range [0...U) and map each item X by this function:
  o!²        //   Create the range [0...U) and map each item Z to 2**Z.
     ãXÄ     //   Get all overlapping slices of length X + 1.
         mx  //   Map by summation.
             // Implicit: output result of last expression
share|improve this answer

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
share|improve this answer

Bash + Unix utilities, 45 bytes

dc<<<2i`seq $[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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.