小小的停留之四 幸运数

到处停留的叶子

上次说到  小小的停留之三 “计算机之父” 天才的数学家冯·诺伊曼
看冯·诺伊曼的故事，他有句名言：“若人们不相信数学简单，只因他们未意识到生命之复杂。”
- m' P0 n. H/ n. A# V, {* D
+ h! [% v2 `2 T7 ^5 w8 N7 B他有个好朋友，据说是最好的朋友，是生于匈牙利的波兰犹太人数学家乌拉姆，这位先生曾参与曼克顿计划（核武器上有Teller-Ulam design，Teller指爱德华·泰勒）。他亦有参与研究核能推动的航天飞机。在纯数学上，遍历理论、数论、集合论和代数拓扑都有他的足迹。
: n7 a, n# a' W
) \2 c: u# o! P+ D9 E所以我在这里要说的幸运数不是中餐馆的饼干里给你的数字，也不是买彩票开奖的数字，而是在1955年波兰数学家乌拉姆提出的一个自然数列，用类似埃拉托斯特尼筛法的算法后留下的整数集合。
' p( i* U+ n4 t: B
' {. X" ^$ x% _# q2 m1 AIn number theory, a lucky number is a natural number in a set which is generated by a "sieve" similar to the Sieve of Eratosthenes that generates the primes.

' g' L' K! ^0 `& b" ?% e. T幸运数的定义
, v$ P4 }, c) B/ \8 V. B  xFORMULA       
Start with the natural numbers. Delete every 2nd number, leaving 1 3 5 7 ...; the 2nd number remaining is 3, so delete every 3rd number, leaving 1 3 7 9 13 15 ...; now delete every 7th number, leaving 1 3 7 9 13 ...; now delete every 9th number; etc.

具体一点来说说幸运数列怎么筛选出来的（喜欢数论的同学一定知道挑选素数的埃拉托斯特尼筛法，这个办法是类似的）

5 N3 T' g4 x& N9 ?2 ?3 W初始，从1开始的自然数列：
' F$ e! |" {% o4 t- I9 a& eBegin with a list of integers starting with 1:
1        2        3        4        5        6        7        8        9        10        11        12        13        14        15        16        17        18        19        20        21        22        23        24        25  ……

开始删除，在这个数列里，从2开始，首先是每隔2个数字，删除第二个数字。剩下来的数字是奇数~~
剩下的数列如下：
) L1 s7 }) E) ^7 [Every second number (all even numbers) is eliminated, leaving only the odd integers:
1                3                5                7                9                11                13                15                17                19                21                23                25  ……
; p0 E3 a  q7 ^/ d
8 m1 V( Z# [+ g' ~/ `" |接下来是3，每隔3个数字删除第三个。剩下的数列如下：
! n) B% j( O: q9 {; MThe second term in this sequence is 3. Every third number which remains in the list is eliminated:
/ e5 e& @1 k& f4 ~; ^+ Y1                3                                7                9                                13                15                                19                21                                25  ……
: C( G, |) J* z% N
现在接下来的数字是7，所以把上述数列中每第七个删除，剩下的数列是：
The next surviving number is now 7, so every seventh number that remains is eliminated:
1                3                                7                9                                13                15                                                21                                25  ……

接下来是9，……
这个过程可以一直无限继续下去，被幸运地留下来的数字就是幸运数。
& l0 N* Y% Y+ m4 Z
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99, ... (sequence A000959 in OEIS).
在OEIS编号为A000959的数列就是Lucky numbers
上述链接给了一个稍微长一点的幸运数列：
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99, 105, 111, 115, 127, 129, 133, 135, 141, 151, 159, 163, 169, 171, 189, 193, 195, 201, 205, 211, 219, 223, 231, 235, 237, 241, 259, 261, 267, 273, 283, 285, 289, 297, 303 ……
) {7 m+ r8 h& Z  ]
, M" _, O! l; q; i) ~有没有同样喜欢看数字的同学告诉我，你看了这个数列发现的是什么呢？
% H# r1 I" Q, H( r5 S
3 M) L- w# c3 U. g2 d2 k- a) F% U
/ z2 c+ G, H% y9 p4 A
& [2 J: G4 @/ m, i第一个短一点的数列，我发现，1，3，5，7的平方（1，9，25，49）都是幸运数，但9的平方81就不是，于是马上想，那么是不是只有奇素数的平方才是幸运数呢？答案是不，11的平方也不是。于是叶子的第一个猜想就在几秒里被叶子证明是错误的。

数论里的各种数列是数学里最容易上手理解的，不过最迷人最折磨人的也是它。著名的例子就是哥德巴赫猜想（Goldbach's conjecture）。
幸运数的挑选过程，类似上面提到过的埃拉托斯特尼筛法挑选素数的过程，同时也和这个著名猜想有关。
! }# W1 I' _8 o1 e4 O6 B另外幸运数也曾经在正式进入书面讨论的时候被建议叫做 "the sieve of Josephus Flavius"，因为它的挑选让大家想到著名的约瑟夫斯问题。

暂时就到这里吧，接下去要不要继续聊引出来的概念和问题呢？
- V0 D( p' a, o7 K6 o' P) `4 q
% l" H5 Y4 n2 T& N" p- Y: E; Y/ T**什么叫做Conjecture？
7 f, j2 o. c2 ^! M**约瑟夫斯问题。

到处停留的叶子

猜想（conjecture）和假说（Hypothesis）

. C$ O- J1 E, E4 Y) y" F1 \& y8 r猜想（conjecture）是一个看上去是真的，但尚未被证明的叙述。比如说上面提到的数学数列，因为它表现的没有规律和无限性，基于观察的某些结论，如果不能用科学逻辑的方法来证明在无限的未来它都是真的，那么之前所观察到的所有事实都仅仅是看上去是正确的。
- f$ [' d2 n2 O( V: y( O/ q
) X/ N3 d9 ~- t! C( {! s0 N2 `当猜想被证明后，它便会成为定理。猜想一日未成为定理，数学家都要小心在逻辑结构之中使用这些猜想。
4 U! h$ p+ k0 N* P$ ?* c8 T
猜想主要因为类比推理和偶然发现的巧合而出现。数学家通常会使用不完全归纳法，来测试自己的猜想。例如费马曾经根据首四个费马数是素数，便猜想所有费马数都是素数（此猜想已被推翻）

3 ?5 e) A" H" I5 |6 [0 G4 Q( E: D: a假说（Hypothesis），即指按照预先设定，对某种现象进行的解释，即根据已知的科学事实和科学原理，对所研究的自然现象及其规律性提出的推测和说明，而且数据经过详细的分类、归纳与分析，得到一个暂时性但是可以被接受的解释。任何一种科学理论在未得到实验确证之前表现为假设学说或假说。

$ q, H5 M0 r4 _( G* i4 p  N有的假设还没有完全被科学方法所证明，也没有被任何一种科学方法所否定，但能够产生深远的影响。如1900年德国物理学家马克斯·普朗克为解决黑体辐射谱而首先提出量子论（量子假说）。

农民家的狗

不明觉厉

到处停留的叶子

* x/ Z* I- y2 m& a9 g, k" N
6 K# H0 Q; e1 `**约瑟夫斯问题    都教授
" e& F! _5 ~, E
- G& U2 A' c8 t4 d8 w2 K我们来聊聊约瑟夫斯问题。
3 K0 K' O. ^4 J  m
有n个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。
) V8 ^; ]# i, y% f% z
问题是，给定了n和k，一开始要站在什么地方才能避免被处决？


, Y5 a1 h# ~  n; |0 Q% `---------------------------------------不思考的分割线---------------------------------------------
据说这个问题是一个经常出现在计算机算法中的问题，不过当年我读书的时候对它并没有特别注意。在计算机编程的算法中，类似问题又称为约瑟夫环。老兵和神牛肯定比我清楚得多。我就不多说什么算法了。牛教授 兵教授  

---------------------------------------历史八卦的分割线----------------------------------
0 p& j8 U( S9 D* r/ M这个问题是以弗拉维奥·约瑟夫斯命名的，他是1世纪的一名犹太历史学家。
据载，他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意。   

独角兽

到处停留的叶子 发表于 2014-7-17 06:50
**约瑟夫斯问题    都教授

, T3 A  V$ [8 r3 D; l我们来聊聊约瑟夫斯问题。

1. 经过努力学习，这题我能用java编程做了，oh yeah！
8 S1 g: g( W! x
2. 但叶子问我的不是编程。对于给定的k，我可以用倒推法硬推。但是，想了半天也没有想到不用推的直接算法。

推的方法如下：

3 q4 F1 {# m+ b* i  \' H7 fn=1，就一号，跑不掉的
n＝2， 要站 （k+1） 模 n 那一号设a(2)，比如 k=2, 则 a2=1 （号）; 若 k=3, 则 a2=2
) M$ i( m+ u3 c; t( N如此类推，n=i 时，要站在 a(i-1)+k 模 n 那一号。比如，k＝6， n＝19 时 要站在14号。


7 P; Q' G$ {, c! u- G+ c我算到k=6都找不出更直接的规律，不好玩

到处停留的叶子

独角兽 发表于 2014-7-16 20:30
* u) ~% L0 M% |1. 经过努力学习，这题我能用java编程做了，oh yeah！

2 z% Z3 {( C- P  [2 Z$ r2. 但叶子问我的不是编程。对于给定的k，我可以用 ...

6 \3 g$ ~& O& H4 C# L, O* L& g. }, j
2 e2 Y5 B8 q$ m1 s( w' \/ U兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答，或者先在网上找找看
: c4 I6 g" y- Q* W
, P6 r% h/ z$ w! i0 x在维基上看到K=2的解法和还有K≠2的通用解法，这里摘抄过来那段关于n的有趣分析。

5 @6 B6 f. U7 E还有下面我抄了两个通用算法，那个java的是不是和你做的一样啊？
  ^. a. k$ \" ]
" W3 U3 E) A7 `0 Z: r- H-----------------------------不动脑筋的分割线--------------------------

一个小心翼翼的Java例子：

1 p( J  ^) E7 t8 { int josephus(int n, int k) {
        return josephus(n, k, 1);
  }
  int josephus(int n, int k, int startingPoint) {
2 Z) m# Z0 @9 l( T! @; j! k5 N0 a& u      if(n == 1)
( e. M5 {3 i- Z! G8 s          return 1;
2 u2 Z6 p# k3 Z+ }" H$ V5 I      int newSp = (startingPoint + k - 2) % n + 1;

8 Q1 s" r  p: q( k* ~      int survivor = josephus(n - 1, k, newSp);
9 m# X# O# T" n      if (survivor < newSp) {
          return survivor;
, _6 l, V" t- m9 k      } else
          return survivor + 1;
7 u/ J0 X; Y9 y* J  }

另外有个更简洁的例子
( _5 C0 d$ ?9 f9 b  def josephus(n, k):
2 ^" \- W* l5 [    if n ==1:
      return 1
! u2 x6 U% @/ {4 e% N; Q5 o    else:
      return ((josephus(n-1,k)+k-1) % n)+1
# G. }! e* S5 j$ f- Z. A* i+ O
（如果n这个数字很大很大，k很小很小，电脑会不会转晕过去呢？）
0 s) e( D1 ~, _! X! Q
以上摘自 http://en.wikipedia.org/wiki/Josephus_problem#Solution
, n, c" q6 `) d" w' k

关于n的分析：
设f(n)为一开始有n个人时，生还者的位置。
如果一开始有偶数个人，则第二圈时位置为x的人一开始在第2x - 1个位置。因此位置为f(2n)的人开始时的位置为2f(n) - 1。这便给出了以下的递推公式：

f(2n)=2f(n)-1
如果一开始有奇数个人，则走了一圈以后，最终是号码为1的人被杀。于是同样地，再走第二圈时，新的第二、第四、……个人被杀，等等。在这种情况下，位置为x的人原先位置为2x+1。这便给出了以下的递推公式：

4 y& |/ k  G+ f* ?* q$ Z7 p! uf(2n+1)=2f(n)+1

1 @. p$ E. F9 H
如果我们把n和f(n)的值列成表，我们可以看出一个规律：
+ v% j' l% K+ E% o& |6 H" w; V
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
1 U  G# }: \5 |: m
从中可以看出，f(n)是一个递增的奇数数列，每当n是2的幂时，便重新从f(n)=1开始。因此，如果我们选择m和l，使得n=2^m+l且0≤ l<2^m，那么f(n)=2 . l+1。显然，表格中的值满足这个方程。可以用数学归纳法给出一个证明。
$ i9 ]# J9 Q2 b- x6 T9 W
定理：如果n=2^m+l且0≤ l<2^m，则f(n) = 2.l+1。

9 a* E! O2 W, j! G
, r& T( M) b( k答案的最漂亮的形式，与n的二进制表示有关：把n的第一位移动到最后，便得到f(n)。这可以通过把n表示为2^m+l来证明。

独角兽

到处停留的叶子 发表于 2014-7-17 11:02
5 ~- `" u1 f4 A2 i+ J兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答，或者先在网上找找看

在 ...

我的推法就是这个：

  return ((josephus(n-1,k)+k-1) % n)+1
% @2 N! {6 }: c1 j7 o! W8 C/ n
我有一点疏忽是如果整除，模的结果是0，但实际应该取n。所以这个表达式把 "+1"搞到括号外面就完全对了。

2的情况我没单拿出来搞。

leekai

绕死了

常挨揍

看不懂
9 O; g( t, `; B6 u  G8 C4 o& l不过今天不幸运数是17

到处停留的叶子

常挨揍 发表于 2014-7-18 09:40
看不懂
不过今天不幸运数是17

8 w: s4 ~' @; G) |5 `* P( l  E" T7月17日成了一个黑色的日子。很让人感觉生命无常。
- J$ a: H8 H8 }( b8 i5 [
, ?9 V1 j, n- B# D3 x8 ]; R以后出行挑日子，要找一个幸运数的交集，这里前面的9个数字也可以参考一下：1，3，7，9，13，15，21，25，31
* |4 R( G; |, y7 s: `
  K; O! H5 m5 b, T" a13号如果遇上星期五，还是算了，不要不信邪。