38
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ A dup of codegolf.stackexchange.com/q/98322/61904 ? \$\endgroup\$ – zeppelin Feb 7 '17 at 17:53
  • 2
    \$\begingroup\$ @zeppelin I thought so too at first, but this one is very different. \$\endgroup\$ – ETHproductions Feb 7 '17 at 17:54
  • 1
    \$\begingroup\$ Related. (Slightly.) \$\endgroup\$ – Martin Ender Feb 7 '17 at 18:01
  • 6
    \$\begingroup\$ Imaginary bonus if someone does this without any form of base conversion (using plain old maths). \$\endgroup\$ – Stewie Griffin Feb 7 '17 at 18:13
  • \$\begingroup\$ Wrote this which is a mix between the two I guess Try it online! \$\endgroup\$ – PrincePolka Mar 7 '18 at 19:13

32 Answers 32

38
\$\begingroup\$

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)
\$\endgroup\$
  • 4
    \$\begingroup\$ Wow. Not only is that a really cool/clever trick, but it's extremely effective. +1, really nice answer! \$\endgroup\$ – DJMcMayhem Feb 7 '17 at 22:54
  • 2
    \$\begingroup\$ The [f] is an amusing touch, can't say I've seen that before. \$\endgroup\$ – FryAmTheEggman Feb 7 '17 at 23:46
18
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ 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 :-) \$\endgroup\$ – ETHproductions Feb 7 '17 at 18:26
  • \$\begingroup\$ Isn't this 12 bytes (at least in UTF-8)? \$\endgroup\$ – Gareth Feb 9 '17 at 17:23
  • 1
    \$\begingroup\$ @Gareth Yes, but Jelly also supports a single byte character set, which contains the only 256 symbols it understands. \$\endgroup\$ – Dennis Feb 9 '17 at 17:24
9
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – JungHwan Min Feb 8 '17 at 2:19
  • \$\begingroup\$ Ugh, I didn't see that—thanks for pointing it out. \$\endgroup\$ – Greg Martin Feb 8 '17 at 2:23
8
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Suggestion(after having to check "dont show anymore popups"): Change to console.log for the test snippet. \$\endgroup\$ – Tejas Kale Feb 9 '17 at 13:18
  • \$\begingroup\$ @TejasKale Good idea, thanks! \$\endgroup\$ – ETHproductions Feb 9 '17 at 13:54
7
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

Mathematica, 35 bytes

Tr/@Rest@Subsequences[2^Range@#/2]&
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – TheNumberOne Feb 8 '17 at 6:03
5
\$\begingroup\$

Haskell, 37 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
  • 3
    \$\begingroup\$ 28 bytes binary conversion boilerplate, so painful. \$\endgroup\$ – Magic Octopus Urn Feb 7 '17 at 18:11
  • 1
    \$\begingroup\$ {(1..<2**it)... saves a byte. \$\endgroup\$ – Gurupad Mamadapur Feb 8 '17 at 14:47
3
\$\begingroup\$

Pyth, 7 bytes

sM.:^L2

Try it online.

Uses Dennis's algorithm.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ "Wasteful and time-consuming" ... and clever! Thanks for this - it's a good reminder to wilfully ignore computational efficiency when golfing. That's really hard when you spend the rest of your days writing fast and clear code... \$\endgroup\$ – Toby Speight Feb 9 '17 at 11:17
  • \$\begingroup\$ Some values missing: dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc - only reports 12 values. I think you want grep ^1[01]*$ instead. \$\endgroup\$ – Toby Speight Feb 9 '17 at 11:20
  • \$\begingroup\$ @TobySpeight Thanks -- there was a bug, which I've corrected. The problem wasn't with the regex; the issue was that seq required an option. (I'm not sure why you were only getting 12 output values though -- even the incorrect version produced 21 output values intead of the correct 28. If you were running this on TIO, it may well have exceeded TIO's 1-minute time limit.) I've tested this on both Linux and OS X now. \$\endgroup\$ – Mitchell Spector Feb 11 '17 at 3:24
  • 1
    \$\begingroup\$ Actually, I misunderstood the question - the important word "consecutive" there somehow went straight past me! \$\endgroup\$ – Toby Speight Feb 13 '17 at 9:10
2
\$\begingroup\$

Mathematica/Mathics, 69 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Python, 61 59 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You can use $argn Very good idea. After reading the question I have in my head a solution with over 200 Bytes \$\endgroup\$ – Jörg Hülsermann Apr 14 '17 at 22:37
  • \$\begingroup\$ @JörgHülsermann Thanks for reminding me of STDIN. I just love merging loops. \$\endgroup\$ – Titus Apr 15 '17 at 5:43
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ You can just print the list. The output format isn't so strict. \$\endgroup\$ – mbomb007 Feb 7 '17 at 19:18
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

MATL, 19 18 bytes

1 byte saved thanks to @Luis

:q2w^XJfP"J@YC2&sv

Try it Online

\$\endgroup\$
  • 1
    \$\begingroup\$ @LuisMendo very clever! Thanks \$\endgroup\$ – Suever Jul 22 '17 at 13:17
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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