extra/project-euler/069/069.factor

   1 ! Copyright (c) 2009 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: combinators fry kernel math math.primes math.primes.factors math.ranges
   4     project-euler.common sequences ;
   5 IN: project-euler.069
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=69
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! Euler's Totient function, φ(n) [sometimes called the phi function], is used
  13 ! to determine the number of numbers less than n which are relatively prime to
  14 ! n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and
  15 ! relatively prime to nine, φ(9)=6.
  16
  17 !     +----+------------------+------+-----------+
  18 !     | n  | Relatively Prime | φ(n) | n / φ(n)  |
  19 !     +----+------------------+------+-----------+
  20 !     | 2  | 1                | 1    | 2         |
  21 !     | 3  | 1,2              | 2    | 1.5       |
  22 !     | 4  | 1,3              | 2    | 2         |
  23 !     | 5  | 1,2,3,4          | 4    | 1.25      |
  24 !     | 6  | 1,5              | 2    | 3         |
  25 !     | 7  | 1,2,3,4,5,6      | 6    | 1.1666... |
  26 !     | 8  | 1,3,5,7          | 4    | 2         |
  27 !     | 9  | 1,2,4,5,7,8      | 6    | 1.5       |
  28 !     | 10 | 1,3,7,9          | 4    | 2.5       |
  29 !     +----+------------------+------+-----------+
  30
  31 ! It can be seen that n = 6 produces a maximum n / φ(n) for n ≤ 10.
  32
  33 ! Find the value of n ≤ 1,000,000 for which n / φ(n) is a maximum.
  34
  35
  36 ! SOLUTION
  37 ! --------
  38
  39 ! Brute force
  40
  41 <PRIVATE
  42
  43 : totient-ratio ( n -- m )
  44     dup totient / ;
  45
  46 PRIVATE>
  47
  48 : euler069 ( -- answer )
  49     2 1000000 [a,b] [ totient-ratio ] map
  50     [ supremum ] keep index 2 + ;
  51
  52 ! [ euler069 ] 10 ave-time
  53 ! 25210 ms ave run time - 115.37 SD (10 trials)
  54
  55
  56 ! ALTERNATE SOLUTIONS
  57 ! -------------------
  58
  59 ! In order to obtain maximum n / φ(n), φ(n) needs to be low and n needs to be
  60 ! high. Hence we need a number that has the most factors. A number with the
  61 ! most unique factors would have fewer relatively prime.
  62
  63 <PRIVATE
  64
  65 : primorial ( n -- m )
  66     {
  67         { [ dup 0 = ] [ drop V{ 1 } ] }
  68         { [ dup 1 = ] [ drop V{ 2 } ] }
  69         [ nth-prime primes-upto ]
  70     } cond product ;
  71
  72 : primorial-upto ( limit -- m )
  73     1 swap '[ dup primorial _ <= ] [ 1 + dup primorial ] produce
  74     nip penultimate ;
  75
  76 PRIVATE>
  77
  78 : euler069a ( -- answer )
  79     1000000 primorial-upto ;
  80
  81 ! [ euler069a ] 100 ave-time
  82 ! 0 ms ave run time - 0.01 SD (100 trials)
  83
  84 SOLUTION: euler069a