循环数列

APPSYZY

给定数字$N$与$m$，表示在数列$1,2,\cdots,N-1,N$中从$1$开始，每$m$个数取出一个，直到取完为止，最终生成新的数列。
例如，当$N=17$，$m=5$时，得到的数列为：$1,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,7$。
求对于$N$和$m$相对应的生成数列的通项公式。

APPSYZY

原题是：对于给定的正整数N和k，求最小的m使得数列的最后一项为k，在上面的例子里，就是对于给定的N=17和k=13，最小的m求出来是7，不知有没有通法

APPSYZY

查了查发现，它和一个叫约瑟夫问题（Josephus Problem）的解决方法很像，但是资料里都没有找到通项公式的

APPSYZY

现在有点怀疑，是不是只有递推公式而没有通项公式

realnumber

回复 4# APPSYZY


    估计是了，
搜索到三个算法，（也许你也看过了）最后一种没明白，前2种比较好懂.
blog.csdn.net/ZHOUBEISI/article/details/52314603

APPSYZY

回复 5# realnumber
$a_1=0$
$a_n=(a_{n-1}+m) \mod i$
估计是求不出通项公式的

hbghlyj

zh.wikipedia.org/wiki/约瑟夫斯问题

我们将明确解出$k=2$时的问题。对于$k\neq 2$的情况，我们在下面给出一个一般的解法。

设$f(n)$为一开始有$n$个人时，生还者的位置(注意：最终的生还者只有一个)。走了一圈以后，所有偶数号码的人被杀。再走第二圈，则新的第二、第四、……个人被杀，等等；就像没有第一圈一样。

如果一开始有偶数个人，则第二圈时位置为$x$的人一开始在第$2x - 1$个位置。因此位置为$f(2n)$的人开始时的位置为$2f(n) - 1$。这便给出了以下的递推公式：$$f(2n)=2f(n)-1.\,$$
如果一开始有奇数个人，则走了一圈以后，最终是号码为1的人被杀。于是同样地，再走第二圈时，新的第二、第四、……个人被杀，等等。在这种情况下，位置为$x$的人原先位置为$2x+1$。这便给出了以下的递推公式：$$f(2n+1)=2f(n)+1.\,$$如果我们把$n$和$f(n)$的值列成表，我们可以看出一个规律：

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$f(n)$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

从中可以看出，$f(n)$是一个递增的奇数数列，每当$n$是2的幂时，便重新从$f(n)=1$开始。因此，如果我们选择$m$和$l$，使得$n=2^m+l$且$0\leq l<2^m$，那么$f(n)=2 \cdot l+1$。注意：$2^m$是不超过$n$的最大幂，$l$是留下的量。显然，表格中的值满足这个方程。我们用数学归纳法给出一个证明。

定理：如果$n=2^m+l$且$0\leq l<2^m$，则$f(n) = 2l+1$。

证明：对$n$应用数学归纳法。$n=1$的情况显然成立。我们分别考虑$n$是偶数和$n$是奇数的情况。

如果$n$是偶数，则我们选择$l_1$和$m_1$，使得$n/2 = 2^{m_1}+l_1$，且$0\leq l_1 < 2^{m_1}$。注意$l_1 = l/2$。我们有$f(n) = 2f(n/2)-1=2((2l_1)+1) - 1=2l+1$，其中第二个等式从归纳假设推出。

如果$n$是奇数，则我们选择$l_1$和$m_1$，使得$(n-1)/2 = 2^{m_1}+l_1$，且$0\leq l_1 < 2^{m_1}$。注意$l_1 = (l-1)/2$。我们有$f(n) = 2f((n-1)/2)+1=2((2l_1)+1) + 1=2l+1$，其中第二个等式从归纳假设推出。证毕。

---

一般情况下，考虑生还者的号码从$n-1$到$n$的变化, 我们可以得到以下的递推公式(编号从0开始)：

$f(n,k)=(f(n-1,k)+k) \bmod n$，$f(1,k)=0$

hbghlyj

答案的最漂亮的形式，与$n$的二进制表示有关：把$n$的第一位移动到最后，便得到$f(n)$。如果$n$的二进制表示为$n=b_0 b_1 b_2 b_3\dots b_m$，则$f(n)=b_1 b_2 b_3 \dots b_m b_0$。
证明：首先$b_0=1$，把$n$表示为$2^m+l$，其中$l=b_1 b_2 b_3 \dots b_m$，所以$2l=b_1 b_2 b_3 \dots b_m 0$，$f(n)=2l+1=b_1 b_2 b_3 \dots b_m b_0$。