不重复地写出[0,1]内的所有既约真分数，并加以证明

时空伴随者

如题，不重不漏写出来，有没有机械性的方法呢？

luyuanhong

下面是我过去在《数学中国》发表过的一个帖子，可供参考：

luyuanhong

下面是我过去在《数学中国》发表过的一个帖子：

时空伴随者

\(定义一种有理数插值法：\frac{a}{b}\hat{+}\frac{c}{d}=\frac{a+c}{b+d}\)
\(\\0,1自动看成\frac{0}{1}，\frac{1}{1}\\然后，做如下操作：\\\)
\(\frac{0}{1},\frac{1}{2},\frac{1}{1},\\ \)
\(\frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1},\\ \)
\(\frac{0}{1},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{1}{1},\\ \)
\(\frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{3}{8},\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{1}{1},\\ \)
\(\frac{0}{1},\frac{1}{6},\frac{1}{5},\frac{2}{9},\frac{1}{4},\frac{3}{11},\frac{2}{7},\frac{3}{10},\frac{1}{3},\frac{4}{11},\frac{3}{8},\frac{5}{13},\frac{2}{5},\frac{5}{12},\frac{3}{7},\frac{4}{9},\frac{1}{2},\frac{5}{9},\frac{4}{7},\frac{7}{12},\frac{3}{5},\frac{8}{13},\frac{5}{8},\frac{7}{11},\frac{2}{3},\frac{7}{10},\frac{5}{7},\frac{8}{11},\frac{3}{4},\frac{7}{9},\frac{4}{5},\frac{5}{6},\frac{1}{1},\\ \)
... ...

时空伴随者

如4#所示，既约真分数\(\frac{q}{p}\)必然在第p-1次操作中完成，怎样证明呢？

王守恩

不重不漏地写出(0,1)内的所有既约真分数。——普遍的方法。

{{1, 1, 2}, {2, 1, 3}, {3, 2, 3}, {4, 1, 4}, {5, 3, 4}, {6, 1, 5}, {7, 2, 5}, {8, 3, 5}, {9, 4, 5}, {10, 1, 6}, {11, 5, 6}, {12, 1, 7}, {13, 2, 7}, {14, 3, 7}, {15, 4, 7}, {16, 5, 7}, {17, 6, 7}, {18,1, 8}, {19, 3, 8}, {20, 5, 8},{21, 7, 8}, {22, 1, 9},
{23, 2, 9}, {24, 4, 9}, {25, 5, 9}, {26, 7, 9}, {27, 8, 9}, {28, 1, 10}, {29, 3, 10}, {30, 7, 10}, {31, 9, 10}, {32, 1, 11}, {33, 2, 11}, {34, 3, 11}, {35, 4, 11}, {36, 5, 11}, {37, 6, 11}, {38, 7, 11}, {39, 8, 11}, {40, 9, 11}, {41, 10, 11}, {42, 1, 12},
{43, 5, 12}, {44, 7, 12}, {45, 11, 12}, {46, 1, 13}, {47, 2, 13}, {48, 3, 13}, {49, 4, 13}, {50, 5, 13}, {51, 6, 13}, {52, 7, 13}, {53, 8, 13}, {54, 9, 13}, {55, 10, 13}, {56, 11, 13}, {57, 12, 13}, {58, 1, 14}, {59, 3, 14}, {60, 5, 14}, {61, 9, 14},
{62, 11, 14}, {63, 13, 14}, {64, 1, 15}, {65, 2, 15}, {66, 4, 15}, {67, 7, 15}, {68, 8, 15}, {69, 11, 15}, {70, 13, 15}, {71, 14, 15}, {72, 1, 16}, {73, 3, 16}, {74, 5, 16}, {75, 7, 16}, {76, 9, 16}, {77, 11, 16}, {78, 13, 16}, {79, 15, 16}, {80, 1, 17},
{81, 2, 17}, {82, 3, 17}, {83, 4, 17}, {84, 5, 17}, {85, 6, 17}, {86, 7, 17}, {87, 8, 17}, {88, 9, 17}, {89, 10, 17}, {90, 11, 17}, {91, 12, 17}, {92, 13, 17}, {93, 14, 17}, {94, 15, 17}, {95, 16, 17}, {96, 1, 18}, {97, 5, 18}, {98, 7, 18}, {99, 11, 18}}
代码——MapIndexed[Prepend[#1, First@#2] &, Take[Select[Flatten[Table[{p, q}, {q, 18}, {p, q - 1}], 1], GCD @@ # == 1 &], 99]]

方法能够解决2个基本问题——

(1)。什么数是第几个数？譬如:  35/200167是第几个数？
代码——W[p_, q_] := Tr[EulerPhi@Range[q - 1]] + Count[Range[p - 1], _?(CoprimeQ[#, q] &)]; W[35, 200167]
12178745362——35/200167是第12178745362个数。

(2)。第几个数是什么数？譬如:  第12345678个数是什么数？
代码——W[n_] := MapIndexed[Prepend[#1, First@#2] &, Select[Join @@ Table[{p, q}, {q, NestWhile[# + 1 &, 1, Length[FareySequence[#]] < n + 2 &]}, {p, q - 1}], CoprimeQ @@ # &]][[n]]; W[12345678]
代码——W[n_] := MapIndexed[Prepend[#1, First@#2] &, Select[Join @@ Table[{p, q}, {q, NestWhile[# + 1 &, 1, Plus @@ EulerPhi[Range[#]] - 1 < n &]}, {p, q - 1}], CoprimeQ @@ # &]][[n]]; W[12345678]
{12345678, 3219, 6373}——第12345678个数是3219/6373。

方法跟这串数有关系。这串数可以有2个代码。
{1, 3, 5, 9, 11, 17, 21, 27, 31, 41, 45, 57, 63, 71, 79, 95, 101, 119, 127, 139, 149, 171, 179, 199, 211, 229, 241, 269, 277, 307, 323, 343, 359, 383, 395, 431, 449, 473, 489, 529, 541, 583, 603, 627, 649, 695, 711, 753, 773, 805, 829, 881, 899, 939}
1表示分母是2的既约真分数有1个,  3表示分母是2,3的既约真分数有3个,  5表示分母是2,3,4的既约真分数有5个,  9表示分母是2—5的既约真分数有9个,  11表示分母是2—6的既约真分数有11个,  17表示分母是2—7的既约真分数有17个,  ......
代码(1)——Table[Length[FareySequence[n]] - 2, {n, 2, 57}]
代码(2)——Table[Plus @@ EulerPhi[Range[n]] - 1, {n, 2, 57}]

luyuanhong

时空伴随者

时空伴随者 发表于 2026-9-21 11:58
如4#所示，既约真分数\(\frac{q}{p}\)必然在第p-1次操作中完成，怎样证明呢？

4#展示的分子的序列，恰好是A002487
Stern's diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1).
(Formerly M0141 N0056)
392
0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19