extra/project-euler/026/026.factor

   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 ;
   4 IN: project-euler.026
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=26
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! A unit fraction contains 1 in the numerator. The decimal representation of
  12 ! the unit fractions with denominators 2 to 10 are given:
  13
  14 !     1/2  =  0.5
  15 !     1/3  =  0.(3)
  16 !     1/4  =  0.25
  17 !     1/5  =  0.2
  18 !     1/6  =  0.1(6)
  19 !     1/7  =  0.(142857)
  20 !     1/8  =  0.125
  21 !     1/9  =  0.(1)
  22 !     1/10 =  0.1
  23
  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.
  26
  27 ! Find the value of d < 1000 for which 1/d contains the longest recurring cycle
  28 ! in its decimal fraction part.
  29
  30
  31 ! SOLUTION
  32 ! --------
  33
  34 <PRIVATE
  35
  36 : source-026 ( -- seq )
  37     1 1000 (a,b) [ prime? ] filter [ 1 swap / ] map ;
  38
  39 : (mult-order) ( n a m -- k )
  40     3dup ^ swap mod 1 = [ 2nip ] [ 1 + (mult-order) ] if ;
  41
  42 PRIVATE>
  43
  44 : coprime? ( m n -- ? )
  45     gcd 1 = nip ;
  46
  47 : recurring-period? ( a/b -- ? )
  48     denominator 10 coprime? ;
  49
  50 ! Multiplicative order a.k.a. modulo order
  51 : mult-order ( a n -- k )
  52     swap 1 (mult-order) ;
  53
  54 : period-length ( a/b -- n )
  55     dup recurring-period? [ denominator 10 swap mult-order ] [ drop 0 ] if ;
  56
  57 <PRIVATE
  58
  59 : max-period ( seq -- elt n )
  60     dup [ period-length ] map dup supremum
  61     over index [ swap nth ] curry bi@ ;
  62
  63 PRIVATE>
  64
  65 : euler026 ( -- answer )
  66     source-026 max-period drop denominator ;
  67
  68 ! [ euler026 ] 100 ave-time
  69 ! 290 ms ave run time - 19.2 SD (100 trials)
  70
  71 SOLUTION: euler026