ホーム - Project Euler

Problem 36¶

Double-base Palindromes¶

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$ (2進) は10進でも2進でも回文数である.

100万未満で10進でも2進でも回文数になるような数の総和を求めよ.

(注: 先頭に0を含めて回文にすることは許されない.)

(import (scheme base)
        (gauche base)
        (scheme flonum))

(define (number-of-digit n base)
  (assume (exact-integer? n))
  (assume (<= 0 n))
  (assume (or (= base 2)
              (= base 10)))
  (if (zero? n)
    1
    (+ (floor->exact
         ((if (= base 2)
            fllog2
            fllog10)
          n))
       1)))

(define (palindrome? n base)
  (assume (exact-integer? n))
  (assume (<= 0 n))
  (assume (or (= base 2)
              (= base 10)))
  (let* ([dn (number-of-digit n base)]
         [loop-count (div dn 2)])
    (let loop ([index 0])
      (cond
        [(<= loop-count index) #t]
        [(= (div (mod n (expt base (+ 1 index)))
                 (expt base index))
            (div (mod n (expt base (- dn index)))
                 (expt base (- dn 1 index))))
         (loop (+ index 1))]
        [else #f]))))

(define answer-36
  (apply + 
         (filter (cut palindrome? <> 2)
                 (filter (cut palindrome? <> 10)
                         (iota 100_0000)))))

(format #t "36: ~d~%" answer-36)