Chapter 04

Problem 4: Largest palindrome product

aoi.iter
aoi.iter
2022.06.23に更新
このチャプターの目次

2022/06/21

https://projecteuler.net/problem=4

問題

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.

では, 3桁の数の積で表される回文数の最大値を求めよ.

考察

方針が2つある

  1. (* 999 999)以下の回文数を大きい順に生成し、それらのうち3桁の積で表現できる回文数を探す
  2. 999以下の数値の組み合わせの積の集合から回文数をフィルタし、その中からもっとも大きい数値を探す

1を採用する

解答

; https://projecteuler.net/problem=4
(use util.stream)

(define (divisible? n x)
  (zero? (mod n x)))

;; 回文数の生成
(define (make-palindrome src)
  (letrec ((make-pal-rec (lambda (ctx rest)
                            (if (zero? rest) ctx
                                (make-pal-rec (+ (mod rest 10) (* 10 ctx))
                                              (div rest 10))))))
           (make-pal-rec src src)))

(make-palindrome 123)
; => 123321

;; 回文数リストの生成
(define (generate-palindrome-list max-src min-src)
  (stream-map make-palindrome (stream-range max-src min-src -1)))

(stream->list (stream-take (generate-palindrome-list 999 100) 5))
; -> (999999 998899 997799 996699 995599)


;; 割り切れるか判定
(define (product? n max min)
  (cond ((< max min) #f)
        ((and (divisible? n max)
              (> (/ n max) min)
              (< (/ n max) max)) #t)
        (else (product? n (- max 1) min))))

(product? 15 10 1)
; => #t
(product? 15 10 4)
; => #f

;; 解答
(define (solve digit)
  (let ((max-src (- (expt 10 digit) 1))
        (min-src (expt 10 (- digit 1))))
    (stream-car
     (stream-filter (lambda (n) (product? n max-src min-src))
                    (generate-palindrome-list max-src min-src)))))

(solve 2)
; => 9009
(solve 3)
; => 906609

感想

N/A

参考資料

N/A