Back
Close

BrainFuck part 5 - Math sequences

DPAmar
1,679 views
Previous: Pascal's triangle

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
  • Then, read integer N
  • 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)
>,[>++++++[-<-------->]>+++++++++[-    read an integer
<<<[->+>+<<]>>[-<<+>>]>]<<[-<+>],]      ** 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
  • Input: read (empty)
  • Output: Collatz sequence, start from N, comma separated

Note: again, this is a valid sequence, modulo 256. And it does not only means that input needs to be less than 256, but that any item within sequence must be too.

Ex:

  • any odd number from 87 leads to a value greater than 256
  • any even number that doubles an odd value from 87 (i.e. all the 4n+2 with n >= 44) fails as well
  • ...
  • even worse : 85 is odd, next value is 256 = 0 in our model, but 0 is an unexpected value ==> it fails and displays comma in an infinite loop...
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants