From: Guillaume Nargeot <killy971@gmail.com>
Date: Tue, 22 Sep 2009 02:16:04 +0000 (+0900)
Subject: Solution to Project Euler problem 72
X-Git-Tag: 0.97~5496^2~2^2~2
X-Git-Url: https://gitweb.factorcode.org/gitweb.cgi?p=factor.git;a=commitdiff_plain;h=941fc66a43310d5892133b8c054b3e2dbbb6c446

Solution to Project Euler problem 72
---

diff --git a/extra/project-euler/072/072-tests.factor b/extra/project-euler/072/072-tests.factor
new file mode 100644
index 0000000000..80a8949d0d
--- /dev/null
+++ b/extra/project-euler/072/072-tests.factor
@@ -0,0 +1,4 @@
+USING: project-euler.072 tools.test ;
+IN: project-euler.072.tests
+
+[ 303963552391 ] [ euler072 ] unit-test
diff --git a/extra/project-euler/072/072.factor b/extra/project-euler/072/072.factor
new file mode 100644
index 0000000000..de6312f2a7
--- /dev/null
+++ b/extra/project-euler/072/072.factor
@@ -0,0 +1,38 @@
+! Copyright (c) 2009 Guillaume Nargeot.
+! See http://factorcode.org/license.txt for BSD license.
+USING: kernel math math.primes.factors math.ranges
+project-euler.common sequences ;
+IN: project-euler.072
+
+! http://projecteuler.net/index.php?section=problems&id=072
+
+! DESCRIPTION
+! -----------
+
+! Consider the fraction, n/d, where n and d are positive integers.
+! If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
+
+! If we list the set of reduced proper fractions for d ≤ 8 in ascending order
+! of size, we get:
+
+! 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3,
+! 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
+
+! It can be seen that there are 21 elements in this set.
+
+! How many elements would be contained in the set of reduced proper fractions
+! for d ≤ 1,000,000?
+
+
+! SOLUTION
+! --------
+
+! The answer can be found by adding totient(n) for 2 ≤ n ≤ 1e6
+
+: euler072 ( -- answer )
+    2 1000000 [a,b] [ totient ] [ + ] map-reduce ;
+
+! [ euler072 ] 100 ave-time
+! 5274 ms ave run time - 102.7 SD (100 trials)
+
+SOLUTION: euler072
diff --git a/extra/project-euler/project-euler.factor b/extra/project-euler/project-euler.factor
index eedf2272ba..bc61d884f5 100644
--- a/extra/project-euler/project-euler.factor
+++ b/extra/project-euler/project-euler.factor
@@ -17,13 +17,13 @@ USING: definitions io io.files io.pathnames kernel math math.parser
     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.069
-    project-euler.071 project-euler.073 project-euler.075 project-euler.076
-    project-euler.079 project-euler.085 project-euler.092 project-euler.097
-    project-euler.099 project-euler.100 project-euler.102 project-euler.112
-    project-euler.116 project-euler.117 project-euler.124 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.071 project-euler.072 project-euler.073 project-euler.075
+    project-euler.076 project-euler.079 project-euler.085 project-euler.092
+    project-euler.097 project-euler.099 project-euler.100 project-euler.102
+    project-euler.112 project-euler.116 project-euler.117 project-euler.124
+    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