extra/project-euler/052/052.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: combinators.short-circuit kernel math math.functions
   4     project-euler.common sequences sorting grouping ;
   5 IN: project-euler.052
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=52
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! It can be seen that the number, 125874, and its double, 251748, contain
  13 ! exactly the same digits, but in a different order.
  14
  15 ! Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x,
  16 ! contain the same digits.
  17
  18
  19 ! SOLUTION
  20 ! --------
  21
  22 ! Analysis shows the number must be odd, divisible by 3, and larger than 123456
  23
  24 <PRIVATE
  25
  26 : map-nx ( n x -- seq )
  27     [ 1 + * ] with map ; inline
  28
  29 : all-same-digits? ( seq -- ? )
  30     [ number>digits natural-sort ] map all-equal? ;
  31
  32 : candidate? ( n -- ? )
  33     { [ odd? ] [ 3 divisor? ] } 1&& ;
  34
  35 : next-all-same ( x n -- n )
  36     dup candidate? [
  37         2dup swap map-nx all-same-digits?
  38         [ nip ] [ 1 + next-all-same ] if
  39     ] [
  40         1 + next-all-same
  41     ] if ;
  42
  43 PRIVATE>
  44
  45 : euler052 ( -- answer )
  46     6 123456 next-all-same ;
  47
  48 ! [ euler052 ] 100 ave-time
  49 ! 92 ms ave run time - 6.29 SD (100 trials)
  50
  51 SOLUTION: euler052