1 ! Copyright (c) 2008 Aaron Schaefer.
2 ! See https://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.functions math.primes
4 project-euler.common sequences ;
7 ! https://projecteuler.net/problem=26
12 ! A unit fraction contains 1 in the numerator. The decimal
13 ! representation of the unit fractions with denominators 2 to 10
26 ! Where 0.1(6) means 0.166666..., and has a 1-digit recurring
27 ! cycle. It can be seen that 1/7 has a 6-digit recurring cycle.
29 ! Find the value of d < 1000 for which 1/d contains the longest
30 ! recurring cycle in its decimal fraction part.
38 : source-026 ( -- seq )
39 999 primes-upto [ recip ] map ;
41 : (mult-order) ( n a m -- k )
42 3dup ^ swap mod 1 = [ 2nip ] [ 1 + (mult-order) ] if ;
46 : recurring-period? ( a/b -- ? )
47 denominator 10 coprime? ;
49 ! Multiplicative order a.k.a. modulo order
50 : mult-order ( a n -- k )
53 : period-length ( a/b -- n )
55 [ denominator 10 swap mult-order ] [ drop 0 ] if ;
59 : max-period ( seq -- elt n )
60 dup [ period-length ] map dup maximum
61 over index [ swap nth ] curry bi@ ;
65 : euler026 ( -- answer )
66 source-026 max-period drop denominator ;
68 ! [ euler026 ] 100 ave-time
69 ! 290 ms ave run time - 19.2 SD (100 trials)