Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|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つもつ最小の立方数を求めよ.

```scheme

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

```