extra/project-euler/041/041.factor

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