Essays/Collatz Conjecture

From J Wiki
Jump to: navigation, search

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/

Xkcd710.png



See also



Contributed by Roger Hui.