Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]

# [[Problem 26]]

## Reciprocal Cycles

A unit fraction contains $1$ in the numerator. The decimal representation of the unit fractions with denominators $2$ to $10$ are given:

$1/2 = 0.5$

$1/3 =0.(3)$

$1/4 =0.25$

$1/5 = 0.2$

$1/6 = 0.1(6)$

$1/7 = 0.(142857)$

$1/8 = 0.125$

$1/9 = 0.(1)$

$1/10 = 0.1$

Where $0.1(6)$ means $0.166666\cdots$, and has a $1$-digit recurring cycle. It can be seen that $1/7$ has a $6$-digit recurring cycle.

Find the value of $d \lt 1000$ for which $1/d$ contains the longest recurring cycle in its decimal fraction part.

## 逆数の循環節 その1

単位分数とは分子が1の分数である. 分母が2から10の単位分数を10進数で表記すると次のようになる.

1/2 = 0.5

1/3 = 0.(3)

1/4 = 0.25

1/5 = 0.2

1/6 = 0.1(6)

1/7 = 0.(142857)

1/8 = 0.125

1/9 = 0.(1)

1/10 = 0.1

0.1(6)は 0.166666... という数字であり, 1桁の循環節を持つ. 1/7 の循環節は6桁ある.

d < 1000 なる 1/d の中で小数部の循環節が最も長くなるような d を求めよ.

```scheme

(import (scheme base)

        (gauche base)

        (scheme sort))

(define (get-recurring-cycle n)

  (let loop ([index 0] [current-mod 1] [lis '()])

    (cond

      [(zero? current-mod) 0]

      [(find (^c (= current-mod (cdr c))) lis)

       => (^c (- index (car c)))]

      [else (loop (+ index 1)

                  (mod (* current-mod 10) n)

                  (cons `(,index . ,current-mod) lis))])))

(define (enum-recurring-cycles n)

  (map (^n (cons n (get-recurring-cycle n)))

       (iota (- n 1) 1)))

(define answer-26

  (car

    (last

      (list-sort (^[a b] (< (cdr a) (cdr b)))

                 (enum-recurring-cycles 1000)))))

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

```