Problem 52 - n倍しても同じ数が現れる

Scheme

英語の簡単なものから

Problem 52 - Project Euler

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

125874は2倍して、251748。なんと同じ数が現れる。同じように2,3,4,5,6倍しても同じ数が現れる数字を探せ。

という問題。

(define (number->list n . base)
  (letrec ((b (if (null? base) 10 (car base)))
           (iter (lambda (acc n)
                   (let ((q (quotient n b))
                         (m (cons (modulo n b) acc)))
                        (if (zero? q)
                            m
                            (iter m q))))))
          (iter '() n)))

(define (problem52 n)
  (letrec ((search (lambda (cmp x m)
                     (cond ((< x 2) #t)
                           ((null? (lset-xor eq?
                                             (number->list (* m x))
                                             cmp))
                            (search cmp (- x 1) m))
                           (else
                             #f))))
           (iter (lambda (m)
                   (if ((search (number->list m) n m) m)
                       (else
                         (iter (+ m 1)))))))
          (iter 1)))

(problem52 2) ; 10255
(problem52 3) ; 142857
(problem52 4) ; 142857
(problem52 5) ; 142857
(problem52 6) ; 142857

6倍しても同じ数が現れるので、最上位の桁は1に固定できると考えれば少し早くなるかも。


142857は、ダイヤル数と言うらしい。

ダイヤル数 - Wikipedia

なんか聞いたことあるな。

思い出した。

http://www.142857.com/

コレダ。