ホーム - Project Euler

Problem 51¶

Prime Digit Replacements¶

By replacing the 1^st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3^rd and 4^th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

素数の桁置換¶

*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる.

56**3の第3桁と第4桁を同じ数で置き換えることを考えよう. この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.

桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)

(import (scheme base)
        (gauche base))

(define (prime? num)
  (assume (exact-integer? num))
  (assume (positive? num))
  (cond
    [(= num 1) #f]
    [(= num 2) #t]
    [(even? num) #f]
    [(= num 3) #t]
    [(zero? (mod num 3)) #f]
    [else
      (let loop ([n6-1 5])
        (let ([n6+1 (+ n6-1 2)])
          (cond
            [(< num
                (* n6-1 n6-1))
             #t]
            [(zero? (mod num n6-1))
             #f]
            [(< num
                (* n6+1 n6+1))
             #t]
            [(zero? (mod num n6+1))
             #f]
            [else
              (loop (+ n6+1 4))])))]))

(define digit-6-pattern
  (let loop1 ([a 0] [lis '()])
    (if (< 3 a)
      lis
      (let loop2 ([b (+ 1 a)] [lis lis])
        (if (< 4 b)
          (loop1 (+ a 1) lis)
          (let ([temp (string->vector "*****c")])
            (vector-set! temp a #\a)
            (vector-set! temp b #\b)
            (loop2 (+ 1 b)
                   (cons (vector->string temp)
                         lis))))))))

(define (sum-num-lis numstr)
  (fold (^[c sum]
          (let ([n (digit->integer c)])
            (if n
              (+ sum n)
              sum)))
        0
        (string->list numstr)))

(define (digit-6-list pattern)
  (filter
    (^[numstr]
      (not (zero?
             (mod (sum-num-lis numstr)
                  3))))
    (let loop ([index 0]
               [rest (string->list pattern)]
               [temp '()]
               [result '()])
      (let ([next-loop (^[select-num-list]
                         (fold-right
                           (^[n lis]
                             (loop (+ index 1)
                                   (cdr rest)
                                   (cons (integer->digit n) temp)
                                   lis))
                           result
                           select-num-list))])
        (cond
          [(null? rest)
           (cons (list->string (reverse temp))
                 result)]
          [(char=? (car rest) #\*)
           (loop (+ index 1)
                 (cdr rest)
                 (cons #\* temp)
                 result)]
          [(zero? index)
           (next-loop (iota 9 1))]
          [(= index 5)
           (next-loop '(1 3 7 9))]
          [else
            (next-loop (iota 10))])))))

(define all-6-list
  (fold (^[pattern result]
          (append (digit-6-list pattern)
                  result))
        '()
        digit-6-pattern))

(define (replace-numstr numstr n)
  (string->number
    (string-map (^c
                  (if (char=? c #\*)
                    (integer->digit n)
                    c))
                numstr)))

(define (prime-6digit? numstr)
  (let ([select-num-list (iota 10)])
    (when (char=? (string-ref numstr 0)
                  #\*)
      (set! select-num-list (cdr select-num-list)))
    (let loop ([rest-num-list select-num-list]
               [find-count 0])
      (cond
        [(<= 8 find-count)
         numstr]
        [(null? rest-num-list)
         #f]
        [(prime? (replace-numstr
                   numstr
                   (car rest-num-list)))
         (loop (cdr rest-num-list) (+ find-count 1))]
        [else
          (loop (cdr rest-num-list) find-count)]))))

(define all-valid-6-list
  (fold (^[numstr lis]
          (if (prime-6digit? numstr)
            (cons numstr lis)
            lis))
        '()
        all-6-list))

(define (small-prime-6digit numstr)
  (cond
    [(and (not (char=?
                 (string-ref numstr 0)
                 #\*))
          (prime? (replace-numstr numstr 0)))
     (replace-numstr numstr 0)]
    [(prime? (replace-numstr numstr 1))
     (replace-numstr numstr 1)]
    [else (replace-numstr numstr 2)]))

(define answer-51
  (apply min
         (map small-prime-6digit
              all-valid-6-list)))

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