Problem 26 - 循環節

Scheme

やっと解けた。

Problem 26 - PukiWiki

単位分数とは分子が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... という数字であり、6が循環節であることを表している。1/7 循環節は6桁ある。

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


100...を素数pで割っていくと、循環節を迎えた時に余りが1になる。という性質を利用する事にする。

10とは互いに素では無い、6の場合、余りが4で循環節のループに入ってしまい、循環節の判別が難しい。循環節も素数よりは短くなりそうなので、ターゲットを素数のみに絞る事にする。

(define (problem26 n)
  (define (p n)
    (letrec ((push (lambda (x n)
                     (cons (quotient (* 10 x) n)
                           (iter (modulo (* 10 x) n)))))
             (iter (lambda (x)
                     (cond ((zero? x) '())
                           ((= x 1) '(*loop*))
                           (else
                             (push x n))))))
            (cons 0
                  (push 1 n))))

  (fold-right (lambda (x m)
                (let ((len (- (length (p x)) 2)))
                     (if (> len (cadr m))
                         (list x len)
                         m)))
              '(0 0)
              (filter prime? (iota (- n 1) 2))))

(problem26 1000) ; (983 982)

あ、素数の抽出部分は略っす。

以下メモ。

  • 9999...で割り切れるまで。という方法もある。
  • 循環節の性質もかなり興味深い。
  • フェルマーの小定理について。
    • フェルマーの小定理はpが素数、aはpとは互いに素な整数とした場合、a^(p-1)をpで割った余りが1になるというもの。
    • 今回はa=10だったので、pを7とすると、10^6を7で割った余りが1になる。循環節も6だ。スゲー。
    • フェルマーさんは変態的な直感の持ち主らしい。
  • フェルマーの小定理→オイラーの関数へと発展していくらしい。


やっと解けた。フェルマーの小定理はかなり使えそうなテクニックなのでキッチリ覚えたい。

参考

追記

今回は素数を使ったけど、フェルマーの小定理なら、互いに素であることが条件なので、gcdでもいいと思う。