画一个三角形阵列,初始时只有每一行的两头有标记,然后从上到下依次把每一行复制两份,摆放成一个等边三角形。最后你会发现,第i行为空行(除两头外不再有其它标记),当且仅当i为素数。对于其它行,标记的位置也与该行行号的质因子有关。这是为什么呢?
照惯例,给个YouTube链接:http://youtube.com/watch?v=sbjPwyPT1AI
设f[i,j]表示第i行左起第j个位置是否有标记。j从0开始计数(即第i行最左边用f[i,0]表示)。对于每个f[i,j],我们将它的值赋给了f[i+j,j]和f[2*i-j,i]。也就是说,对于每组i和j,我们都进行以下两个操作:
f[i+j,j] <- f[i,j]
f[2*i-j,i] <- f[i,j]
而这实际上就是辗转相除的变形,不断递归下去后,最终f[i,j]表示的其实就是i和j是否互质。这样一来,上面那些东西就全解释清楚了。
用这种方法描述数论问题是一件很有趣的事,给人感觉很神奇。如果你感兴趣的话,这里有一个类似的例子,你可以看到Sierpinski三角形、杨辉三角和组合数的奇偶性是如何联系在一起的。
沙发
板凳
very impressive
interesting and impressive
留言很辛苦…总是说我验证码输错…..难道我算错了么
看了您的博客很厉害,很厉害!
牛人。
人与人的智商差别呀。感叹我笨。
我还是好好学习吧。
还是好好学习吧。
虽然你的思维相对于宇宙智慧来说只不过是汪洋中的一滴水,但这滴水却凝聚着海洋的全部财富;是质量上的一而非数量上的一;你的思维拥有一切宇宙智慧。