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.

## No comments:

Post a Comment