1 ! Copyright (c) 2007 Samuel Tardieu.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: arrays kernel math.algebra math math.functions math.primes.list
4 math.ranges sequences ;
7 ! http://projecteuler.net/index.php?section=problems&id=134
12 ! Consider the consecutive primes p1 = 19 and p2 = 23. It can be
13 ! verified that 1219 is the smallest number such that the last digits
14 ! are formed by p1 whilst also being divisible by p2.
16 ! In fact, with the exception of p1 = 3 and p2 = 5, for every pair of
17 ! consecutive primes, p2 p1, there exist values of n for which the last
18 ! digits are formed by p1 and n is divisible by p2. Let S be the
19 ! smallest of these values of n.
21 ! Find S for every pair of consecutive primes with 5 p1 1000000.
26 ! Compute the smallest power of 10 greater than m
27 : next-power-of-10 ( m -- n )
28 10 swap log 10 log / >integer [ 10 * ] times ; foldable
30 ! Compute S for a given pair (p1, p2) -- that is the smallest positive
31 ! number such that X = p1 [npt] and X = 0 [p2] (npt being the smallest
32 ! power of 10 above p1)
34 over 0 2array rot next-power-of-10 rot 2array chinese-remainder ;
36 : euler134 ( -- answer )
37 primes-under-million 2 tail dup 1 tail 1000003 add [ s ] 2map sum ;
39 ! [ euler134 ] 10 ave-time
40 ! 6743 ms run / 79 ms GC ave time - 10 trials