1 USING: math math.functions math.primes
2 project-euler.common sequences sets ;
6 ! https://projecteuler.net/index.php?section=problems&id=87
11 ! The smallest number expressible as the sum of a prime square,
12 ! prime cube, and prime fourth power is 28. In fact, there are
13 ! exactly four numbers below fifty that can be expressed in such
16 ! 28 = 2^2 + 2^3 + 2^4
17 ! 33 = 3^2 + 2^3 + 2^4
18 ! 49 = 5^2 + 2^3 + 2^4
19 ! 47 = 2^2 + 3^3 + 2^4
21 ! How many numbers below fifty million can be expressed as the
22 ! sum of a prime square, prime cube, and prime fourth power?
26 :: prime-powers-less-than ( primes pow n -- prime-powers )
27 primes [ pow ^ ] map [ n <= ] filter ;
29 ! You may think to make a set of all possible sums of a prime
30 ! square and cube and then subtract prime fourths from numbers
31 ! ranging from 1 to 'n' to find this. As n grows large, this is
32 ! actually more inefficient!
34 ! Prime numbers grow ~ n / log n
36 ! Thus there are (n / log n)^(1/2) prime squares <= n,
37 ! (n / log n)^(1/3) prime cubes <= n,
38 ! and (n / log n)^(1/4) prime fourths <= n.
40 ! If we compute the cartesian product of these, this takes
41 ! O((n / log n)^(13/12)).
43 ! If we instead precompute sums of squares and cubes, and
44 ! iterate up to n, checking each fourth power against it, this
47 ! O(n * (n / log n)^(1/4)) = O(n^(5/4)/(log n)^(1/4)) >> O((n / log n)^(13/12))
49 ! When n = 50,000,000, the first equation is approximately 10
50 ! million and the second is approximately 2 billion.
52 :: prime-triples ( n -- answer )
53 n sqrt primes-upto :> primes
54 primes 2 n prime-powers-less-than :> primes^2
55 primes 3 n prime-powers-less-than :> primes^3
56 primes 4 n prime-powers-less-than :> primes^4
57 primes^2 primes^3 [ + ] cartesian-map concat
58 primes^4 [ + ] cartesian-map concat
59 [ n <= ] filter members length ;
63 :: euler087 ( -- answer )
64 50,000,000 prime-triples ;