## The 3n+1 Problem

Thursday, October 25, 2012

Yesterday, a lengthy blog post from the Racket community discussed the “3n+1” problem (also known as the Collatz conjecture):

Consider a positive number n. The cycle length of n is the number of times we repeat the following, until we reach n=1:

- If n is odd, then n = 3n+1
- If n is even, then n = n/2
For example, given n=22, we see the following sequence: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1. The cycle length of 22 is, therefore, 16, since it took 16 repetitions to get to 1.

Given a definition of cycle length of a number, here’s the rest of the problem: given any two numbers

`i`

and`j`

, compute the maximum cycle length over all numbers between`i`

and`j`

, inclusive.

### Solution

Solving this in Factor could start by defining a word to take a number and compute its next value in the cycle. Since this is an internal word, we won’t add the check for the end condition of n=1:

```
: next-cycle ( x -- y )
dup odd? [ 3 * 1 + ] [ 2 / ] if ;
```

Creating the “cycle sequence” for a given number can be done by:

```
: cycles ( n -- seq )
[ dup 1 > ] [ [ next-cycle ] keep ] produce swap suffix ;
```

We could always find the “cycle length” by calling `cycles length`

, but
a slightly faster way would not create an intermediate sequence:

```
: cycle-length ( n -- m )
1 [ over 1 > ] [ [ next-cycle ] [ 1 + ] bi* ] while nip ;
```

We can find the maximum cycle (number and it’s cycle length) for any given sequence of numbers:

```
: max-cycle ( seq -- elt )
[ dup cycle-length ] { } map>assoc [ second ] supremum-by ;
```

For convenience, we can make some helper words to find either the number and/or the maximum cycle length:

```
: max-cycle-value ( seq -- n ) max-cycle first ;
: max-cycle-length ( seq -- m ) max-cycle second ;
```

### Testing

Factor strives to be a concise language, some of which is natural for a concatenative style. You can see this in the simple approach to unit testing:.

```
{
{ 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 }
} [ 22 cycles ] unit-test
{ 1 } [ 1 cycle-length ] unit-test
{ 2 } [ 2 cycle-length ] unit-test
{ 6 } [ 5 cycle-length ] unit-test
{ 16 } [ 22 cycle-length ] unit-test
{ 20 } [ 1 10 [a..b] max-cycle-length ] unit-test
{ 125 } [ 100 200 [a..b] max-cycle-length ] unit-test
{ 89 } [ 201 210 [a..b] max-cycle-length ] unit-test
{ 174 } [ 900 1000 [a..b] max-cycle-length ] unit-test
```

### Performance

The original post discussed performance. Since many cycles have numbers in common, we could change our approach to a recursive one, with memoization:

```
MEMO: fast-cycle-length ( n -- m )
dup 1 > [ next-cycle fast-cycle-length 1 + ] [ drop 1 ] if ;
```

Indeed, this takes roughly 15-20% of the time that our previous approach took to compute the number of cycles for the numbers 1 to 100,000 with a cold cache.

### Main

Like the original solution, we can add a “main” to allow running from the command line:

```
: run-cycles ( -- )
[
[ blank? ] split-when harvest first2
[ string>number ] bi@ 2dup [a..b] max-cycle-length
"%s %s %s\n" printf
] each-line ;
MAIN: run-cycles
```

And using the original sample file, produce the same output:

```
$ cat sample-data.txt
1 10
100 200
201 210
900 1000
$ factor cycles.factor < sample-data.txt
1 10 20
100 200 125
201 210 89
900 1000 174
```

The code for this is available on my GitHub.