Problem 71¶
Ordered Fractions¶
Consider the fraction, $\dfrac n d$, where $n$ and $d$ are positive integers. If $n \lt d$ and $\operatorname{HCF}(n,d)=1$, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for $d \le 8$ in ascending order of size, we get:
$$\frac 1 8, \frac 1 7, \frac 1 6, \frac 1 5, \frac 1 4, \frac 2 7, \frac 1 3, \frac 3 8, \mathbf{\frac 2 5}, \frac 3 7, \frac 1 2, \frac 4 7, \frac 3 5, \frac 5 8, \frac 2 3, \frac 5 7, \frac 3 4, \frac 4 5, \frac 5 6, \frac 6 7, \frac 7 8$$
It can be seen that $\dfrac 2 5$ is the fraction immediately to the left of $\dfrac 3 7$.
By listing the set of reduced proper fractions for $d \le 1,000,000$ in ascending order of size, find the numerator of the fraction immediately to the left of $\dfrac 3 7$.
順序分数¶
nとdを正の整数として, 分数 n/d を考えよう. n<d かつ HCF(n,d)=1 のとき, 真既約分数と呼ぶ.
d ≤ 8について既約分数を大きさ順に並べると, 以下を得る:
3/7のすぐ左の分数は2/5である.
d ≤ 1,000,000について真既約分数を大きさ順に並べたとき, 3/7のすぐ左の分数の分子を求めよ.
(import (scheme base)
(gauche base))
;;; ファレイ数列の性質から、3/7 の左隣は
;;; 3b - 7a = 1 を満たす a/b である
;;; b <= 10^6 を満たす中で最大の b を求め
;;; その時の a/b が答えになる
(define (a-b)
(let loop ([b #e1e6])
; 7a = 3b - 1
(let ([current (- (* b 3) 1)])
(if (zero? (mod current 7))
`(,(div current 7) ,b)
(loop (- b 1))))))
(define answer-71 (car (a-b)))
(format #t "71: ~d~%" answer-71)
Noppi が2024/02/01に更新 · 2件の履歴