不重复地写出[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}]