BrainFuck part 5 - Math sequences

DPAmar
2,312 views

Collatz sequence

Collatz sequence is defined by

• C(0) is a parameter
• C(n+1) =
• C(n)/2 if C(n) is even
• 3 * C(n) + 1 if odd

Though it has not been proved yet, the sequence is supposed to end up with ..., 4, 2, 1 and then loop 4, 2, 1, ...

Let's read an integer N and write the full Collatz sequence (comma separated) until 1 is reached

Let's start

• Memory: empty
• Cursor: first cell
• Input: a decimal number N

Process

• First, generate comma (code 44), to print it when needed
• Decrease N by 1
• while N is not null (i.e. original N is not 1)
• Increase N (regenerate it)
• Copy / print N and print comma
• Try to divide N by 2
• Decrease by N
• Set else flag
• If N not null : decrease by 2, clear else flag, update quotient
• Loop until N is not null
• Then, according to else flag
• unset : N was even, and quotient N/2 is our next value
• set : N was odd, N = 2k+1, quotient is k and next value is 3N+1 = 6k+4
• In this case, multiply k by 3 : 3k
• Then add 2: 3k + 2
• And multiply by 2 : 6k+4
• in all cases, we have our next value
• copy as new N and decrease by 1 (we loop on N-1)
• Loop
• Print 1 (the final element)

Code

>++++[-<+++++++++++>]                  ( 44 = 4 x 11)
<<<[->+>+<<]>>[-<<+>>]>]<<[-<+>],]      ** part 2 **
<-[                                    while N is not 1
+                                    regenerate N
[->+>+<<]>[-<+>]>[>>>>++++++++++<<   copy / print N
<<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<    ** part 2 **
]>]<<]>+[-<+>]>>>[-]>[-<<<<+>>>>]<    ** part 3 **
<<<]<[>++++++[<++++++++>-]<-.[-]<]    ** part 4 **
<<.>                                 print comma
[->+<[->->>+<<]                      try to divide by 2 with an else flag
>[-                                  N is null and flag is set: N is odd
>>[-<+++>]<                        compute 3k
++[->++<]                          then 3k plus 2 and finally 6k plus 4 which is 3N plus 1
]<<]                                 division loop
>>>[-<<<+>>>]<<<-                    move new N and decrease by one
]                                      loop
<+++++.                                print '1' (code 49, 44 plus 5)


Minified version

>++++[-<+++++++++++>]>,[>++++++[-<-------->]>+++++++++[-<<<[
->+>+<<]>>[-<<+>>]>]<<[-<+>],]<-[+[->+>+<<]>[-<+>]>[>>>>++++
++++++<<<<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]>+[-<+>]>>>[
-]>[-<<<<+>>>>]<<<<]<[>++++++[<++++++++>-]<-.[-]<]<<.>[->+<[
->->>+<<]>[->>[-<+++>]<++[->++<]]<<]>>>[-<<<+>>>]<<<-]<+++++.


Final state

• Memory: 49, 0, 0, 0
• Cursor: first cell