extra/project-euler/037/037.factor

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