Solution to Project Euler problem 124

diff --git a/extra/project-euler/124/124-tests.factor b/extra/project-euler/124/124-tests.factor
new file mode 100644 (file)
index 0000000..cdbb5af
--- /dev/null
+++ b/extra/project-euler/124/124-tests.factor
@@ -0,0 +1,4 @@
+USING: project-euler.124 tools.test ;
+IN: project-euler.124.tests
+
+[ 21417 ] [ euler124 ] unit-test

diff --git a/extra/project-euler/124/124.factor b/extra/project-euler/124/124.factor
new file mode 100644 (file)
index 0000000..0f4d1ee
--- /dev/null
+++ b/extra/project-euler/124/124.factor
@@ -0,0 +1,63 @@
+! Copyright (c) 2009 Guillaume Nargeot.
+! See http://factorcode.org/license.txt for BSD license.
+USING: arrays kernel math.primes.factors
+math.ranges project-euler.common sequences sorting ;
+IN: project-euler.124
+
+! http://projecteuler.net/index.php?section=problems&id=124
+
+! DESCRIPTION
+! -----------
+
+! The radical of n, rad(n), is the product of distinct prime factors of n.
+! For example, 504 = 2^3 × 3^2 × 7, so rad(504) = 2 × 3 × 7 = 42.
+
+! If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n),
+! and sorting on n if the radical values are equal, we get:
+
+!   Unsorted          Sorted
+!   n  rad(n)       n  rad(n) k
+!   1    1          1    1    1
+!   2    2          2    2    2
+!   3    3          4    2    3
+!   4    2          8    2    4
+!   5    5          3    3    5
+!   6    6          9    3    6
+!   7    7          5    5    7
+!   8    2          6    6    8
+!   9    3          7    7    9
+!  10   10         10   10   10
+
+! Let E(k) be the kth element in the sorted n column; for example,
+! E(4) = 8 and E(6) = 9.
+
+! If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).
+
+
+! SOLUTION
+! --------
+
+<PRIVATE
+
+: rad ( n -- n )
+    unique-factors product ; inline
+
+: rads-upto ( n -- seq )
+    [0,b] [ dup rad 2array ] map ;
+
+: (euler124) ( -- seq )
+    100000 rads-upto sort-values ;
+
+PRIVATE>
+
+: euler124 ( -- answer )
+    10000 (euler124) nth first ;
+
+! [ euler124 ] 100 ave-time
+! 373 ms ave run time - 17.61 SD (100 trials)
+
+! TODO: instead of the brute-force method, making the rad
+! array in the way of the sieve of eratosthene would scale
+! better on bigger values.
+
+SOLUTION: euler124

diff --git a/extra/project-euler/project-euler.factor b/extra/project-euler/project-euler.factor
index f0e40674da0f7b887bcb2676aa01f502066dd9e4..eedf2272ba85a4ad367c77df4086b1704e0ab503 100644 (file)
--- a/extra/project-euler/project-euler.factor
+++ b/extra/project-euler/project-euler.factor
@@ -20,10 +20,10 @@ USING: definitions io io.files io.pathnames kernel math math.parser
     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.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.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