Problem 36 - 10進数でも2進数でも回文数

また翻訳してみる。

The decimal number, 585 = 1001001001_2 (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
(Please note that the palindromic number, in either base, may not include leading zeros.)

次の数、585 = 1001001001(2進数)はどちらの基数でも回文数となる。
100万未満の数で、10進、2進のどちらでも回文数となる数の総和を求めなさい。

こんな感じ？

まず、number->listを拡張して、基数変換に対応させる。

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

ちょっと便利になった。

回文判定は反転させればいいので、

(define (problem36 n)
  (define (palindromic? l) (equal? l (reverse l)))
  (cond ((< n 0) '())
        ((and (palindromic? (number->list n))
              (palindromic? (number->list n 2)))
         (cons n (problem36 (- n 2))))
        (else
          (problem36 (- n 2)))))

(problem36 (- 1000000 1)) ; (585585 73737 53835 53235 39993 32223 15351 9009 7447 717 585 313 99 33 9 7 5 3 1)
(apply + (problem36 (- 1000000 1))) ; 872187

こんな感じ。

010とはならないので、奇数じゃないと回文数にならない。
回文のみ回せばいいので、100万回やるのは無駄っぽい。

追記

ちょっとすっきりさせた。
奇数のみに絞って、倍速化。ループは50万回に。まだ遅い。