Collatz sequence

From Esolang
Jump to: navigation, search

The Collatz sequence, also called the Hailstone sequence, is a sequence of numbers relevant to the Collatz conjecture, which theorizes that any number using this algorithm will eventually be reduced to 1. The conjecture's truth is supported by calculations, but it hasn't yet been proved that no number can indefinitely stay above 1.

Formal definition

To get a Collatz sequence from a number, if it's even, divide it by two, and if it's odd, multiply it by three and add one. Continue the operation on the result of the previous operation until the number becomes 1.

Pseudocode Example

 function collatz(n)
 while n > 1
   show n
   if n is odd then
     set n = 3n + 1
   else
     set n = n / 2
   endif
 endwhile
 show n

Example of a Collatz sequence

Collatz sequence of 25:

25
76
38
19
58
29
88
44
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

See also

Collatz function

External resources

Collatz conjecture on Wikipedia