! SOLUTION
! --------
-: nth-prime ( n -- n )
- 1- lprimes lnth ;
-
: euler007 ( -- answer )
10001 nth-prime ;
--- /dev/null
+USING: project-euler.069 tools.test ;
+
+{ 510510 } [ euler069 ] unit-test
+{ 510510 } [ euler069a ] unit-test
--- /dev/null
+! Copyright (c) 2009 Aaron Schaefer.
+! See http://factorcode.org/license.txt for BSD license.
+USING: combinators fry kernel math math.primes math.primes.factors math.ranges
+ project-euler.common sequences ;
+IN: project-euler.069
+
+! http://projecteuler.net/index.php?section=problems&id=69
+
+! DESCRIPTION
+! -----------
+
+! Euler's Totient function, φ(n) [sometimes called the phi function], is used
+! to determine the number of numbers less than n which are relatively prime to
+! n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and
+! relatively prime to nine, φ(9)=6.
+
+! +----+------------------+------+-----------+
+! | n | Relatively Prime | φ(n) | n / φ(n) |
+! +----+------------------+------+-----------+
+! | 2 | 1 | 1 | 2 |
+! | 3 | 1,2 | 2 | 1.5 |
+! | 4 | 1,3 | 2 | 2 |
+! | 5 | 1,2,3,4 | 4 | 1.25 |
+! | 6 | 1,5 | 2 | 3 |
+! | 7 | 1,2,3,4,5,6 | 6 | 1.1666... |
+! | 8 | 1,3,5,7 | 4 | 2 |
+! | 9 | 1,2,4,5,7,8 | 6 | 1.5 |
+! | 10 | 1,3,7,9 | 4 | 2.5 |
+! +----+------------------+------+-----------+
+
+! It can be seen that n = 6 produces a maximum n / φ(n) for n ≤ 10.
+
+! Find the value of n ≤ 1,000,000 for which n / φ(n) is a maximum.
+
+
+! SOLUTION
+! --------
+
+! Brute force
+
+<PRIVATE
+
+: totient-ratio ( n -- m )
+ dup totient / ;
+
+PRIVATE>
+
+: euler069 ( -- answer )
+ 2 1000000 [a,b] [ totient-ratio ] map
+ [ supremum ] keep index 2 + ;
+
+! [ euler069 ] 10 ave-time
+! 25210 ms ave run time - 115.37 SD (10 trials)
+
+
+! ALTERNATE SOLUTIONS
+! -------------------
+
+! In order to obtain maximum n / φ(n), φ(n) needs to be low and n needs to be
+! high. Hence we need a number that has the most factors. A number with the
+! most unique factors would have fewer relatively prime.
+
+<PRIVATE
+
+: primorial ( n -- m )
+ {
+ { [ dup 0 = ] [ drop V{ 1 } ] }
+ { [ dup 1 = ] [ drop V{ 2 } ] }
+ [ nth-prime primes-upto ]
+ } cond product ;
+
+: (primorial-upto) ( count limit -- m )
+ '[ dup primorial _ <= ] [ 1+ dup primorial ] produce
+ nip penultimate ;
+
+: primorial-upto ( limit -- m )
+ 1 swap (primorial-upto) ;
+
+PRIVATE>
+
+: euler069a ( -- answer )
+ 1000000 primorial-upto ;
+
+! [ euler069a ] 100 ave-time
+! 0 ms ave run time - 0.01 SD (100 trials)
+
+SOLUTION: euler069a
! repeatedly until the denominator is as close to 1000000 as possible without
! going over.
-<PRIVATE
-
-: penultimate ( seq -- elt )
- dup length 2 - swap nth ;
-
-PRIVATE>
-
: euler071 ( -- answer )
2/5 [ dup denominator 1000000 <= ] [ 3/7 mediant dup ] produce
nip penultimate numerator ;
-! Copyright (c) 2007-2008 Aaron Schaefer.
+! Copyright (c) 2007-2009 Aaron Schaefer.
! See http://factorcode.org/license.txt for BSD license.
-USING: arrays kernel make math math.functions math.matrices math.miller-rabin
- math.order math.parser math.primes.factors math.ranges math.ratios
- sequences sorting strings unicode.case parser accessors vocabs.parser
- namespaces vocabs words quotations prettyprint ;
+USING: accessors arrays kernel lists make math math.functions math.matrices
+ math.miller-rabin math.order math.parser math.primes.factors
+ math.primes.lists math.ranges math.ratios namespaces parser prettyprint
+ quotations sequences sorting strings unicode.case vocabs vocabs.parser
+ words ;
IN: project-euler.common
! A collection of words used by more than one Project Euler solution
! log10 - #25, #134
! max-path - #18, #67
! mediant - #71, #73
+! nth-prime - #7, #69
! nth-triangle - #12, #42
! number>digits - #16, #20, #30, #34, #35, #38, #43, #52, #55, #56, #92
! palindrome? - #4, #36, #55
! pandigital? - #32, #38
! pentagonal? - #44, #45
+! penultimate - #69, #71
! propagate-all - #18, #67
! sum-proper-divisors - #21
! tau* - #12
: number-length ( n -- m )
log10 floor 1+ >integer ;
+: nth-prime ( n -- n )
+ 1- lprimes lnth ;
+
: nth-triangle ( n -- n )
dup 1+ * 2 / ;
: pentagonal? ( n -- ? )
dup 0 > [ 24 * 1+ sqrt 1+ 6 / 1 mod zero? ] [ drop f ] if ;
+: penultimate ( seq -- elt )
+ dup length 2 - swap nth ;
+
! Not strictly needed, but it is nice to be able to dump the triangle after the
! propagation
: propagate-all ( triangle -- new-triangle )
-! Copyright (c) 2007, 2008, 2009 Aaron Schaefer, Samuel Tardieu.
+! Copyright (c) 2007-2009 Aaron Schaefer, Samuel Tardieu.
! See http://factorcode.org/license.txt for BSD license.
USING: definitions io io.files io.pathnames kernel math math.parser
prettyprint project-euler.ave-time sequences vocabs vocabs.loader
project-euler.045 project-euler.046 project-euler.047 project-euler.048
project-euler.049 project-euler.052 project-euler.053 project-euler.054
project-euler.055 project-euler.056 project-euler.057 project-euler.058
- project-euler.059 project-euler.063 project-euler.067 project-euler.071
- project-euler.073 project-euler.075 project-euler.076 project-euler.079
- project-euler.092 project-euler.097 project-euler.099 project-euler.100
- project-euler.116 project-euler.117 project-euler.134 project-euler.148
- project-euler.150 project-euler.151 project-euler.164 project-euler.169
- project-euler.173 project-euler.175 project-euler.186 project-euler.190
- project-euler.203 project-euler.215 ;
+ project-euler.059 project-euler.063 project-euler.067 project-euler.069
+ project-euler.071 project-euler.073 project-euler.075 project-euler.076
+ project-euler.079 project-euler.092 project-euler.097 project-euler.099
+ project-euler.100 project-euler.116 project-euler.117 project-euler.134
+ project-euler.148 project-euler.150 project-euler.151 project-euler.164
+ project-euler.169 project-euler.173 project-euler.175 project-euler.186
+ project-euler.190 project-euler.203 project-euler.215 ;
IN: project-euler
<PRIVATE
projects / factor.git / commitdiff