1 ! Copyright (c) 2009 Guillaume Nargeot.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: arrays kernel math.primes.factors
4 math.ranges project-euler.common sequences sorting ;
7 ! http://projecteuler.net/index.php?section=problems&id=124
12 ! The radical of n, rad(n), is the product of distinct prime factors of n.
13 ! For example, 504 = 2^3 × 3^2 × 7, so rad(504) = 2 × 3 × 7 = 42.
15 ! If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n),
16 ! and sorting on n if the radical values are equal, we get:
31 ! Let E(k) be the kth element in the sorted n column; for example,
32 ! E(4) = 8 and E(6) = 9.
34 ! If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).
43 unique-factors product ; inline
45 : rads-upto ( n -- seq )
46 [0..b] [ dup rad 2array ] map ;
48 : (euler124) ( -- seq )
49 100000 rads-upto sort-values ;
53 : euler124 ( -- answer )
54 10000 (euler124) nth first ;
56 ! [ euler124 ] 100 ave-time
57 ! 373 ms ave run time - 17.61 SD (100 trials)
59 ! TODO: instead of the brute-force method, making the rad
60 ! array in the way of the sieve of eratosthene would scale
61 ! better on bigger values.