extra/project-euler/052/052.factor

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