extra/project-euler/041/041.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math.combinatorics math.primes sequences project-euler.common ;
   4 IN: project-euler.041
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=41
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! We shall say that an n-digit number is pandigital if it makes use of all the
  12 ! digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is
  13 ! also prime.
  14
  15 ! What is the largest n-digit pandigital prime that exists?
  16
  17
  18 ! SOLUTION
  19 ! --------
  20
  21 ! Check 7-digit pandigitals because if the sum of the digits in any number add
  22 ! up to a multiple of three, then it is a multiple of three and can't be prime.
  23 ! I assumed there would be a 7-digit answer, but technically a higher 4-digit
  24 ! pandigital than the one given in the description was also possible.
  25
  26 !     1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
  27 !     1 + 2 + 3 + 4 + 5 + 6 + 7 + 8     = 36
  28 !     1 + 2 + 3 + 4 + 5 + 6 + 7         = 28  *** not divisible by 3 ***
  29 !     1 + 2 + 3 + 4 + 5 + 6             = 21
  30 !     1 + 2 + 3 + 4 + 5                 = 15
  31 !     1 + 2 + 3 + 4                     = 10  *** not divisible by 3 ***
  32
  33 : euler041 ( -- answer )
  34     { 7 6 5 4 3 2 1 } all-permutations
  35     [ digits>number ] map [ prime? ] find nip ;
  36
  37 ! [ euler041 ] 100 ave-time
  38 ! 64 ms ave run time - 4.22 SD (100 trials)
  39
  40 SOLUTION: euler041