# BrainFuck part 5 - Math sequences

DPAmar
2,341 views

## Welcome!

playgrounds if you didn't already !

The goal of this playground is to play with maths, again, more exactly with some famous math sequences.

A prime number is a number that allows only 2 distinct divisors: 1 and itself. First prime numbers are 2, 3, 5, 7, 11 ...

Computing all prime numbers up to a limit can be implemented using a sieve :

• Generate an array of all integers from 2 up to the limit
• Go to the first non-null item in the array
• This number N is prime
• Then, reset array items every N cells starting from this one

Example:

• 2 is prime
• remove 4, 6, 8, ... and all multiple of 2
• 3 is a prime
• remove 6 (again), 9, 12, ... and all multiples of 3
• 4 is null (reset by 2)
• 5 is prime
• remove 10 (again), 15 (again), 20 (again), 25, ...
• 6 is null
• 7 is prime
• ...

Let's print all prime numbers (<256 of course), in a comma separated list

## Let's start

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

## Process

• First, generate comma (code 44), to print it when needed
• Generate an array from 2 to max value
• Values can be null, it's a 2-cell-long array
• _Note : we will use a structure [value, flag] instead of [flag, value], code is a bit shorter_a
• method
• decrease empty cell by one to have max value
• set flag on the right to 1
• while value cell is not null, copy after the flag, then set the flag and repeat
• This generates a set of cells [value, flag], from 255 to 1 : remove 2 extra cells (one array item) at the end
• Note: the array is reversed... but it's not a big deal
• Go to last array item
• For each array item
• If value is not null : prime
• Copy and print
• Print comma
• Copy again as counter
• Move cells on the left and decrease counter
• When counter is null, N is a factor of current cell : reset cell and recreate counter, then continue
• loop

## Code

>++++[-<+++++++++++>]      ( 44 = 4x11 )
>-                         generate max value
[                          while current value is not null
+                        set flag
>-                       decrease next value
]                          loop
<-<-<                      remove last value (1) and go to first cell (2; on flag)
[                          while current cell is an array item
-                        reset flag (cell is being processed but not part of the array anymore)
<[                       if number is not null : prime
[->>+>>+<<<<]>>>>      copy (note leave the ex flag cell empty to ease array browsing)
[>>>>++++++++++<<<<[-  print N as decimal number
>+>>+>-[<-]<[->>+<<<<   ** part 2 **
[->>>+<<<]>]<<]>+[-<+   ** part 3 **
>]>>>[-]>[-<<<<+>>>>]   ** part 4 **
<<<<]<[>++++++[<+++++   ** part 5 **
+++>-]<-.[-]<]          ** part 6 **
<<<<[<<]<.             print comma
>>>[>>]                go back to end of array
>[->+>>+<<<]>[-<+>]<   copy value as cell counter
<<<[                   go to last array cell
-<[->>+<<]>>>+       move to right (reset flag then move value then set new flag)
[>>]+                go to counter and set else flag
<-[>-]>[             decrease counter; if null (else flag still set)
-                  reset else flag
<<[<<]>            go to last moved value
[-]                reset value (multiple of N)
>[>>]>>            go back to end of array and then counter saved copy
[-<+<<+>>>]<[->+<] create a new counter
]                    end if (position: just before counter saved copy; the last non empty cell in memory)
<<<[<<]<<]             process next cells
>>>>[-<[-<<+>>]<+>>>>] Move back all array cells
>>[-]<<<[-]            reset counter remainder and counter copy
<<]                      end if
<]                         loop


## Minified version

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


## Final state

• Memory: 44, 0, 0, 0
• Cursor: on 2nd cell
• Input: empty
• Output: All prime numbers, base 10, comma separated

## Test program

Let's replace the "-" that generates the max value by a "," that reads a char

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


This will write prime numbers up to a given limit (ex : 'x' for primes up to 120)   