对于正整数 n ≥ m:

例如,当 n ≥ 9 时:

当 n 非常大时,使用这个公式能够减少计算量。


取定正整数 m,令数列 an = 2n mod 10m,则 an+1 = 2an mod 10m。即:

  • 数列当前项的值决定了数列后一项的值
  • 数列的每一项都是小于 10m 的正整数

所以,这个数列必定是循环的,其最小正周期小于 10m


当 n ≥ 1 时,2n mod 101 的值(共 4·50 个):

  • 2, 4, 8, 6

当 n ≥ 2 时,2n mod 102 的值(共 4·51 个):

  • 12, 32, 52, 72, 92
  • 04, 24, 44, 64, 84
  • 16, 36, 56, 76, 96
  • 08, 28, 48, 68, 88

当 n ≥ 3 时,2n mod 103 的值(共 4·52 个):

  • 032, 072, 112, ..., 992
  • 024, 064, 104, ..., 984
  • 016, 056, 096, ..., 976
  • 008, 048, 088, ..., 968

当 n ≥ 4 时,2n mod 104 的值(共 4·53 个):

  • 0032, 0112, 0192, ..., 9952
  • 0064, 0144, 0224, ..., 9984
  • 0016, 0096, 0176, ..., 9936
  • 0048, 0128, 0208, ..., 9968

对于正整数 n,以下公式成立的概率大于 99.999999%:

当 n < 109 或 n mod 109 ≥ 9 时,这个公式成立。

评论

推荐 1
推导过程有吗
没有推导过程。这个公式是我自己观察一些测试数据后总结出来的。 –  黄志斌 02-16 08:15
用数学归纳法能证明吗 –  lt 02-16 08:44
好象不能用数学归纳法证明 –  黄志斌 02-17 14:52
正文中增加了一些内容 –  黄志斌 02-17 14:52
终于知道 4·5^n的来历了 –  lt 02-17 15:15

推荐 0
这个公式的使用示例见:
图灵社区:幂的一个公式(二)
http://www.ituring.com.cn/article/274311

推荐 0
当 m = 1 时,只要计算出数列 a 的前 5 项:2, 4, 8, 6, 2
就可以认为是这个公式的一个证明。
对于一般的 m,谁能给出一个证明。

我要评论

需要登录后才能发言
登录未成功,请修改提交。