extra/project-euler/124/124.factor

   1 ! Copyright (c) 2009 Guillaume Nargeot.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: arrays kernel math.primes.factors
   4 ranges project-euler.common sequences sorting ;
   5 IN: project-euler.124
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=124
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  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.
  14
  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:
  17
  18 !   Unsorted          Sorted
  19 !   n  rad(n)       n  rad(n) k
  20 !   1    1          1    1    1
  21 !   2    2          2    2    2
  22 !   3    3          4    2    3
  23 !   4    2          8    2    4
  24 !   5    5          3    3    5
  25 !   6    6          9    3    6
  26 !   7    7          5    5    7
  27 !   8    2          6    6    8
  28 !   9    3          7    7    9
  29 !  10   10         10   10   10
  30
  31 ! Let E(k) be the kth element in the sorted n column; for example,
  32 ! E(4) = 8 and E(6) = 9.
  33
  34 ! If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).
  35
  36
  37 ! SOLUTION
  38 ! --------
  39
  40 <PRIVATE
  41
  42 : rad ( n -- n )
  43     unique-factors product ; inline
  44
  45 : rads-upto ( n -- seq )
  46     [0..b] [ dup rad 2array ] map ;
  47
  48 : (euler124) ( -- seq )
  49     100000 rads-upto sort-values ;
  50
  51 PRIVATE>
  52
  53 : euler124 ( -- answer )
  54     10000 (euler124) nth first ;
  55
  56 ! [ euler124 ] 100 ave-time
  57 ! 373 ms ave run time - 17.61 SD (100 trials)
  58
  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.
  62
  63 SOLUTION: euler124