前面文章我們介紹了約瑟夫問題，并給出了基本的數學模型，和其内部數學性質的分析。
今天我們接着上期的問題分析把整個過程的數學細節都描繪下來，注意今天的描繪的粒度是每一次對整個序列的周遊，而第一篇描述的時候是每一次行動。但是，這次更加粗粒度的角度沒有抹去任何細節，反而抓住了更加深刻的規律，利用了剔除過程中每個周期内的周期性，或者說是同餘性質，我們一點點來看。
我們依然用有限狀态自動機模型來模組化，考慮k = 2的情況。我們考察的初始狀态設定為S0 = (1b1b2......bm, 0)，兩個值分别是餘下人數和初始相位，0為原始約瑟夫過程，1為跳過其第一步的過程。每次輸出的是前一個狀态的相位值，對應當次能留下的末位值條件，根據上一篇的分析，其狀态變化過程為：
O1 = S0_2 = 0;
S1 = (1b1b2......b(m - 1), 0) if bm = 0;
S1 = (1b1b2......b(m - 1) + 1, 1) if bm = 1;
O2 = S1_2 = bm;
S2 = (1b1b2......b(m - 2), 0) if b(m - 1) = 0;
S2 = (1b1b2......b(m - 2), 1) if b(m - 1) = 1, bm = 0;
S2 = (1b1b2......b(m - 2) + 1, 1) if b(m - 1) = 1, bm = 1;
O3 = S2_2 = b(m - 1)
......
Si = (1b1b2......b(m - i), 0) if b(m - (i - 1)) = 0;
Si = (1b1b2......b(m - i), 1) if b(m - (i - 1)) = 1;
Si = (1b1b2......b(m - i) + 1, 1) if b((m - (i - 1)):m) = 1;
Oi = S(i - 1)_2 = b(m - (i - 1));
S(m - 1) = (1b1, 0) if b2 = 0;
S(m - 1) = (1b1, 1) if b2 = 1;
S(m - 1) = (1b1 + 1, 1) if b(2:m) = 1;
O(m - 1) = S(m - 2)_2 = b2;
Sm = (1, 0), if b1 = 0;
Sm = (1, 1), if b1 = 1;
Sm = (10, 1), if b(1:m) = 1;
Om = S(m - 1)_2 = b1;
綜上，每一次的輸出序列為0，bm， b(m - 1)，……，b1，那麼倒轉以後的b1b2,......,bm0，即為所求。由此還可以知道，如果b1 = 1，倒數第2個去掉的是b2b3,......,bm0；若b1 = 0，則對應的1b2b3,......,bm0一定不小于n，下一個去掉的索引超出了範圍，取不到；而再接下去的則是以b3b4,......,bm0結尾，範圍在内的按大小順序倒序取所有(n - 1)範圍内的值（因為在一個周期内先拿走小的再到大的，大的會在這個周遊輪次留到後面的位置被去掉），以此類推。
我的天，我原本以為美妙的結論背後一定也有簡潔的推導，看來我想多了。不過，過程艱難，結論優雅也是數學常有的特點了。
在實際使用中，和約瑟夫過程相關的發牌其實有很多變種，常見的就是第一張到底是留還是發的差別，等效為預先處理掉相位錯位部分再開始就可以了。另外，也可以每次把牌依次發成兩疊，每次取特殊一疊則代表一個周遊周期内選取的相位，而下一階段的發牌則等價于從這些發出去的牌中重新開始，并且存在一個倒序和相位的重新歸零。同樣，這種結局很好模拟，但是寫出通項公式很困難，可能我們發明的數學運算符号，還不夠多。最後，完美洗牌的逆過程其實和一次k = 2的一個周遊周期也有相通之處，隻不過被剔除的那些牌增加了一個倒序操作，可以見得在同樣的數學結構背後，表面的世界可以多麼豐富多彩。
以上是k = 2的，也是最常用的情況。但當我用類似的思路想拓展到k > = 3的時候，希望也能有類似的公式結論，但發現複雜程度要遠遠大些。
拿k = 3為例，此時相位值取0，1，2，表示從第幾步開始執行過程。這還好說，其值和n(mod 3)直接密切相關。但是，在第二輪的時候，把這些數重新化為連續自然數就不那麼容易了，它不像k = 2那樣非黑即白，而是一輪過後，會形模3周期為2的序列，再過一輪，就更加混亂，需要更長的周期才能描述清楚了。關鍵是周期的增長我暫時也觀察沒找到很好的規律，用上三進制表達，也遠非移位那麼簡單，除非，每次殺2人留1人，才能對上前面的推導。
是以，原本可用的以周遊一次為周期的劃分方式已經不能很好地歸約這個過程。但仍然有這麼好的周期規律，怎樣使用能夠讓我們的運算化簡呢？我們不妨換個思路，以一次周遊到最後一個被剔除的元素為止為一個過程，然後直接以相同的相位開啟下一個周期。此時，每次周遊的元素不包括序列末尾取餘數多出來的幾個，相當于要在序列上做一次首尾片段的平移才能等效接下來的操作，但一個令人驚喜的好處是，再也不用糾結相位的變化帶來的混亂變化了。這樣雖然還是寫不出通項公式，但是能夠寫出比較優雅的遞推關系式了。
從遞歸角度講，第一次剔除人的編号必然是(k - 1)，那麼新的序列為k, k + 1, ......, (n - 1), 0, 1, ......, (k - 2)，此序列的長度為(n - 1)，這麼多元素的解為f(n - 1, k)，但是這個解是以0:(n - 1)為基準的。是以我們隻需要對這二者的索引對應關系表達即可（不是個完整的集合到自身的映射，故非置換）：
k, k + 1, ......, (n - 1), 0, 1, ......, (k - 2)
0, 1, 2......, n - 1 - k, n - k, ......, n - 2
顯然，+ k (mod n)，即為所求，可看作原序列向左循環移位了k個機關（左移，而且溢出的位遞補到首位上），對原本對應不上的多的一個元素(k - 1)，恰好删除掉了。是以完成了這兩個序列的比對，寫成式子就是：
f(n, k) = (f(n - 1, k) + k) (mod n)
當k < n的時候，也即，一個周遊過程可能删除超過1個元素時，我們可以按規律合并處理，在這樣一個次周期内（次的意思是，大多數時候并未真的走完一個周期），删除結果為：
[n / k]k,......, (n - 1)
0, 1, ......, k - 2,
k, k + 1, ......, 2k - 2,
......
([n / k] - 1)k, [n / k]k - 2.
當k | n時，第一行不存在。
是以我們面臨的新問題的n’= n - [n / k]，我們隻要搞定兩個相同長序列的轉化問題，問題就得解了。
首先，如果想把新序列的0和同長度n'的自然序列對齊，需要向左循環移位的數量是n - 1 - [n / k]k + 1 = n - [n / k]k = n % k，相當于每個數模n’減這麼多，就可以得到啥也不删除，僅修改相位的結果。而删除部分怎麼算呢？
實際的規律其實是，自然序列每增加(k - 1)新序列增加k，這時整體趨勢，也就是說，乘以k / (k - 1)可以使得每個周期的第一個元素恰好相等，而後面的元素每次都會多增加1 / (k - 1)，一直增加（k - 2）次到(k - 2) / (k - 1)，直到下一個元素因為删除跳過一個索引，一次性追回來這1個機關，又回到同一起跑線。注意這個數到此之前都不到1。是以這個函數恰好可以用高斯函數表達：
f(n, k) = [k / (k - 1)((f(n’, k) - n % k)mod n’)]
于是，整個約瑟夫問題求解的，複雜度降低為O(klogn)的遞歸表達式如下：
f(n, k) =
[k / (k - 1)((f(n’, k) - n % k)mod n’)], k < n, n >= 2,
(f(n - 1, k) + k) (mod n), 2 <= n <= k,
0, n = 1
k >= 2
于是，在周期性的數學性質幫助下，我們找到了更深層次的約瑟夫問題的求解政策，大大降低了問題的時間複雜度。另外，對于k = 2情況，似乎是某種巧合達成了優雅的結論，并且很容易擴充出求倒數第n個剔除的元素是多少。最後，我拿着這個公式研究了一下k = 3和更大值時候的情況，發現了一些規律，但是确實也不像2那樣容易地寫出通項公式，找到優雅地表示形式了。你如果找到了，希望你能分享給我。
以上就是約瑟夫問題數學部分的全部内容，從下一篇起，我們進入魔術部分，看看這一神奇的結構能夠怎樣配合上我們的魔術表演，去繼續締造屬于我們的奇迹。