1 ! Copyright (c) 2008 Aaron Schaefer.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.functions math.primes math.ranges sequences project-euler.common ;
6 ! http://projecteuler.net/index.php?section=problems&id=26
11 ! A unit fraction contains 1 in the numerator. The decimal representation of
12 ! the unit fractions with denominators 2 to 10 are given:
24 ! Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be
25 ! seen that 1/7 has a 6-digit recurring cycle.
27 ! Find the value of d < 1000 for which 1/d contains the longest recurring cycle
28 ! in its decimal fraction part.
36 : source-026 ( -- seq )
37 999 primes-upto [ recip ] map ;
39 : (mult-order) ( n a m -- k )
40 3dup ^ swap mod 1 = [ 2nip ] [ 1 + (mult-order) ] if ;
44 : recurring-period? ( a/b -- ? )
45 denominator 10 coprime? ;
47 ! Multiplicative order a.k.a. modulo order
48 : mult-order ( a n -- k )
51 : period-length ( a/b -- n )
52 dup recurring-period? [ denominator 10 swap mult-order ] [ drop 0 ] if ;
56 : max-period ( seq -- elt n )
57 dup [ period-length ] map dup supremum
58 over index [ swap nth ] curry bi@ ;
62 : euler026 ( -- answer )
63 source-026 max-period drop denominator ;
65 ! [ euler026 ] 100 ave-time
66 ! 290 ms ave run time - 19.2 SD (100 trials)