extra/project-euler/026/026.factor

   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 ;
   5 IN: project-euler.026
   6
   7 ! https://projecteuler.net/problem=26
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! A unit fraction contains 1 in the numerator. The decimal
  13 ! representation of the unit fractions with denominators 2 to 10
  14 ! are given:
  15
  16 !     1/2  =  0.5
  17 !     1/3  =  0.(3)
  18 !     1/4  =  0.25
  19 !     1/5  =  0.2
  20 !     1/6  =  0.1(6)
  21 !     1/7  =  0.(142857)
  22 !     1/8  =  0.125
  23 !     1/9  =  0.(1)
  24 !     1/10 =  0.1
  25
  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.
  28
  29 ! Find the value of d < 1000 for which 1/d contains the longest
  30 ! recurring cycle in its decimal fraction part.
  31
  32
  33 ! SOLUTION
  34 ! --------
  35
  36 <PRIVATE
  37
  38 : source-026 ( -- seq )
  39     999 primes-upto [ recip ] map ;
  40
  41 : (mult-order) ( n a m -- k )
  42     3dup ^ swap mod 1 = [ 2nip ] [ 1 + (mult-order) ] if ;
  43
  44 PRIVATE>
  45
  46 : recurring-period? ( a/b -- ? )
  47     denominator 10 coprime? ;
  48
  49 ! Multiplicative order a.k.a. modulo order
  50 : mult-order ( a n -- k )
  51     swap 1 (mult-order) ;
  52
  53 : period-length ( a/b -- n )
  54     dup recurring-period?
  55     [ 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