# 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
)
```