1 ! Copyright (c) 2007, 2008 Aaron Schaefer.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel make math sequences sorting project-euler.common ;
6 ! http://projecteuler.net/index.php?section=problems&id=9
11 ! A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
14 ! For example, 3² + 4² = 9 + 16 = 25 = 5².
16 ! There exists exactly one Pythagorean triplet for which a + b + c = 1000.
17 ! Find the product abc.
23 ! Algorithm adapted from http://www.friesian.com/pythag.com
27 : next-pq ( p1 q1 -- p2 q2 )
28 ! p > q and both are odd integers
29 dup 1 = [ drop 2 + dup ] when 2 - ;
31 : abc ( p q -- triplet )
35 [ - 2 / , ] ! b = (p² - q²) / 2
36 [ + 2 / , ] 2bi ! c = (p² + q²) / 2
37 ] { } make natural-sort ;
39 : (ptriplet) ( target p q triplet -- target p q )
40 sum pickd = [ next-pq 2dup abc (ptriplet) ] unless ;
42 : ptriplet ( target -- triplet )
43 3 1 { 3 4 5 } (ptriplet) abc nip ;
47 : euler009 ( -- answer )
48 1000 ptriplet product ;
50 ! [ euler009 ] 100 ave-time
51 ! 1 ms ave run time - 0.73 SD (100 trials)