ホーム - Project Euler

Problem 38¶

Pandigital Multiples¶

Take the number $192$ and multiply it by each of $1$, $2$, and $3$:

\begin{align} 192 \times 1 &= 192\\ 192 \times 2 &= 384\\ 192 \times 3 &= 576 \end{align}

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)$.

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)$.

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$?

パンデジタル倍数¶

192 に 1, 2, 3 を掛けてみよう.

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

積を連結することで1から9の パンデジタル数 192384576 が得られる. 192384576 を 192 と (1,2,3) の連結積と呼ぶ.

同じようにして, 9 を 1,2,3,4,5 と掛け連結することでパンデジタル数 918273645 が得られる. これは 9 と (1,2,3,4,5) との連結積である.

整数と (1,2,...,n) (n > 1) との連結積として得られる9桁のパンデジタル数の中で最大のものはいくつか?

(import (scheme base)
        (gauche base))

(define (valid-num? n)
  (assume (exact-integer? n))
  (assume (<= 236 n 362))
  (let ([table (make-vector 10 #f)])
    (set! (vector-ref table 0) #t)
    (set! (vector-ref table 1) #t)
    (set! (vector-ref table 8) #t)
    (set! (vector-ref table 9) #t)
    (let loop ([rest n])
      (if (zero? rest)
        #t
        (let ([check-n (mod rest 10)]
              [rest (div rest 10)])
          (cond
            [(vector-ref table check-n) #f]
            [else
              (set! (vector-ref table check-n) #t)
              (loop rest)]))))))

(define (pandigital? n)
  (assume (exact-integer? n))
  (assume (<= 1_0000_0000 n 9_9999_9999))
  (let ([table (make-vector 10 #f)])
    (set! (vector-ref table 0) #t)
    (let loop ([rest n])
      (if (zero? rest)
        #t
        (let ([check-n (mod rest 10)]
              [rest (div rest 10)])
          (cond
            [(vector-ref table check-n) #f]
            [else
              (set! (vector-ref table check-n) #t)
              (loop rest)]))))))

(define find-max-pandigital
  (let loop ([n 362])
    (if (< n 236)
      (errorf "見つかりませんでした~%")
      (let ([d9 (+ 9_000_18_000
                   (* n 1_00_000)
                   (* n 2))])
        (if (pandigital? d9)
          d9
          (loop (- n 1)))))))

(define answer-38 find-max-pandigital)

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