extra/project-euler/069/069.factor

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