若不存在这样的n，请证明2的n次方不能够被11整除，即2^nmod(11)≠0。...
若不存在这样的n，请证明2的n次方不能够被11整除，即2^n mod(11)≠0。
展开选择擅长的领域继续答题？
{@each tagList as item}
${item.tagName}
{@/each}
手机回答更方便，互动更有趣，下载APP
}

n 最小值 106粗略猜想，平均每 11 可能会有 1 个数的串联能被 11 整除快速计算公式存在：var (
t1 = []int{10, 10, 0, 2, 5, 9, 3, 9, 5, 2, 0}
)
func f2(n int) int {
if n <= 0 {
return -1
}
p, t := place(n)
result := 0
if p > 1 {
result = (117 - p) % 11
}
if p%2 == 1 {
b := (n - t)
d := (b + 2) % 22 / 2
if b%2 == 0 {
result = d + 11 - result
} else {
result = d + result
}
} else {
result += t1[(n-t)%11]
}
if result >= 11 {
result -= 11
}
return result
}
func place(n int) (int, int) {
p := 1
t := 1
for n >= 100000000 {
p += 8
t *= 100000000
n /= 100000000
}
if n >= 10000 {
p += 4
t *= 10000
n /= 10000
}
if n >= 100 {
p += 2
t *= 100
n /= 100
}
if n >= 10 {
p++
t *= 10
n /= 10
}
return p, t
}
大整数法：func bigger() int {
i0 := big.NewInt(0)
i10 := big.NewInt(10)
i11 := big.NewInt(11)
b := big.NewInt(0)
t := big.NewInt(10)
for i := 1; ; i++ {
bi := big.NewInt(int64(i))
if t.Cmp(bi) == 0 {
t.Mul(t, i10)
}
b.Mul(b, t).Add(b, bi)
bi.Mod(b, i11)
if bi.Cmp(i0) == 0 {
return i
}
}
}
// 输出 106
首先我们利用被 11 整除的特点来简化一下运算过程：若 a%11=b，则 a*100%11=(a*99+a)%11=a%11=b推广：若 a%11=b，则 a*10^(2d)%11=b（注：d 为整数）若 a%11=b，则 a*10%11=(a*11-a)%11=-a%11=-b（注：负数可以加 11 转正）推广：若 a%11=b，则 a*10^(2d+1)%11=-b显然，(a+c)%11=(a%11+c%11)%11推广：(a+c)%11=(a*10^(2d)%11+b%11)%11推广：(a+c)%11=(-a*10^(2d+1)%11+b%11)%11结合问题来说，可以发现：当 n 的位数是奇数，则 f(n)=(f(n-1)*10^(2d+1)+n)%11=(n-f(n-1))%11=(n+11-f(n-1))%11当 n 的位数是偶数，则 f(n)=(f(n-1)*10^(2d)+n)%11=(n+f(n-1))%11因为是求模，所以 f(x) 都是 0-10 的数（负数通过加 11 转正），n 更是模成 0-10 的循环，所以整个计算并不需要（高精度）大整数。func main() {
result := 0
c := 10
t := 10 // 下一个更长位数的数字
p := 1 // 当前数字位数
for i := 1; c > 0; i++ {
if i == t {
t *= 10
p++
}
odd, diff := p % 2 == 1, i % 11
if odd {
result = diff + 11 - result
} else {
result = diff + result
}
if result >= 11 {
result -= 11
}
if result == 0 {
c--
fmt.Printf("%10d: %3d, %5t, result: %10d\n", i, diff, odd, result)
}
}
}
输出结果：
106:
7,
true, result:
0
113:
3,
true, result:
0
128:
7,
true, result:
0
135:
3,
true, result:
0
150:
7,
true, result:
0
157:
3,
true, result:
0
172:
7,
true, result:
0
179:
3,
true, result:
0
194:
7,
true, result:
0
201:
3,
true, result:
0可以发现，两个 n 的间隔在 7 与 15 交替。（后来发现 7+15=11*2 啊！）按照公式，可以找到一些周期性。令 a=10^(2d+1)，可知 a 的位数为偶数。若 a+x 的位数与 a 相同，则有 f(a+x)=(f(a-1)+(a+0)+(a+1)+(a+2)+...(a+x))%11。又 a%11=10^(2d+1)%11=10，所以 f(a+x)=(f(a-1)+10+11+12+...+(x+10))%11。所以这个显然存在与 x 的周期性。很容易求出 10~(x+10) 和模 11 的周期性：10, 10, 0, 2, 5, 9, 3, 9, 5, 2, 0。根据不同的前值（即 f(a-1) 的值范围 0-10），可以得出一张表：可以看到，若前值为 3、4、5、7、10 时，周期里面不会出现 0 值，也就是无法被整除。前值为 0、1、2、6、9 时，会有两个 0 值，剩下 8 只有一个 0 值。（如果分布平均，那么可以认为 121 个数有 11 个能被整除，也就是 11 个里面有 1 个。）容易知道 f(9) = 5，所以 f(10)~f(99) 都没有 0 值，也就是没有能被整除的。现在令 a=10^(2d)，可知 a 的位数为奇数，且 a%11=10^(2d)%11=1。可以观察到，f(a)=(a-f(a-1))%11=(1-f(a-1))%11，f(a+1)=(a+1-f(a))%11=(1+1-(1-f(a-1))%11=(2-1+f(a-1))%11，f(a+2)=(a+2-f(a+1))%11=(3-2+1-f(a-1))%11。足够的观察后发现，每 22 个数可以满足一个周期，可以用 WPS 做出下表：可以看出，对位数为奇数的 n 来说，每 22 个就有 2 个能被 11 整除。确认周期性之后，就可以快速搜索不同位数的周期性。计算前 22 个数的整除情况，剩下数字直接模 22 就能快速知道结果。比如 (999-100)%22=19，所以 999 与 119 的相当。知道 999 的值，那么 1000～1021 的值也能算出来，然后 9999 也就出来了。func quick() {
result := 0
t := 10
p := 1
i := 1
i22 := make([]int, 0, 22)
for p <= 17 {
if p % 2 == 1 {
result = 11 - result
}
result += i % 11
if result >= 11 {
result -= 11
}
if result == 0 {
fmt.Printf("%18d, result %2d\n", i, result)
}
i22 = append(i22, result)
if len(i22) == 22 {
i = t - 1 // 加速
result = i22[(i-t/10) % 22]
}
i++
if i == t {
t *= 10
p++
i22 = i22[:0]
}
}
fmt.Printf("quick done\n")
}
输出如下：
106, result
0
113, result
0
10002, result
0
10017, result
0
100000, result
0
100001, result
0
100011, result
0
100012, result
0
1000020, result
0
1000021, result
0
100000003, result
0
100000016, result
0
1000000006, result
0
1000000017, result
0
10000000007, result
0
10000000012, result
0
100000000004, result
0
100000000008, result
0
100000000015, result
0
100000000019, result
0
1000000000008, result
0
1000000000011, result
0
100000000000004, result
0
100000000000015, result
0
1000000000000005, result
0
1000000000000007, result
0
1000000000000016, result
0
1000000000000018, result
0
10000000000000000, result
0
10000000000000019, result
0早期想利用的特性如下：被 11 整除的数有一个特点：所有位数按奇偶分开，（奇数位的和）与（偶数位的和）的差能被 11 整除。此处有一个递归：若一个数能被 11 整除，其奇偶数位和之差也能被 11 整除。对于 n，可以计算 n 自身的奇数位数字之和与偶数位之和的减值，以 g(n) 表示这个差值。可以推导一些特性，如 g(n) = n % 10 - g(int(n/10))。n 串到 n-1 的结果上，如果 n 本身是位数是奇数，会导致 n-1 的结果奇偶互换；然后再加上 g(n) 就可以。通项式也许存在呢？关键点是计算 f(10^d-1) 的值。注意到：
9, result
5
99, result
4
999, result
3
9999, result
2
99999, result
1
999999, result
0
9999999, result 10
99999999, result
9
999999999, result
8
9999999999, result
7
99999999999, result
6
999999999999, result
5
9999999999999, result
4
99999999999999, result
3
999999999999999, result
2
9999999999999999, result
1
99999999999999999, result
0也就是周期性是显然存在的。从 10^d 到 10^(d+1)-1，一共是 9*10^d 个数字，对 d >= 1 来说，一定是偶数个数字。所以从 10^(d)-1 串联到 10^(10+1)-1，f(10^(d)-1) 的值不需要翻转。观察对 9 串联 10～99 的数字，个数位的 0～9 各有 9 个，十数位 1～9 各有 10 个，0 不影响结果，所以结果是十数位多出来一套 1～9。考虑到 2+9、3+8、4+7、5+6 刚才配对，所以等于十数位多出来 1。所以模 11 的值减 1。再考虑 999 串联 1000～9999，低两位的 0-9 是一样多的，可以忽略。百数位 0～9 各有 900 个，千数位 1～9 各有 1000 个，也就是千数位多出 100 套 1～9。其中 99 套归零，最后还是剩下 1～9 套。所以结论还是千数位多 1，对模 11 的影响是再次减 1。可以确认数字位数是偶数的 99..99，对比前一个 99..9 来说，模 11 的值要减 1。那么位数为奇数的情况，如对 99 串联 100～999。因为百数位的数字 1～9 是交错变成奇偶位（比如 1xx1xx），每个数字都是 100 个，所以刚好归零。十数位的数字也是 10 个一组，奇偶交错，也是归零。那么个数位的数字实际上变成 90 组 0123456789。考虑到 f(9)=5，所以这 90 组等于 90*5%11=10，也相当于模 11 减 1。直接计算 f(n) 的代码：func f(n int) int {
if n <= 0 {
return -1
}
s := strconv.Itoa(n)
odd := len(s) % 2 == 1
result := 0
i := 0
m := 0
if len(s) > 1 {
t := 1
for c := 1; c < len(s); c++ {
t *= 10
}
result = (117-len(s)) % 11
i = t - 1
m = i % 11
}
for c := (n - i) % 22; c > 0; c-- {
m++
if m == 11 {
m = 0
}
if odd {
result = m + 11 - result
} else {
result += m
}
if result >= 11 {
result -= 11
}
}
return result
}
}