不能回到起点

liexi20101117

上中学时，好像计算机课本上有道题材，大致意思好像是这样说的： 　　一个圆上有N个点，假如从某一点A开始，先间隔一个点跳跃，再间隔两个点跳跃，再间隔三个点跳跃，以此类推，按这个规律，经过一千次后不会跳跃到起始那个点A上。这个N最小为多少？ 当时刚学程序，不懂，后来又没时间学习了（呵呵，因工作谋生呀） 真的有这样的N吗

mjs1wh

这样的N肯定存在，难点是要求最小值

hujunhua

1、如果仅仅要求是作为结果的第1000跳不与起点重合, 那没什么难的. 2、如果是要求过程中的每一跳都不与起点重合, 则可编程来解决。直接计算也可以。 设起点为0，那么第1跳到2，第2跳到5，第3跳到9，...，第n跳到n(n+3)/2，...， 第1000跳到500×1003. 对于第1种题设，就是要找不能整除500×1003的最小N，N=3就可以了。 对于第2种题设，就是要找一个不能整除这个数列中的任何一项的最小N。由于通项公式n(n+3)/2可分解为两项之积，手工找起来也不难。显然，N就是1003之后最小素数1009. 因为对于合数N，二次同余方程n(n+3)/2≡0(mod N)总是存在小于N的解，所以1009以下的合数都不行。

liexi20101117

胡版主，太强了。谢谢了。 不过，版主，我原本想问的题目是我的推广的问题： 一个圆上有N个点，假如从某一点A开始，先间隔一个点跳跃，再间隔两个点跳跃，再间隔三个点跳跃，以此类推，按这个规律，经过M次后始终有一个点B不会被经过。 这个M，N最小为多少？ 点B存在吗

hujunhua

不存在求$M_{min}$的问题, 没有意义 对于给定的$M, N_{min}=(M+3)$之后的最小素数

liexi20101117

呵呵，是呀，我写错了，原本想问是说M有最大值吗？ 那么我还有三个想法： 1、请问点B是从点A开始后的第几个点，与M和/或N有什么关系吗。 2、N和跳跃方式规定后，点B是固定的吗? 3、有M趋于无穷的点B存在吗？

mjs1wh

按胡版主的思路，就是个整除的问题，应该不难解决的，

liexi20101117

胡版，mjs1wh,两位老师： 为什么你们不能帮我把6楼的答案或分析情况结论写一下呢，我也写不出什么好的问题让大家讨论与分享。不过，这个学生时代的问题一直在我心头呀。 真心希望两位或其它的老师与高手有时间帮我解决下6楼的的问题。期待中。

hujunhua

一、给定B和N后，可求最大M。先解同余方程n(n+3)/2≡B(mod N) 1、方程有解，就有最小正解m(03并且为2的幂时。证明如下： 设第x跳与第y跳会踩到同一点，即x(x+3)/2≡y(y+3)(mod N), 那么 (x-y)(x+y+3)/2≡0(mod N), ………………（有事出去，你自己往下做做看）

liexi20101117

好的，我照您说的做下. 但例1：N=7，数列n(n+3)/2(mod7)为2，5，2，0，6，6，0，2，5，2，0，6，6，0，…，即B=1，3，4时永远不会被踩到。 这句话，是不是说，有可能有多个点在一定条件下（或永远）不会被踩到呀