Problem 38 » 履歴 » バージョン 1
Noppi, 2024/01/15 02:14
| 1 | 1 | Noppi | [ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]] |
|---|---|---|---|
| 2 | # [[Problem 38]] |
||
| 3 | |||
| 4 | ## Pandigital Multiples |
||
| 5 | <p>Take the number $192$ and multiply it by each of $1$, $2$, and $3$:</p> |
||
| 6 | \begin{align} |
||
| 7 | 192 \times 1 &= 192\\ |
||
| 8 | 192 \times 2 &= 384\\ |
||
| 9 | 192 \times 3 &= 576 |
||
| 10 | \end{align} |
||
| 11 | |||
| 12 | By concatenating each product we get the $1$ to $9$ pandigital, $192384576$. We will call $192384576$ the concatenated product of $192$ and $(1,2,3)$. |
||
| 13 | |||
| 14 | The same can be achieved by starting with $9$ and multiplying by $1$, $2$, $3$, $4$, and $5$, giving the pandigital, $918273645$, which is the concatenated product of $9$ and $(1,2,3,4,5)$. |
||
| 15 | |||
| 16 | What is the largest $1$ to $9$ pandigital $9$-digit number that can be formed as the concatenated product of an integer with $(1,2, \dots, n)$ where $n \gt 1$? |
||
| 17 | |||
| 18 | ## パンデジタル倍数 |
||
| 19 | 192 に 1, 2, 3 を掛けてみよう. |
||
| 20 | |||
| 21 | > 192 × 1 = 192 |
||
| 22 | > 192 × 2 = 384 |
||
| 23 | > 192 × 3 = 576 |
||
| 24 | |||
| 25 | 積を連結することで1から9の パンデジタル数 192384576 が得られる. 192384576 を 192 と (1,2,3) の連結積と呼ぶ. |
||
| 26 | |||
| 27 | 同じようにして, 9 を 1,2,3,4,5 と掛け連結することでパンデジタル数 918273645 が得られる. これは 9 と (1,2,3,4,5) との連結積である. |
||
| 28 | |||
| 29 | 整数と (1,2,...,n) (n > 1) との連結積として得られる9桁のパンデジタル数の中で最大のものはいくつか? |
||
| 30 | |||
| 31 | ```scheme |
||
| 32 | (import (scheme base) |
||
| 33 | (gauche base)) |
||
| 34 | |||
| 35 | (define (valid-num? n) |
||
| 36 | (assume (exact-integer? n)) |
||
| 37 | (assume (<= 236 n 362)) |
||
| 38 | (let ([table (make-vector 10 #f)]) |
||
| 39 | (set! (vector-ref table 0) #t) |
||
| 40 | (set! (vector-ref table 1) #t) |
||
| 41 | (set! (vector-ref table 8) #t) |
||
| 42 | (set! (vector-ref table 9) #t) |
||
| 43 | (let loop ([rest n]) |
||
| 44 | (if (zero? rest) |
||
| 45 | #t |
||
| 46 | (let ([check-n (mod rest 10)] |
||
| 47 | [rest (div rest 10)]) |
||
| 48 | (cond |
||
| 49 | [(vector-ref table check-n) #f] |
||
| 50 | [else |
||
| 51 | (set! (vector-ref table check-n) #t) |
||
| 52 | (loop rest)])))))) |
||
| 53 | |||
| 54 | (define (pandigital? n) |
||
| 55 | (assume (exact-integer? n)) |
||
| 56 | (assume (<= 1_0000_0000 n 9_9999_9999)) |
||
| 57 | (let ([table (make-vector 10 #f)]) |
||
| 58 | (set! (vector-ref table 0) #t) |
||
| 59 | (let loop ([rest n]) |
||
| 60 | (if (zero? rest) |
||
| 61 | #t |
||
| 62 | (let ([check-n (mod rest 10)] |
||
| 63 | [rest (div rest 10)]) |
||
| 64 | (cond |
||
| 65 | [(vector-ref table check-n) #f] |
||
| 66 | [else |
||
| 67 | (set! (vector-ref table check-n) #t) |
||
| 68 | (loop rest)])))))) |
||
| 69 | |||
| 70 | (define find-max-pandigital |
||
| 71 | (let loop ([n 362]) |
||
| 72 | (if (< n 236) |
||
| 73 | (errorf "見つかりませんでした~%") |
||
| 74 | (let ([d9 (+ 9_000_18_000 |
||
| 75 | (* n 1_00_000) |
||
| 76 | (* n 2))]) |
||
| 77 | (if (pandigital? d9) |
||
| 78 | d9 |
||
| 79 | (loop (- n 1))))))) |
||
| 80 | |||
| 81 | (define answer-38 find-max-pandigital) |
||
| 82 | |||
| 83 | (format #t "38: ~d~%" answer-38) |
||
| 84 | ``` |