extra/project-euler/070/070.factor

   1 ! Copyright (c) 2010 Aaron Schaefer. All rights reserved.
   2 ! The contents of this file are licensed under the Simplified BSD License
   3 ! A copy of the license is available at http://factorcode.org/license.txt
   4 USING: arrays combinators.short-circuit kernel math math.combinatorics
   5 math.functions math.primes project-euler.common sequences
   6 sequences.extras ;
   7 FROM: project-euler.common => permutations? ;
   8 IN: project-euler.070
   9
  10 ! http://projecteuler.net/index.php?section=problems&id=70
  11
  12 ! DESCRIPTION
  13 ! -----------
  14
  15 ! Euler's Totient function, φ(n) [sometimes called the phi function], is used
  16 ! to determine the number of positive numbers less than or equal to n which are
  17 ! relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less
  18 ! than nine and relatively prime to nine, φ(9)=6. The number 1 is considered to
  19 ! be relatively prime to every positive number, so φ(1)=1.
  20
  21 ! Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation
  22 ! of 79180.
  23
  24 ! Find the value of n, 1 < n < 10^(7), for which φ(n) is a permutation of n and
  25 ! the ratio n/φ(n) produces a minimum.
  26
  27
  28 ! SOLUTION
  29 ! --------
  30
  31 ! For n/φ(n) to be minimised, φ(n) must be as close to n as possible; that is,
  32 ! we want to maximise φ(n). The minimal solution for n/φ(n) would be if n was
  33 ! prime giving n/(n-1) but since n-1 never is a permutation of n it cannot be
  34 ! prime.
  35
  36 ! The next best thing would be if n only consisted of 2 prime factors close to
  37 ! (in this case) sqrt(10000000). Hence n = p1*p2 and we only need to search
  38 ! through a list of known prime pairs. In addition:
  39
  40 !     φ(p1*p2) = p1*p2*(1-1/p1)(1-1/p2) = (p1-1)(p2-1)
  41
  42 ! ...so we can compute φ(n) more efficiently.
  43
  44 <PRIVATE
  45
  46 ! NOTE: ±1000 is an arbitrary range
  47 : likely-prime-factors ( -- seq )
  48     7 10^ sqrt >integer 1000 [ - ] [ + ] 2bi primes-between ; inline
  49
  50 : n-and-phi ( seq -- seq' )
  51     ! ( seq  = { p1, p2 } -- seq' = { n, φ(n) } )
  52     [ product ] [ [ 1 - ] map product ] bi 2array ;
  53
  54 : fit-requirements? ( seq -- ? )
  55     first2 { [ drop 7 10^ < ] [ permutations? ] } 2&& ;
  56
  57 : minimum-ratio ( seq -- n )
  58     [ [ first2 / ] map arg-min ] keep nth first ;
  59
  60 PRIVATE>
  61
  62 : euler070 ( -- answer )
  63    likely-prime-factors 2 all-combinations [ n-and-phi ] map
  64    [ fit-requirements? ] filter minimum-ratio ;
  65
  66 ! [ euler070 ] 100 ave-time
  67 ! 379 ms ave run time - 1.15 SD (100 trials)
  68
  69 SOLUTION: euler070