1 ! Copyright (c) 2007 Aaron Schaefer.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: combinators.short-circuit kernel make math math.functions math.ranges
4 sequences project-euler.common ;
7 ! http://projecteuler.net/index.php?section=problems&id=14
12 ! The following iterative sequence is defined for the set of positive integers:
14 ! n -> n / 2 (n is even)
15 ! n -> 3n + 1 (n is odd)
17 ! Using the rule above and starting with 13, we generate the following
20 ! 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
22 ! It can be seen that this sequence (starting at 13 and finishing at 1)
23 ! contains 10 terms. Although it has not been proved yet (Collatz Problem), it
24 ! is thought that all starting numbers finish at 1.
26 ! Which starting number, under one million, produces the longest chain?
28 ! NOTE: Once the chain starts the terms are allowed to go above one million.
38 : next-collatz ( n -- n )
39 dup even? [ 2 / ] [ 3 * 1 + ] if ;
43 : collatz ( n -- seq )
44 [ [ dup 1 > ] [ dup , next-collatz ] while , ] { } make ;
46 : euler014 ( -- answer )
47 1,000,000 [1..b] { } [ collatz longer ] reduce first ;
50 ! 52868 ms run / 483 ms GC time
58 : worth-calculating? ( n -- ? )
59 1 - 3 { [ divisor? ] [ / even? ] } 2&& ;
63 : euler014a ( -- answer )
64 500000 1000000 [a..b] { 1 } [
65 dup worth-calculating? [ collatz longer ] [ drop ] if
68 ! [ euler014a ] 10 ave-time
69 ! 4821 ms run / 41 ms GC time
71 ! TODO: try using memoization