pe 129(repunit divisibility,含证明)

發表於 更新於 分類於 Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘

题目

https://projecteuler.net/problem=129

题意

给一个整数n,(gcd(n,10)=1)，找最小的 111...111使得是n的倍数，A(n)返回这个最小的长度

A(7)=6,A(41)=5

求最小的n能让A(n) > 1000000的

存在性证明

题目说始终存在

因为$\text{gcd}(n,10) = 1$所以n不包含2和5这两个质因子

考虑结尾的字符为1,3,7,9

因为要证明的是任意n都能找到111...111，对于3,7,9结尾的，对应乘上7,3,9都会变成1 结尾的

那我们其实只要证明了 任何以1结尾的数，能找到111...111是它的倍数即可，我卡住了

对于给定n要找到,考虑它的每个质数因子p

$(10^i-1)/9 = 0 \pmod p$

费马小定理

$a^{p-1} - 1 = 0 \pmod p$

如果$p=3$, 有111是它的倍数(不是按照上面的公式, 因为有除以9的部分)

如果$p$是非2,3,5的质数

$10^{p-1}-1=0 \pmod p$

$(10^{p-1}-1)/9=0 \pmod p$

我们只得到

$10^{(p_1-1)(p_2-1)(p_3-1)} = 1 \pmod {p_1 p_2 p_3}$

但是如果有幂次质因子还是未知

和费马小定理相似但是更强劲的 欧拉定理

$a^{\varphi (n)} \equiv 1 \pmod{n}$

要求正好是 a和n互质

对于不含质因子3的$n$，能直接通过上式得到

$10^{\varphi (n)} \equiv 1 \pmod{n}$

$(10^{\varphi (n)} - 1)/9 \equiv 0 \pmod{n}$

对于含有3质因子的$n$,直接考虑9n

$10^{\varphi (9n)} \equiv 1 \pmod{9n}$

$10^{\varphi (9n)} - 1 \equiv 0 \pmod{9n}$

$(10^{\varphi (9n)} - 1)/9 \equiv 0 \pmod{n}$

得证

证明 $A(n) \le n$

考虑找到的$111\cdots 111$ 对应的商 $x = 111\cdots111 / n$

因为我们上面证明了$n$能整除，所以倒过来思考乘积如何填数

$x \cdot n = 111\cdots111$

因为 n 的末位是$1,3,7,9$中的奇数，那么 对于给定的尾数能直接确定商的尾数

同样我们能唯一确定十位,考虑每次计算后的余数

这里的余数是指 $((最少的前补1(\ge 0个) + 上一次的剩余值 - 当前商位上的数码\cdot n)/10) \pmod n$,

显然，上一次的剩余值通过个位数唯一决定 当前商的数码，又 前补1要最少又能满足表达式大于0,也是唯一方案。

因此 低$i$位的余数唯一确定$i+1$位的余数 $r_{i+1} = f(r_i)$，注意多个剩余值可能对应同一个余数，但这些余数相同的剩余值推导出的 高位的剩余值唯一

因此 考虑余数的变化，因为最终余数为零，所以中途余数不能成环。综上，商的位数不会超过$n$

因此原始的$111\cdots 111 = x\cdot n$ 也不会超过$n$

以7 举例, 说明上面的证明过程

$3\cdot 7=21,(111-21)/10 = 9 = 2 \pmod 7$

余数是控制链的长度，但是不影响计算 所以下面是109而不是102, 稍加理解的话是$102 - 6\cdot 7 = 109 - 7\cdot 7$

$7\cdot 7=49,(109-49)/10 = 6 = 6 \pmod 7$

$8\cdot 7=56,(106-56)/10 = 5 = 5 \pmod 7$

$5\cdot 7=35,(105-35)/10 = 7 = 0 \pmod 7$ // 同上不影响计算

$1\cdot 7 = 7, 7 - 7 = 0$

因此$15873 \cdot 7 = 111111$

余数变化是$2 \to 6 \to 5 \to 0$

对应上面唯一描述是

剩余值$11$,确定商的数码$3$,$3\cdot 7=21$,最少补充1个1,$(111-21=90)/10 = 9$,剩余值9,余数2

剩余值$ 9$,确定商的数码$7$,$7\cdot 7=49$,最少补充1个1,$(109-49=60)/10 = 6$,剩余值6,余数6

剩余值$ 6$,确定商的数码$8$,$8\cdot 7=56$,最少补充1个1,$(106-56=50)/10 = 5$,剩余值5,余数5

剩余值$ 5$,确定商的数码$5$,$5\cdot 7=35$,最少补充1个1,$(105-35=70)/10 = 7$,剩余值7,余数0

剩余值$ 7$,确定商的数码$1$,$1\cdot 7=7 $,最少补充0个1,7-7=0 结束

其实上面欧拉定理，我们只用关心 n 包含质因子3的情况，A(i) 是否会超过n

代码

幂次总是在小于 n的时候能模为1,这样可以从1000000开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def A(v):
    p = 1
    for j in range(1, 9*v+1):
        p *= 10
        p %= 9*v
        if p % (9*v) == 1:
            return j


def main():
    maxAi = 0
    for i in range(500000-10, 1000000):
        ii = i*2+1
        if ii % 10 != 5:
            Ai = A(ii)
            # if Ai > ii:
            #     print(ii, Ai)
            if Ai - maxAi > 10000:
                maxAi = Ai
                print(ii, Ai)
            if Ai > 1000000:
                print(ii, Ai)
                break
    print("end")


main()

参考

https://mathlesstraveled.com/2011/11/16/fun-with-repunit-divisors-proofs/

https://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem#Introductory

https://en.wikipedia.org/wiki/Euler%27s_theorem