Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|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$<sup>st</sup> digit, $d_2$ be the $2$<sup>nd</sup> 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のパンデジタル数の総和を求めよ.

```scheme

(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)

```