Essays/Collatz Conjecture
Introduction
n is a positive integer. Define a sequence as follows: The first term is n . Let k be the current term.
- if k is even, the next term is k%2
- if k is odd, the next term is 1+3*k
Repeat until 1 is reached.
For example, the sequence starting at 9 is: 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 . Lothar Collatz made the conjecture in 1937 that for all positive integers n the sequence terminates at 1. The conjecture remains unproven.
The Collatz Conjecture is also known as the 3n + 1 conjecture or the Syracuse problem; the sequence is referred to as the Collatz sequence, hailstone sequence, or hailstone numbers.
The Collatz sequence can be implemented as follows:
collatz=: -:`(>:@(3&*))`1: @. (1&= + 2&|) collatz 9 28 collatz 28 14 collatz 1 1 collatz^:a: 9 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Sequence Lengths
The sequence lengths for all the integers less than y can be computed by keeping a list C of lengths found so far. In iteration i , we use collatz^:(i&<:)^:a: i to get the partial sequence from i to j where j is less than i and already in C , and update C using the partial sequence.
cn=: 3 : 0
C=. y{._1 1
for_i. i.y do.
if. 0=i{C do.
b=. y>j=. collatz^:(i&<:)^:a: i
C=. ((b#i.-#j)+(_1{j){C) (b#j)}C
end.
end.
)
cn 20
_1 1 2 8 3 6 9 17 4 20 7 15 10 10 18 18 5 13 21 21
The problem can also be solved by explicitly computing the Collatz sequence for each element of }.i.y , but cn is much more efficient:
_1, #@(collatz^:a:)"0 }.i.20 _1 1 2 8 3 6 9 17 4 20 7 15 10 10 18 18 5 13 21 21 6!:2 'cn 1e4' 0.320282 6!:2 '_1, #@(collatz^:a:)"0 }.i.1e4' 4.66107
A Vector Approach
The basic iteration collatz can be replaced by collatzv (which requires that y>1 ):
collatzv=: 3 : '<. (2|y)} 0 1 + 0.5 3 */y' collatzv i.20 0 4 1 10 2 16 3 22 4 28 5 34 6 40 7 46 8 52 9 58 collatz"0 i.20 0 1 1 10 2 16 3 22 4 28 5 34 6 40 7 46 8 52 9 58 1 + +/ *./\ 1 ~: collatzv^:(i.50) i.20 51 1 2 8 3 6 9 17 4 20 7 15 10 10 18 18 5 13 21 21 cn 20 _1 1 2 8 3 6 9 17 4 20 7 15 10 10 18 18 5 13 21 21
Moreover, the sequence length for 2*n is 1 + the sequence length for n . Thus:
cnv=: 3 : 0
f=. 2^m=. i. <.@(2&^.)&.<: y
m=. >:m
C=. 0 ,~ m f} y{._1
j=.i=. 3 + i.@<.&.-: y-2
while. #i do.
j=. collatzv j
b=. 0<(j<.y){C
p=. , f */ b#i
q=. , m +/ (b#j){C
m=. >:m
i=. (-.b)#i
j=. (-.b)#j
b=. y>p
C=. (b#q) (b#p)}C
end.
}:C
)
cnv is faster than cn but uses more space.
(cn -: cnv) 1e4 1 ts=: 6!:2 , 7!:2@] NB. time and space ts 'cn 1e4' 0.311987 147264 ts 'cnv 1e4' 0.0355665 700416
Collected Definitions
collatz=: -:`(>:@(3&*))`1: @. (1&= + 2&|)
cn=: 3 : 0
C=. y{._1 1
for_i. i.y do.
if. 0=i{C do.
b=. y>j=. collatz^:(i&<:)^:a: i
C=. ((b#i.-#j)+(_1{j){C) (b#j)}C
end.
end.
)
collatzv=: 3 : '<. (2|y)} 0 1 + 0.5 3 */y'
cnv=: 3 : 0
f=. 2^m=. i. <.@(2&^.)&.<: y
m=. >:m
C=. 0 ,~ m f} y{._1
j=.i=. 3 + i.@<.&.-: y-2
while. #i do.
j=. collatzv j
b=. 0<(j<.y){C
p=. , f */ b#i
q=. , m +/ (b#j){C
m=. >:m
i=. (-.b)#i
j=. (-.b)#j
b=. y>p
C=. (b#q) (b#p)}C
end.
}:C
)
From http://xkcd.com/710/
See also
Contributed by Roger Hui.