Collatz Encoding

Question

The Collatz Conjecture

The famous Collatz Conjecture (which we will assume to be true for the challenge) defines a sequence for each natural number, and hypothesizes that every such sequence will ultimately reach 1. For a given starting number N, the following rules are repeatedly applied until the result is 1:

While N > 1:

• If N is even, divide by 2
• If N is odd, multiply by 3 and add 1

Collatz Encoding

For this challenge, I have defined the Collatz encoding of a number, such that the algorithm specified in the conjecture may be used to map it to another unique number. To do this, you start with a 1 and at each step of the algorithm, if you divide by 2 then append a 0, otherwise append a 1. This string of digits is the binary representation of the encoding.

As an example we will compute the Collatz Encoding of the number 3, with the appended digits marked. The sequence for 3 goes

₍₁₎ 3 ->₁ 10 ->₀ 5 ->₁ 16 ->₀ 8 ->₀ 4 ->₀ 2 ->₀ 1.

Therefore, our encoding is 208 (11010000 in binary).

The Challenge

Your challenge is to write a function or program which takes an integer (n>0) as input, and returns its Collatz encoding. This is a code golf challenge, so your goal is to minimize the number of bytes in your answer.

• For the edge case n=1, your solution should return 1, because no iterations are computed and every encoding starts with a 1.

• Floating point inaccuracies in larger results are acceptable if your language cannot handle such numbers accurately (encodings on the order of 10^40 as low as 27)

Test Cases

I have written a reference implementation (Try It Online!) which generates the encodings of the first 15 natural numbers:

 1 | 1
 2 | 2
 3 | 208
 4 | 4
 5 | 48
 6 | 336
 7 | 108816
 8 | 8
 9 | 829712
 10 | 80
 11 | 26896
 12 | 592
 13 | 784
 14 | 174352
 15 | 218128

Answer 1

Python 2, 49 bytes

f=lambda n,x=1:1/n*x or f(n/2-n%2*~n,x-n%2*~x<<1)

Try it online!

Explanation

Notice the following: if n is odd, 3*n+1 must be even. This means that in the odd case, we can combine two steps into one, with (3*n+1)/2. Although it seems more complicated, the formula actually becomes much shorter:

[n/2,(3*n+1)/2][n%2]
[n/2,n+n/2+1][n%2]
n/2+[0,n+1][n%2]
n/2+n%2*(n+1)
n/2+n%2*-~n
n/2-n%2*~n

Then, to calculate the Collatz encoding, we'll append [0] if n is even, and [1, 0] if n is odd. Working on integers, we see that x becomes [x*2,x*4+2][n%2]. This can be further reduced to x-n%2*~x<<1 (proof is left as an exercise to the reader).

Python 2, 50 bytes

f=lambda n,x=1:1/n*x or f(n/2-n%2*~n<<n%2,x*2+n%2)

Try it online!

The "obvious" method to compute the next term would be [n/2,3*n+1][n%2], but we can do better with a little bit magic: n/2-n%2*~n<<n%2. It can be derived by working backwards:

[n/2,3*n+1][n%2]
[n/2,(3*n+1)/2][n%2]<<n%2
n/2+[0,n+1][n%2]<<n%2
n/2+n%2*(n+1)<<n%2
n/2+n%2*-~n<<n%2
n/2-n%2*~n<<n%2

• loopy walt: Damn. I was sitting on it too long ...
• EmilyR: Awesome solution! I came to this same realization, but couldn't figure out how to shorten the formula.

Answer 2

FRACTRAN, 11 fractions (72 bytes) and reversible

$$\frac{7}{13},\frac{11}{17},\frac{247}{35},\frac{338}{441},\frac{104}{21},\frac{425}{209},\frac{153}{44},\frac{85}{49},\frac{169}{22},\frac{17}{7},\frac{195}{11}$$

The input is \11ドル\cdot 2^{n-1}\$ and the output is \11ドル\cdot 5^{k-1}\$ where \$k\$ is the Collatz encoding of \$n\$. (Note: it doesn't halt there. It will go on to generate all the other redundant encodings of this technically multivalued function, for every number of \4,2,1ドル\$ cycles.)

If you replace all the instructions with their reciprocals and give it \11ドル\cdot 5^{k-1}\$ as input, it will compute \11ドル\cdot 2^{n-1}\$.

• Qaziquza: Incredible answer! Wow!
• Neil: I don't know FRACTRAN so is it legitimate to provide input in any form other than pn for some prime p?
• benrg: @Neil I don't know if there are official rules. I subtracted one from the input and output for esthetic, not golfing reasons: they're 1-based but FRACTRAN is 0-based. Extra factors are pretty common in answers here. This FRACTRAN-specific challenge bans them, while this one by the same user allows them. I don't like the 11 factor in this answer, but I couldn't see how to make it reversible otherwise. State-transition instructions have to work both ways, so they have to be after other instructions of both states, so every state needs a way to test for itself.

Answer 3

JavaScript (ES6), 41 bytes

f=(n,o=1)=>n>1?f(n&1?n*3+1:n/2,2*o|n&1):o

Try it online!

Commented

f = ( // f is a recursive function taking:
 n, // n = input
 o = 1 // o = output, initialized to 1
) => //
n > 1 ? // if n is still greater than 1:
 f( // do a recursive call:
 n & 1 ? // if n is odd:
 n * 3 + 1 // use 3n + 1
 : // else:
 n / 2, // use n / 2
 2 * o | n & 1 // append the parity bit of n to the output
 ) // end of recursive call
: // else:
 o // we're done: return the output

• AncientSwordRage: I love the :o at the end.... It's pretty much my face when trying to understand this... How does it work?
• Arnauld: @AncientSwordRage Explanation added, BTW. (I forgot to ping you.)

Answer 4

Python 3.8 (pre-release), 55 bytes

f=lambda n,e=1:e*(n<2)or f(n*3//(6-5*(c:=n%2))+c,2*e+c)

Try it online!

This one uses an extra byte to do integer division since otherwise the answers accrue floating point innacuracy. I decided to submit the one with the extra / because Python can handle arbitrarily large integers according to your memory.

• ovs: n*3//(6-5*c)+c can be (3*n+1)//(6-5*c), which leads to 53 bytes. (One more byte could be saved by switching to Python 2)

Answer 5

K (ngn/k), 31 bytes

2/1 :':2!(1<){(-2!x;1+3*x)2!x}\

Try it online!

• doug: Almost all other solutions here carry two arguments through the iteration. Calculating the encoding on the Collatz sequence is a novel approach.

Answer 6

x86 32-bit machine code, 20 bytes

41 D1 E9 73 0A 6B C9 06 83 C1 04 0F 29 C0 F9 D1 D0 E2 ED C3

Try it online!

Uses the fastcall calling convention – argument in ECX, result in EAX.

In assembly:

s: inc ecx # Add 1 to restore the value of ECX.
 shr ecx, 1 # Shift ECX right by 1; the low bit goes into CF.
 jnc a # Jump if CF=0 (the number was even).
 imul ecx, 6 # Multiply ECX by 6.
 add ecx, 4 # Add 4 to ECX, producing 3n+1 where n is the original value
 .byte 0x0F # Effectively skip an instruction by making it part of a harmless "movaps xmm0, xmm0".
f: sub eax, eax # (Start here.) Set EAX to 0.
 stc # Set CF to 1.
a: rcl eax, 1 # Append CF to the bits of EAX.
 loop s # Subtract 1 from ECX and jump if it's nonzero.
 ret # Return.

Answer 7

Haskell, (削除) 55 (削除ここまで) (削除) 53 (削除ここまで) 49 bytes

-2 bytes thanks to Unrelated String

a?n|n<2=a|p<-mod n 2=(2*a+p)?(6^p*n`div`2+p)
(1?)

The solution is the anonymous function (1?). Attempt This Online!

Explanation

Port of my BQN solution, essentially. We define an infix function ? that takes an accumulator a and a number n:

a ? n

When n is 1, just return the accumulator:

 | n < 2 = a

Otherwise, calculate n mod 2 and assign to p (for "parity"):

 | p <- mod n 2

Compute the new accumulator and number, and recurse:

 = (2 * a + p) ? (6 ^ p * n `div` 2 + p)

The new accumulator is simply twice the current accumulator plus the parity (2 * a + p). The Collatz function calculation is a little more involved:

6^p*n`div`2+p
6^p 6 to the power of the parity (1 if even, 6 if odd)
 *n Times n (n if even, 6*n if odd)
 `div`2 Int-divided by 2 (n `div` 2 if even, 3*n if odd)
 +p Plus the parity (n `div` 2 if even, 3*n+1 if odd)

Then our solution is simply ? with a first argument (initial accumulator value) of 1.

• Unrelated String: Can shave 1 off with infix, and another with some guard abuse

Answer 8

Pip, (削除) 27 (削除ここまで) (削除) 26 (削除ここまで) 25 bytes

Wa>1Io+:o+Y%aa:6Ey*a/2+yo

Attempt This Online!

Explanation

Wa>1Io+:o+Y%aa:6Ey*a/2+yo
 a is first cmdline input; o is 1 (implicit)
W While
 a>1 a is greater than 1:
 %a Parity of a (0 if even, 1 if odd)
 Y Yank into y variable
 o+ Add current value of o
 o+: Add that total to o in-place
 New value of o is 2*o+%a
 I If new value of o is truthy (which is always the case):
 6Ey 6 to the power of y (1 if a is even, 6 if odd)
 *a Times a
 /2 Divided by 2 (a/2 if even, 3*a if odd)
 +y Plus y (a/2 if even, 3*a+1 if odd)
 a: Assign that result back to a
 o Autoprint the final value of o

Answer 9

C (gcc), 49 bytes

e;f(n){for(e=1;~-n;n=n%2?++e,3*n+1:n/2)e+=e;n=e;}

Try it online!

Inputs an integer.
Returns its Collatz encoding.

Answer 10

Husk, 17 bytes

ḋ:1m%2↑←¡?o→*31⁄2%2

Try it online!

Should be golfable. Ties ḋ:1hm%2U¡?o→*31⁄2%2 courtesy of @Razetime.

 ¡ Infinitely iterate on the argument:
 ? %2 if even,
 1⁄2 halve, else
 o→*3 3n+1.
 ↑← Take while != 1,
 m%2 map mod 2,
 :1 prepend 1,
ḋ convert from binary.

Only reason I thought to use Husk for this is this almost works:

Husk, 19 bytes

ḋ:1↔tḋ€Σ¡ṁ§eDo/3←;1

Try it online!

Unfortunately manages to give 3840 instead of 829712 for 9, by virtue of not actually caring about the paths deterministically chosen (takes 28 to 85 as well as 14).

 ¡ Infinitely iterate
 ;1 starting from [1]
 ṁ concat-map
 §e \n -> [ , ]
 D 2*n
 o/3← n-1/3 ,
 Σ concatenate the iterations,
 € find the first 1-index of the input in them,
 ḋ convert to binary,
 t remove the leading 1,
 ↔ reverse,
 :1 put the leading 1 back,
ḋ and convert from binary.

• Razetime: another 17: ḋ:1hm%2U¡?o→*3½%2

Answer 11

K (ngn/k), (削除) 53 (削除ここまで) (削除) 52 (削除ここまで) (削除) 48 (削除ここまで) 46 bytes

*|{$[1=n:*x;:x;*p;1+3*n;-2!n],2/|p:2 0!'x}/|1,

Try it online!

Pretty straightforward stab at this. Recurse with accumulator carrying both the number and the encoding.

-1 found a byte by using encode
-4 trying to remember lessons coltim passed on. (use tacit)
-2 don’t need list syntax

Answer 12

Python 3.8 (pre-release), 50 bytes

f=lambda n,x=0:4//n*x/2or f(1-6*n//(l:=n^-n),~x*l)

Try it online!

Returns a float (+1 byte for int).

Test harness from @dingledooper or whoever they nicked it from ;-)

How?

Straight-forward recursion with one twist: Group n steps down, 1 step up into one iteration. This avoids branching at the expense of a slightly more complicated body. Detail: Recall that n^-n clears the lowest set bit in n and sets all above including the sign bit, so this is effectively the same as -2 * (n&-n)

Answer 13

Retina 0.8.2, (削除) 72 (削除ここまで) 68 bytes

.+
$*1;1
{+`^(1+)1円;(1+)
1ドル;2ドル2ドル
^1;(1+)
$.1
(1+);(1+)
11ドル1ドル1ドル;12ドル2ドル

Try it online! Link is to test suite that computes the results from 1 to n. Explanation:

.+
$*1;1

Convert n to unary and pair it with an initial output value of 1.

{`

Repeat while the input is paired.

+`^(1+)1円;(1+)
1ドル;2ドル2ドル

While n is even, halve it and double the output value.

^1;(1+)
$.1

If n is 1, then delete it and convert the output to decimal.

(1+);(1+)
11ドル1ドル1ドル;12ドル2ドル

Otherwise, triple n, double the output, and increment both of them.

After porting to Retina 1, it's possible to golf the answer down to 53 bytes, but for some reason it becomes inordinately slow:

.+
_;$&*
+`(_+);(_+)2円(_?)
1ドル1ドル3ドル;2ドル$.3*$(4*_5*2ドル
\G_

Try it online! Link includes faster test cases. Explanation:

.+
_;$&*

Convert n to unary and pair an initial output value of 1 with it.

+`(_+);(_+)2円(_?)
1ドル1ドル3ドル;2ドル$.3*$(4*_5*2ドル

While n is greater than 1, perform a Collatz step on it, updating the output value appropriately. Here 1ドル is the previous output value, 2ドル is n//2 (integer division) and 3ドル is n%2, thus n is replaced by n//2+n%2*(n//2*5+4) which computes equal to n*3+1 when n is odd.

\G_

Convert the output value to decimal and delete n.

Answer 14

Haskell, 107 bytes

s d 0=0
s(a:q)n=a*2^n+(s q$n-1)
f n|n<2=[]|even n=0:f(div n 2)|1>0=1:f(n*3+1)
r 1=1
r n=s(1:f n)$length$f n

Attempt This Online!

I am new to Haskell golf, so I apologize for any bits of this that are outrageously ungolfed.

• Qaziquza: Thanks for the help @Steffan!
• Qaziquza: Fixed, if probably sub-optimally. Thanks for pointing that out!
• DLosc: n>1 works in place of n\=1; but even better, if you rearrange the order of the guards to put |n<2=[] first, you don't need to check n>1&& on the others.
• Qaziquza: Thanks for the help @DLosc! That saved a ton of bytes!

Answer 15

Factor + math.extras project-euler.014, 59 bytes

[ collatz [ < ] monotonic-count rest 1 prefix 48 v+n bin> ]

Try it online!

There is no way Factor would be competitive using the mathy recursive algorithm. Too many symbols means too much whitespace. So we take advantage of the fact that Factor has a built-in collatz sequence word and a simple way to detect increases in a sequence.

Explanation

 ! 3
collatz ! { 3 10 5 16 8 4 2 1 }
[ < ] monotonic-count ! { 0 1 0 1 0 0 0 0 } (did it increase? then 1)
rest 1 prefix ! { 1 1 0 1 0 0 0 0 } (change first element to 1)
48 v+n ! { 49 49 48 49 48 48 48 48 } (add 48 [equivalent to "11010000"])
bin> ! 208 (convert from binary)

Answer 16

Re:direction, (削除) 42 (削除ここまで) 38 bytes

++v
v>
<
+>+
>v
+> >
v
+> >>
> >v
+ >>

Try it online!

The following notation will be used for the contents of the queue: a number means that many ►s, and | means one ▼. If the input number is N, the initial queue is N|, but for the purpose of this program, it's better to view it as N|0.

This program works through the Collatz iterations, while having the second number be 1 less than a number containing the result bits. It does two iterations at a time for odd numbers greater than 1. The possibilities are as shown:

Execution path for 1

Execution path for 2N Execution path for 2N+1

Answer 17

Charcoal, 30 bytes

×ばつ3θ÷θ2θI↨2υ

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input n.

⊞υ1

Start with a Collatz encoding of 1.

W⊖θ

Repeat until n=1.

×ばつ3θ÷θ2θ

Save n%2 to the encoded value, and switch on that to halve or increment and triple n as appropriate. (Note that in order to avoid floating-point inaccuracy, I've used an integer halve, which is a byte longer than a floating-point halve.)

I↨2υ

Output the encoded value converted from base 2.

Answer 18

Jelly, 14 bytes

×ばつ3‘$HḂ?’пḂṙ-Ḅ

Try it online!

How it works

×ばつ3‘$HḂ?’пḂṙ-Ḅ - Main link. Takes n on the left
 п - While loop, collecting each iteration i:
 ’ - Condition: i > 1
 ? - Body: If:
 Ḃ - Condition: Bit; i % 2
 $ - True×ばつ3 - 3i
 ‘ - 3i+1
 H - False: Halve
 Ḃ - Bit of each i
 ṙ- - Rotate the final 1 to the front
 Ḅ - Convert from binary

Answer 19

BQN, (削除) 36 (削除ここまで) 31 bytes

-5 bytes inspired by ovs

1⊸{aS1:a;(p×ばつw)Sp+x÷2÷6⋆p←2|x}

Anonymous function that takes an integer and returns its Collatz encoding. Try it at BQN online

Explanation

1⊸{aS1:a;(p×ばつw)Sp+x÷2÷6⋆p←2|x}
 { } Function of two arguments (right argument is the
 number, left argument calculates the answer):
 aS1: Given left argument a and right argument 1,
 a return a
 ; Otherwise,
 S call this function recursively
 with new right argument:
 2|x Current number mod 2
 p← Store that value in p (for parity)
 6⋆ 6 to that power (1 for even numbers, 6 for odd)
 2÷ 2 divided by that amount (2 or 1/3)
 x÷ Current number divided by that (x/2 or x*3)
 p+ Add p (x/2+0 or x*3+1)
 ( ) and new left argument:
 ×ばつw Current accumulator times 2
 p+ Plus p
1⊸ Call that function with a left argument of 1

Somewhat surprisingly, there seem to be no floating point errors from dividing by 3 until the numbers get too large to store as integers anyway.

• ovs: Separating the odd and even case seems to save a byte
• ovs: Or 35 bytes with the cases combined
• ovs: Ah sorry, It thought the URL was auto-updating like ATO. Here is an actual link for the first one. The other one is 1⊸{wS1:w;(k⊑6‿1÷ ̃k+3×x)S ̃w+w+k←2|x}
• DLosc: Ah, nice! Didn't think of assigning 2|x to a name. I played around with the second one and found a better formula that saved 4 more bytes. :D

Answer 20

Rust, (削除) 77 67 (削除ここまで) 61 bytes

-10 bytes, thanks @alephalpha.
-6 bytes, thanks @Juan Ignacio Díaz

|mut n|{let mut b=1;while n>1{b=2*b+n%2;n=[n/2,3*n+1][n%2]}b}

Try it online!

If overflows are not okay we can use (削除) 81 (削除ここまで) 74 (-6 bytes, thanks @Juan Ignacio Díaz) bytes instead and write

|mut n|{let mut b=1.;while n!=1{if n%2>0{b=2.*b+1.;n=3*n+1;}b*=2.;n/=2;}b}

Try it online!

which returns the value as a float, so it doesn't overflow for an input of 27. Instead it returns 4272797808638851700000000000000000, which is 137289440854955024 too small.

• alephalpha: -10 bytes.
• JSorngard: @alephalpha I'm a bit new to stack exchange, should I edit my answer with your code and cite it, or leave it for people to find in the comments?
• alephalpha: It's up to you. Usually I'll edit the answer and say something like "-n bytes thanks to @user".
• ceilingcat: 60 bytes and 69 bytes

Answer 21

PARI/GP, 47 bytes

f(n,i=1)=if(n<2,i,f(if(n%2,3*n+1,n/2),2*i+n%2))

Attempt This Online!

Answer 22

05AB1E, 17 bytes

[D#ÐÉi3*>ë;])ÉÁ2β

Try it online or verify all test cases.

Explanation:

[ # Loop indefinitely:
 D # Duplicate the current value
 # (which will be the implicit input in the first iteration)
 # # If it's equal to 1: stop the infinite loop
 Ð # Triplicate the current value
 Éi # Pop one, and it it's odd:
 3* # Multiply the value by 3
 > # And add 1
 ë # Else (it's even instead):
 ; # Halve it
] # Close the if-else statement and loop
 ) # Wrap all values on the stack into a list
 É # Check for each value whether it's odd
 Á # Rotate the list once towards the right
 2β # Convert it from a binary-list to an integer
 # (after which the result is output implicitly)

Answer 23

R, 58 bytes

f=function(n,o=1,m=n%%2)`if`(n>1,f((5*m+1)*n/2+m,2*o+m),o)

Try it online!

Recursive function.

---

R, 58 bytes

function(n){while(n>1){T=T*2+(m=n%%2)
n=(5*m+1)*n/2+m}
+T}

Try it online!

Non-recursive approach, same length.

Answer 24

Desmos, (削除) 83 (削除ここまで) 80 bytes

i->i+si+sk,n->(floor(n/2)+kn+k)(k+1)s
s=max(0,sign(n-1))
k=mod(n,2)
i=1
n=\ans_0

Try it on Desmos!

-3 bytes thanks to Aiden Chow

Answer 25

C, (削除) 75 (削除ここまで) 54 bytes

Edit: 54 bytes, credit to ceilingcat.

c(n,x){for(x=1;n>1;n=n%2?x++,n*3+1:n/2)x+=x;return x;}

Works with gcc and clang. Test main: main(){for(int i=1;i<16;i++) printf("%d\n",c(i));}

Takes and returns int16_t. Beware of the dreaded integer overflow.

81 chars, not conforming to requirements, but no overflow:

#define P putchar(4
c(n){P 9);for(;n>1;){if(n%2){n=n*3+1;P 9);}else{n/=2;P 8);}}}

Prints as binary to stdout.

Answer 26

Wolfram Language(Mathematica), 61 bytes

Try it online!

f[n_,i_:1]:=If[n<2,i,f[If[Mod[n,2]==1,3n+1,n/2],2i+Mod[n,2]]]

Answer 27

tinylisp 2, 62 bytes

(d E(\(N(A 1))(?(= N 1)A(E(?(o N)(+(* 3 N)1)(/ N 2))(+(o N)A A

Try It Online!

Ungolfed/explanation

Another port of my BQN answer.

(def encode ; Define encode
 (lambda ; as a lambda function
 (num (accum 1)) ; that takes a number and an accumulator that defaults to 1:
 (if (= num 1) ; If num is 1,
 accum ; return accum
 (encode ; Else, do a recursive call with these arguments:
 (if (odd? num) ; First argument: if num is odd,
 (+ (* 3 num) 1) ; 3 * num + 1
 (/ num 2)) ; else num / 2
 (+ (odd? num) ; Second argument: add 1 if num is odd, 0 otherwise
 accum ; to accum
 accum))))) ; and accum again--thus, 2 * accum + (num mod 2)

Answer 28

Bespoke, 325 bytes

from a value N in this sequence,assuming Collatz would be true
each of possible values do have some form of"codes"in some encoding form
starting this with one,we doubled each moment;when odd,we added singular one
creating bijection here of integers;conjecture requires this if true
although unproven whether one is a forced N

Calculates \$D = n \% 2\$, then changes the "encoded" result \$r\$ to \2ドルr + D\$ and the inputted number \$n\$ to \$\frac{6^D \times n}{2}\$ each iteration while \$n - 1\$ is nonzero.

Answer 29

MathGolf, 16 bytes

┴ò_■しかく_@<\_┴←¬]y░å

Try it online.

Unfortunately there seem to be some bugs in MathGolf with the !! and ä builtins, since this should have been possible in 12 bytes instead: ┴ô_■しかく!!<_┴←¬]ä..

Explanation:

┴ # Check if the (implicit) input is equal to 1
 ← # While false with pop,
 ò # execute the following 6 characters as inner code-block:
 _ # Duplicate the current value
 ■しかく # Pop the copy, and push its Collatz value
 _ # Duplicate that Collatz value
 @ # Triple-swap the top three values on the stack: a,b,b → b,a,b
 < # Pop the top two and push a<b
 \ # Swap the top two values
 _ # Duplicate the top value
 ┴ # Pop the copy, and check if it's equal to 1
 ¬ # Rotate the stack once, so this duplicated 1 is at the front
 ] # Wrap the entire stack into a list
 y # Join it together to a number
 ░ # Convert it to a string
 å # Convert it from a binary-string to an integer
 # (after which the entire stack is output implicitly)

Answer 30

Burlesque, 41 bytes

1{J2dv{2./}{3.*+.}IE}C~J1Fi.+1+]m{2.%}2ug

Try it online!

1 # Continuation takes last (1) value from stack
{
 J # Duplicate
 2dv # Divisible by two
 {2./} # Halve
 {3.*+.} # *3+1
 IE # If else
}C~ # Continue infinitely
J # Duplicate
1Fi # Find index of 1
.+ # Take that many
1+] # Prepend 1
m{2.%} # Map mod 2
2ug # Read as binary digits