算法： 循环节长为 k 的分数的最小分母

elim

设 $1 < k \in\mathbb{N},  B_k = \{b\in\mathbb{N}^+:  \exists a\in \mathbb{N} (\frac{a}{b}\text{的循环节长} k)\}$, 求 $\min B_k$

liangbch

你查一下本站的帖子吧。我记得站长gxq对此问题有研究，对于指定的既约分数p/q,站长的程序可以快速的求得循环节的长度。

gxqcn

求循环节长度，需要用到初等数论中的“指数”概念，
但反过来已知循环节长度，求分母，暂想不出特别好的算法，
如果值不很大的话，采用遍历法应该也蛮快的。

mathe

很简单，999…9因子分解即可，k个9

elim

命题 $\min B_k = \min \{b: (b | 10^k -1)\wedge (\forall d \in\mathbb{N}^+ ((d | k > d)\implies &#172;(b | 10^d -1)))\}$

例 $k = 6, 10^6 -1 = 3^3\cdot 7\cdot 11\cdot 13\cdot 37,\;10^3-1 = 3^3\cdot 37,\;10^2 -1 = 3^2\cdot 11$
      $10^1-1 = 3^2.$ 故 $\min B_6 = \min\{3^{e_1} 7^{e_2}11^{e_3}13^{e_4}37^{e_5} | e_2+e_4 > 0\} = 7$

      $k = 3,  10^3 - 1 = 3^3\cdot 37,  10^1 - 1 = 3^2$ 故
      $\min B_3 = \{b = 3^{e_1}37^{e_2} | (e_1 = 3)\vee (e_2 = 1)\} = 3^3 = 27.$

elim

对大值 k, 解严重依赖于 repunit ($11\cdots 1 = (10^k -1)/9$)的分解. 一般PC搞不定，
但有一个非常棒的网站可以下 repunit 数据: http://mada.la.coocan.jp/nrr/repunit/

elim

这种分母l理论上是 $10^k -1$ 的因子中除不尽任何 $10^d-1$ 的最小者。其中 $d | k >d >0$.
按这个思路求解就得分解楼上说的 repunit.

站长建议的遍历方法(也就是对分母序列$\{n\}$逐项求对应的循环节长，直到循环节长为给定$k$为止，
这种思想指导下的算法，应该有很大优化空间)。这应该是在一般PC上可行的快速方法。

elim

楼上的算法没有错误，但本质上还是依赖于 10^k - 1 的分解。只是用最原始的方法从小到大找  10^k - 1 的因子，看其是不是任何 10^d -1 的因子(其中 `d\mid k, 1\le d < k` ), 若不是就停止循环，输出结果。

可见算法有（猜想）不小于 $\frac{\log k}{k}$ 的几率会不出结果： 例如 k = 101 就可以让计算机算到世界末日 (10^101 - 1 = 9x 4531530181816613234555190841 x 129063282232848961951985354966759 x 18998088572819375252842078421374368604969). 所以算法应该调用 repunit 因子分解数据库. 在这方面 mathematica 远远比不上 pari/gp, 而后者虽然不像其他软件那样impossible, 还是慢。所以借助于已有计算有实质性的提升。

zeroieme

跟前$10^d-1$重复的因子 逐一用最大公约数检查更快吧。