ホーム - Project Euler

Problem 62¶

Cubic Permutations¶

The cube, $41063625$ ($345^3$), can be permuted to produce two other cubes: $56623104$ ($384^3$) and $66430125$ ($405^3$). In fact, $41063625$ is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

立方数置換¶

立方数 $41063625$ ($345^3$) は, 桁の順番を入れ替えると2つの立方数になる: $56623104$ ($384^3$) と $66430125$ ($405^3$) である. $41063625$は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.

立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.

(import (scheme base)
        (gauche base))

(define (cube num)
  (* num num num))

(define (digit-vector num)
  (assume (exact-integer? num))
  (assume (positive? num))
  (let ([result (make-vector 10 0)])
    (let loop ([current num])
      (if (zero? current)
        result
        (let ([tail-num (mod current 10)])
          (vector-set! result
                       tail-num
                       (+ (vector-ref result tail-num)
                          1))
          (loop (div current 10)))))))

(define (same-vector? vec1 vec2)
  (let loop ([i 0])
    (cond
      [(< 9 i) #t]
      [(not (= (vector-ref vec1 i)
               (vector-ref vec2 i)))
       #f]
      [else
        (loop (+ i 1))])))

(define (permutate? num1 num2)
  (same-vector? (digit-vector num1)
                (digit-vector num2)))

(define (permutate-5-number)
  ; 345 ～ 464 までが 8 桁の候補 → ×
  ; 465 ～ 999 までが 9 桁の候補 → ×
  ; 1002 ～ 2154 までが 10 桁の候補 → ×
  ; 2155 ～ 4641 までが 11 桁の候補 → ×
  ; 4642 ～ 9999 までが 12 桁の候補 → ○
  (let loop ([result '()])
    (cond
      [(<= 5 (length result)) result]
      [(null? result)
       (any (^n
              (loop (cons n result)))
            (iota (- 9999 4642 -1) 4642))]
      [else
        (let* ([current (car result)]
               [next (+ 1 (car result))]
               [current-cube (cube current)])
          (if (< 9999 next)
            #f
            (any (^n
                   (loop (cons n result)))
                 (filter (^n
                           (permutate? current-cube (cube n)))
                         (iota (- 9999 next -1) next)))))])))

(define answer-62
  (cube (apply min (permutate-5-number))))

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