extra/project-euler/037/037.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.parser math.primes sequences project-euler.common ;
   4 IN: project-euler.037
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=37
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! The number 3797 has an interesting property. Being prime itself, it is
  12 ! possible to continuously remove digits from left to right, and remain prime
  13 ! at each stage: 3797, 797, 97, and 7. Similarly we can work from right to
  14 ! left: 3797, 379, 37, and 3.
  15
  16 ! Find the sum of the only eleven primes that are both truncatable from left to
  17 ! right and right to left.
  18
  19 ! NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
  20
  21
  22 ! SOLUTION
  23 ! --------
  24
  25 <PRIVATE
  26
  27 : r-trunc? ( n -- ? )
  28     10 /i dup 0 > [
  29         dup prime? [ r-trunc? ] [ drop f ] if
  30     ] [
  31         drop t
  32     ] if ;
  33
  34 : reverse-digits ( n -- m )
  35     number>string reverse string>number ;
  36
  37 : l-trunc? ( n -- ? )
  38     reverse-digits 10 /i reverse-digits dup 0 > [
  39         dup prime? [ l-trunc? ] [ drop f ] if
  40     ] [
  41         drop t
  42     ] if ;
  43
  44 PRIVATE>
  45
  46 : euler037 ( -- answer )
  47     23 1000000 primes-between [ r-trunc? ] filter [ l-trunc? ] filter sum ;
  48
  49 ! [ euler037 ] 100 ave-time
  50 ! 130 ms ave run time - 6.27 SD (100 trials)
  51
  52 SOLUTION: euler037