MATHEMATICA例程2——小数循环节

Standard

 

Hello大家好,这里是Mathematica例程大讲堂。

之前发现从关键词 Mathematica 过来的搜索流量偏高,于是便跑过来填这个许久之前挖的坑。上一篇文章是讲关于如何用 Mathematica 生成 Look And Say 序列,反复看了之后觉得难度太高,不适合初学,于是这次便来讲一点简单的、比较基本的例子。


一、主要目标

这次要计算的是 1/n 的小数部分的最小循环节长度,其中 n 最好是质数,例如:

1 / 3  = 0.333...
1 / 7  = 0.142857142857...
1 / 19 = 0.0526315789473684210526...

1/7 的循环节是"142857",有6位,而 1/19 的循环节是"052631578947368421",有18位,以此类推。

如果你觉得从中找到了规律,不妨来猜一下 1/81,1/9801 的循环节长度是多少位呢?^_^


二、分析

求分数的最小循环节长度实际上是有固定方法的,下面介绍的是错位相减法,以 1/7 为例:

1000000 / 7 = 142857.14285714...
-)    1 / 7 =      0.14285714...
--------------------------------
 999999 / 7 = 142857.0

可以通过凑数的方法把小数部分的循环节减掉,只要相减的结果是整数,那么循环节就算出来了,循环节长度自然是呼之欲出了。

更具体地,我们应该用 7 不断去试除 9, 99, 999, 9999... 直到结果为整数,当 7 能整除 999999 时,循环节就是6位。


三、实现

至此方法已经讲完了,看起来一个简单的 While/For 循环就可以实现。那怎样在 Mathematica 中优雅地实现 While 循环呢?这便是本文要讲述的重点。

很多初学者可能第一反应就是在 Mma 的官方文档中对应函数,结果还真能找到 For 和 While 这两个函数,然后便参照C++的语法实现了,以为任务就完成了。殊不知这种看似很顺畅的做法在 Mathematica 中却相当低效,有悖于 Mma 整体函数式编程的范式。

所以在这里我不会列出用 While/For 实现的代码,以免误导新人,虽然这样的写法是完全正确且符合语法的。

有一套特定的函数式的语法结构可以实现这种需求:试想一下,我们不就是需要先生成一列数 (9, 99, 999 ...),然后在符合某个条件时终止并返回吗?有个叫 NestWhileDocs 的内置函数恰好就是来做这个的!

NestWhile: 

 

NestWhile[f, expr, test]

从 expr 开始,然后重复应用 f 直到 test 不再得到 True 为止。 

 

于是便有了方法一

In[1]:= NestWhile[10 # + 9 &, 9, ! IntegerQ[#/7] &] // IntegerLength
Out[1]= 6

这种方法从数字 9 开始,很 tricky 地构造了一个序列(99=9*10+9, 999=99*10+9, ...),然后不断尝试直到被 7 整除。

这种方法针对该特定问题是可以给出答案的,但是隐藏了内部迭代的变量,万一这个 9, 99, 999... 的序列不能由前一项推断出后一项呢?

下面介绍一种普适化的方法,即方法二

In[2]:= NestWhile[# + 1 &, 1, ! IntegerQ[(10^# - 1)/81] &]
Out[2]= 9

这种方式从数字 1 开始,用一个加一算子(#+1&)作为迭代函数,用“10的幂次减一”来构造迭代终止测试函数。这与 For 循环的处理流程颇为相似,但这种做法是彻底的函数式的,至少没有类似 "i++" 的变量出现。

小提示:

可以由此抽象出一类更一般的迭代范式:

NestWhile[succ, i, test]

其中 i 是初始迭代值,succ 是后继函数,test 是测试终止函数。

这种方法特别适合那种描述为 “找出第一个满足XX条件的数” 的问题。 

再具体一点,NestWhile[succ, i, test]For[i=1, test[i], i++, Null]; i 的输出结果是一致的,内部处理的逻辑也是一样的。如果你遇到需要枚举自增某个变量,然后在合适的时候终止的情况,建议使用第一种表达方法,不要使用第二种方法。不仅仅是因为第一种方法看起来更短,另一个差别在于第二种方法会产生全局变量 i,而第一种则不会。(简单的循环就使用了全局变量会直接暴露你是个 Mathematica 新手,这个大家都不想的嘛)

然后或许你可以动手计算一下1/81,1/9801 的循环节长度是多少?看和你猜想的一样吗?

 

四、小结及参考资料

这篇文章在我的草稿箱中一直压了近半年,好在今天检查的时候发现了它,就把它发了出来。本文的初衷是希望读者能学会在 Mathematica 中简单迭代的写法。如果遇到类似问题时,你的第一反应不是 For 的话,那么本文的目的便达到了。

文末附两个相关链接:

1. 小数循环节的选题来源:EP26 Reciprocal cycles

2. 一个相关的博客,里面讨论了本问题的推广形式及其在 Mma 中的一种巧妙实现的方式,供感兴趣的读者阅读:循环节那点事儿