不能回到起点

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(0<m<N). 要使B点不被前M跳踩到，最多只能跳m-1下，即必须M<m，因为第m跳会踩到B点。
2、如果方程无解，那么一直跳下去都不会踩到点B，即M可趋向无穷。这是可能的，因为二次多项式数列一般不能覆盖N的完全同余系。但是需要具体问题具体分析。
例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时永远不会被踩到。
例2：N=8，数列n(n+3)/2(mod8)为2，5，1，6，4，3，3，4，6，1，5，2，0，7，7，0（以下循环），可见不存在永远踩不到的B点。
这就有一个问题：对于这种跳跃方式，圆圈上的点数N为多少时存在永远踩不到的B点？答案是N>3并且为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时永远不会被踩到。
这句话，是不是说，有可能有多个点在一定条件下（或永远）不会被踩到呀