extra/project-euler/134/134.factor

   1 ! Copyright (c) 2007 Samuel Tardieu.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: arrays kernel lists lists.lazy math.algebra math math.functions
   4     math.order math.primes.lists math.ranges project-euler.common sequences ;
   5 IN: project-euler.134
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=134
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! Consider the consecutive primes p1 = 19 and p2 = 23. It can be verified that
  13 ! 1219 is the smallest number such that the last digits are formed by p1 whilst
  14 ! also being divisible by p2.
  15
  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 digits
  18 ! are formed by p1 and n is divisible by p2. Let S be the smallest of these
  19 ! values of n.
  20
  21 ! Find S for every pair of consecutive primes with 5 p1 1000000.
  22
  23
  24 ! SOLUTION
  25 ! --------
  26
  27 ! Compute the smallest power of 10 greater than or equal to m
  28 : next-power-of-10 ( m -- n )
  29     10 swap log10 ceiling >integer ^ ; foldable
  30
  31 <PRIVATE
  32
  33 ! Compute S for a given pair (p1, p2) -- that is the smallest positive
  34 ! number such that X = p1 [npt] and X = 0 [p2] (npt being the smallest
  35 ! power of 10 above p1)
  36 : s ( p1 p2 -- s )
  37     over 0 2array rot next-power-of-10 rot 2array chinese-remainder ;
  38
  39 PRIVATE>
  40
  41 : euler134 ( -- answer )
  42     0 5 lprimes-from uncons swap [ 1000000 > ] luntil
  43     [ [ s + ] keep ] leach drop ;
  44
  45 ! [ euler134 ] 10 ave-time
  46 ! 933 ms ave run timen - 19.58 SD (10 trials)
  47
  48 MAIN: euler134