ホーム - Project Euler

Problem 43¶

Sub-string Divisibility¶

The number, $1406357289$, is a $0$ to $9$ pandigital number because it is made up of each of the digits $0$ to $9$ in some order, but it also has a rather interesting sub-string divisibility property.

Let $d_1$ be the $1$^st digit, $d_2$ be the $2$^nd digit, and so on. In this way, we note the following:

• $d_2d_3d_4=406$ is divisible by $2$
• $d_3d_4d_5=063$ is divisible by $3$
• $d_4d_5d_6=635$ is divisible by $5$
• $d_5d_6d_7=357$ is divisible by $7$
• $d_6d_7d_8=572$ is divisible by $11$
• $d_7d_8d_9=728$ is divisible by $13$
• $d_8d_9d_{10}=289$ is divisible by $17$

Find the sum of all $0$ to $9$ pandigital numbers with this property.

部分文字列被整除性¶

数1406357289は0から9のパンデジタル数である (0から9が1度ずつ現れるので). この数は部分文字列が面白い性質を持っている.

$d_1$を上位1桁目, $d_2$を上位2桁目の数とし, 以下順に$d_n$を定義する. この記法を用いると次のことが分かる.

• $d_2d_3d_4=406$ は 2 で割り切れる
• $d_3d_4d_5=063$ は 3 で割り切れる
• $d_4d_5d_6=635$ は 5 で割り切れる
• $d_5d_6d_7=357$ は 7 で割り切れる
• $d_6d_7d_8=572$ は 11 で割り切れる
• $d_7d_8d_9=728$ は 13 で割り切れる
• $d_8d_9d_{10}=289$ は 17 で割り切れる

このような性質をもつ0から9のパンデジタル数の総和を求めよ.

(import (scheme base)
        (gauche base))

(define pandigital-num-list
  (let loop ([index 1]
             [rest (iota 10)]
             [current 0]
             [lis '()])
    (let ([next-loop (^[fold-rest]
                       (fold-right (^[n lis]
                                     (loop (+ index 1)
                                           (delete n rest)
                                           (+ (* current 10)
                                              n)
                                           lis))
                                   lis
                                   fold-rest))])
      (cond
        [(null? rest)
         (cons current lis)]
        ; 先頭は 0 以外
        [(= index 1)
         (next-loop (iota 9 1))]
        ; 先頭から 4 桁目は偶数になる
        [(= index 4)
         (let ([rest-even (filter even? rest)])
           (if (null? rest-even)
             lis
             (next-loop rest-even)))]
        ; 先頭から 6 桁目は 0 または 5 になる
        [(= index 6)
         (let ([rest-5 (filter (^n (zero? (mod n 5)))
                               rest)])
           (if (null? rest-5)
             lis
             (next-loop rest-5)))]
        [else
          (next-loop rest)]))))

(define (match-num? num)
  (filter (^n
            (let ([d345 (div (mod n 100_000_000)
                             100_000)]
                  [d567 (div (mod n 1_000_000)
                             1_000)]
                  [d678 (div (mod n 100_000)
                             100)]
                  [d789 (div (mod n 10_000)
                             10)]
                  [d890 (mod n 1_000)])
              (and (zero? (mod d345 3))
                   (zero? (mod d567 7))
                   (zero? (mod d678 11))
                   (zero? (mod d789 13))
                   (zero? (mod d890 17)))))
          pandigital-num-list))

(define answer-43
  (apply + (match-num? pandigital-num-list)))

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