小小的停留之四 幸运数

到处停留的叶子

上次说到  小小的停留之三 “计算机之父” 天才的数学家冯·诺伊曼
看冯·诺伊曼的故事，他有句名言：“若人们不相信数学简单，只因他们未意识到生命之复杂。”
, n! D0 V' j8 p& T3 U+ A
他有个好朋友，据说是最好的朋友，是生于匈牙利的波兰犹太人数学家乌拉姆，这位先生曾参与曼克顿计划（核武器上有Teller-Ulam design，Teller指爱德华·泰勒）。他亦有参与研究核能推动的航天飞机。在纯数学上，遍历理论、数论、集合论和代数拓扑都有他的足迹。

所以我在这里要说的幸运数不是中餐馆的饼干里给你的数字，也不是买彩票开奖的数字，而是在1955年波兰数学家乌拉姆提出的一个自然数列，用类似埃拉托斯特尼筛法的算法后留下的整数集合。

In 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.
8 k3 F0 \4 Q8 m5 ]
; f7 h" i+ Z. Y4 ?" ]. {幸运数的定义
FORMULA       
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.
! l6 U* M& @4 ^
具体一点来说说幸运数列怎么筛选出来的（喜欢数论的同学一定知道挑选素数的埃拉托斯特尼筛法，这个办法是类似的）
1 W: o, r6 s3 v. @/ ^- ?. M0 ?+ N' x  Z
+ }: S6 @/ v3 _. o/ l" S! Q初始，从1开始的自然数列：
& _& v6 g/ Q' F7 Q6 `# g* s2 }Begin with a list of integers starting with 1:
6 U1 V% ?) h, h9 B- g1        2        3        4        5        6        7        8        9        10        11        12        13        14        15        16        17        18        19        20        21        22        23        24        25  ……
5 }6 u: z0 }& |2 V
开始删除，在这个数列里，从2开始，首先是每隔2个数字，删除第二个数字。剩下来的数字是奇数~~
剩下的数列如下：
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  ……
- r" o, p2 d7 x( K$ w
接下来是3，每隔3个数字删除第三个。剩下的数列如下：
. h, B. l; F: H0 Y: I; gThe second term in this sequence is 3. Every third number which remains in the list is eliminated:
$ n1 t; k7 T* n3 {; S+ l1                3                                7                9                                13                15                                19                21                                25  ……
6 M3 ~0 ~) C4 P/ k) n+ Q, x; T
现在接下来的数字是7，所以把上述数列中每第七个删除，剩下的数列是：
; G6 N9 r9 m- x9 @1 gThe next surviving number is now 7, so every seventh number that remains is eliminated:
4 `# S% w! }; ?1 e( ^1                3                                7                9                                13                15                                                21                                25  ……

2 B2 O+ }9 S8 `7 J9 v接下来是9，……
这个过程可以一直无限继续下去，被幸运地留下来的数字就是幸运数。
. r: `* }& G% l
9 U/ X9 d: G7 \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
4 G# x7 k+ I- Z2 e. ?8 D( U上述链接给了一个稍微长一点的幸运数列：
- V, q, T- n$ S1, 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 ……
8 R" u6 [$ U% `, N0 L
有没有同样喜欢看数字的同学告诉我，你看了这个数列发现的是什么呢？



+ f* l6 W" Y" v0 t4 P第一个短一点的数列，我发现，1，3，5，7的平方（1，9，25，49）都是幸运数，但9的平方81就不是，于是马上想，那么是不是只有奇素数的平方才是幸运数呢？答案是不，11的平方也不是。于是叶子的第一个猜想就在几秒里被叶子证明是错误的。
7 r' [2 p# P# d2 N, @$ T
) d! r- D5 ~% }$ p数论里的各种数列是数学里最容易上手理解的，不过最迷人最折磨人的也是它。著名的例子就是哥德巴赫猜想（Goldbach's conjecture）。
$ U7 \. `: j2 l; s5 @8 F/ v幸运数的挑选过程，类似上面提到过的埃拉托斯特尼筛法挑选素数的过程，同时也和这个著名猜想有关。
另外幸运数也曾经在正式进入书面讨论的时候被建议叫做 "the sieve of Josephus Flavius"，因为它的挑选让大家想到著名的约瑟夫斯问题。

暂时就到这里吧，接下去要不要继续聊引出来的概念和问题呢？
/ d  W4 D4 ~, n' u8 w! @" Q' E, d
**什么叫做Conjecture？
/ w1 ^6 a3 ?: G**约瑟夫斯问题。

到处停留的叶子

猜想（conjecture）和假说（Hypothesis）
  o8 P3 a7 y! X4 G
猜想（conjecture）是一个看上去是真的，但尚未被证明的叙述。比如说上面提到的数学数列，因为它表现的没有规律和无限性，基于观察的某些结论，如果不能用科学逻辑的方法来证明在无限的未来它都是真的，那么之前所观察到的所有事实都仅仅是看上去是正确的。
9 H- r5 d+ R5 n5 o% ]; F2 k5 k. O
1 Y0 Q* ?! B& H& F. N" S当猜想被证明后，它便会成为定理。猜想一日未成为定理，数学家都要小心在逻辑结构之中使用这些猜想。

7 i, i8 }+ @- l% P. w8 }: I. Y猜想主要因为类比推理和偶然发现的巧合而出现。数学家通常会使用不完全归纳法，来测试自己的猜想。例如费马曾经根据首四个费马数是素数，便猜想所有费马数都是素数（此猜想已被推翻）
6 @; [& r. j4 u3 ]
) l! n) N3 B7 S. ^& B- G假说（Hypothesis），即指按照预先设定，对某种现象进行的解释，即根据已知的科学事实和科学原理，对所研究的自然现象及其规律性提出的推测和说明，而且数据经过详细的分类、归纳与分析，得到一个暂时性但是可以被接受的解释。任何一种科学理论在未得到实验确证之前表现为假设学说或假说。
8 O1 L: y# v7 k& k
5 ?6 {! K) ]. j1 G3 I2 E有的假设还没有完全被科学方法所证明，也没有被任何一种科学方法所否定，但能够产生深远的影响。如1900年德国物理学家马克斯·普朗克为解决黑体辐射谱而首先提出量子论（量子假说）。

农民家的狗

不明觉厉

到处停留的叶子

% [9 Z! y' g; ^" \9 d* n: p**约瑟夫斯问题    都教授

我们来聊聊约瑟夫斯问题。

' \7 V1 N2 v; `3 _有n个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。
8 w6 ]$ U9 `6 z: \( y
问题是，给定了n和k，一开始要站在什么地方才能避免被处决？

$ l3 w' P/ Q" U6 _0 ~# Y0 q
4 j$ l( N! A9 J( D) _3 K% c4 c5 p---------------------------------------不思考的分割线---------------------------------------------
据说这个问题是一个经常出现在计算机算法中的问题，不过当年我读书的时候对它并没有特别注意。在计算机编程的算法中，类似问题又称为约瑟夫环。老兵和神牛肯定比我清楚得多。我就不多说什么算法了。牛教授 兵教授  

/ }5 w- [% W  R( _' p8 D---------------------------------------历史八卦的分割线----------------------------------
) a+ i) `. c7 P- m9 Q" X* ]这个问题是以弗拉维奥·约瑟夫斯命名的，他是1世纪的一名犹太历史学家。
据载，他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意。   

独角兽

到处停留的叶子 发表于 2014-7-17 06:50
! @  y3 I$ t/ F0 x5 s! L. Y' \1 a**约瑟夫斯问题    都教授

我们来聊聊约瑟夫斯问题。

$ U, B3 ~: k. v) i1 G; @1. 经过努力学习，这题我能用java编程做了，oh yeah！

2. 但叶子问我的不是编程。对于给定的k，我可以用倒推法硬推。但是，想了半天也没有想到不用推的直接算法。

% o9 s' j2 P  q5 U+ F! r0 i推的方法如下：
* g" R. X. V/ ?2 u
1 B6 I, _  s4 X+ Rn=1，就一号，跑不掉的
n＝2， 要站 （k+1） 模 n 那一号设a(2)，比如 k=2, 则 a2=1 （号）; 若 k=3, 则 a2=2
如此类推，n=i 时，要站在 a(i-1)+k 模 n 那一号。比如，k＝6， n＝19 时 要站在14号。

2 ]+ z  X8 E# t$ q! y' W+ t
我算到k=6都找不出更直接的规律，不好玩

到处停留的叶子

独角兽 发表于 2014-7-16 20:30
- \+ ^' k' t- k9 U/ l1. 经过努力学习，这题我能用java编程做了，oh yeah！

2. 但叶子问我的不是编程。对于给定的k，我可以用 ...

! B1 g; {  t$ r: c# I* g
兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答，或者先在网上找找看
7 q! k0 G, |! C3 Q0 W1 R
在维基上看到K=2的解法和还有K≠2的通用解法，这里摘抄过来那段关于n的有趣分析。
. J5 `  I! w3 w/ z- }1 `3 N
还有下面我抄了两个通用算法，那个java的是不是和你做的一样啊？

% G) J# j1 h" H, d# h% g3 K" `-----------------------------不动脑筋的分割线--------------------------
' J$ u- d7 T* E! \2 ~
一个小心翼翼的Java例子：

int josephus(int n, int k) {
  h- Z  k6 @; a$ s2 c. j, W        return josephus(n, k, 1);
  }
  int josephus(int n, int k, int startingPoint) {
      if(n == 1)
0 z, A8 P# h9 R+ t2 ]: `% @' [          return 1;
" s" [0 k. ^: m" T  o& q) h      int newSp = (startingPoint + k - 2) % n + 1;

& P; m( `$ O) K& n* t( c% y( T* X  c      int survivor = josephus(n - 1, k, newSp);
      if (survivor < newSp) {
          return survivor;
  |4 }; ^1 l! I" P      } else
" L, V" j9 F7 Y$ c. R0 v* ~( b          return survivor + 1;
5 a+ M: g0 H. f$ g, Q  }

) |4 w) Q/ c* f' d. p4 T1 t/ b另外有个更简洁的例子
  def josephus(n, k):
, O$ O6 c4 _! C/ a. A$ r5 Y    if n ==1:
      return 1
    else:
5 N! U0 D# l$ j* S      return ((josephus(n-1,k)+k-1) % n)+1
* m8 H% A- D  ?% a, b5 A. c
（如果n这个数字很大很大，k很小很小，电脑会不会转晕过去呢？）
6 W5 x+ e8 E* K+ B; V3 b" s: Z" N
* H5 k' G0 C; A0 z( {; t; z0 r以上摘自 http://en.wikipedia.org/wiki/Josephus_problem#Solution


) p; h( B/ k; ^9 ~% g+ v3 B关于n的分析：
& l5 n: w' n7 d4 O# W设f(n)为一开始有n个人时，生还者的位置。
如果一开始有偶数个人，则第二圈时位置为x的人一开始在第2x - 1个位置。因此位置为f(2n)的人开始时的位置为2f(n) - 1。这便给出了以下的递推公式：

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

1 o3 h* `" G7 [' ^f(2n+1)=2f(n)+1


如果我们把n和f(n)的值列成表，我们可以看出一个规律：
5 Z% U/ m; M! `7 A+ J4 m; p0 u- j# y
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≤ l<2^m，那么f(n)=2 . l+1。显然，表格中的值满足这个方程。可以用数学归纳法给出一个证明。
. \; R7 W1 p8 R6 x* Q
定理：如果n=2^m+l且0≤ l<2^m，则f(n) = 2.l+1。

0 v6 H, ?* J) Z- i6 _
答案的最漂亮的形式，与n的二进制表示有关：把n的第一位移动到最后，便得到f(n)。这可以通过把n表示为2^m+l来证明。

独角兽

到处停留的叶子 发表于 2014-7-17 11:02
/ \4 y5 d/ }3 x& m2 e兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答，或者先在网上找找看

9 \6 C* |/ N: P* t( q0 ]$ H在 ...

! ?  G6 q3 |- m; H! j: d我的推法就是这个：
3 V1 y+ U* |# F( a5 ^
% U% s+ D& N8 U1 ~- R  return ((josephus(n-1,k)+k-1) % n)+1
" u! H8 s$ w3 l6 ?* Z
我有一点疏忽是如果整除，模的结果是0，但实际应该取n。所以这个表达式把 "+1"搞到括号外面就完全对了。
+ W! s( ^* n" [& s  x
5 J6 B' q. m% v+ X; H6 b9 ~2的情况我没单拿出来搞。

leekai

绕死了

常挨揍

看不懂
不过今天不幸运数是17

到处停留的叶子

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

. d9 X, ]. Z* V4 Y2 h" Q( @# h! ^7月17日成了一个黑色的日子。很让人感觉生命无常。
' K0 Q5 s4 U( P& j" \1 B- I
以后出行挑日子，要找一个幸运数的交集，这里前面的9个数字也可以参考一下：1，3，7，9，13，15，21，25，31
3 y. W, l0 R' k9 G
13号如果遇上星期五，还是算了，不要不信邪。