小小的停留之四 幸运数

到处停留的叶子

上次说到  小小的停留之三 “计算机之父” 天才的数学家冯·诺伊曼
看冯·诺伊曼的故事，他有句名言：“若人们不相信数学简单，只因他们未意识到生命之复杂。”

他有个好朋友，据说是最好的朋友，是生于匈牙利的波兰犹太人数学家乌拉姆，这位先生曾参与曼克顿计划（核武器上有Teller-Ulam design，Teller指爱德华·泰勒）。他亦有参与研究核能推动的航天飞机。在纯数学上，遍历理论、数论、集合论和代数拓扑都有他的足迹。

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

! Z- V4 c6 U9 ]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.
, F* V7 q! ?7 ?- `- \& O
" y, T: |" A1 _% Q5 s6 x幸运数的定义
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.
: E  ^- f% {4 c# P+ R* [
具体一点来说说幸运数列怎么筛选出来的（喜欢数论的同学一定知道挑选素数的埃拉托斯特尼筛法，这个办法是类似的）

初始，从1开始的自然数列：
/ _' I  Z% C9 f# N% O$ C  W( ?Begin with a list of integers starting with 1:
/ T' A: J3 U' T5 i# z1        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个数字，删除第二个数字。剩下来的数字是奇数~~
  q! g# S* o5 Y/ }剩下的数列如下：
9 c+ c3 _: W$ W$ a4 c( `$ ]Every second number (all even numbers) is eliminated, leaving only the odd integers:
) z9 H9 U3 ^7 s, t8 q4 y5 @1                3                5                7                9                11                13                15                17                19                21                23                25  ……

接下来是3，每隔3个数字删除第三个。剩下的数列如下：
The second term in this sequence is 3. Every third number which remains in the list is eliminated:
0 P+ ?3 R* _3 t$ Z+ I# P9 p1                3                                7                9                                13                15                                19                21                                25  ……
# N0 c; [# F  |
- G2 y8 |3 D, ]+ Z- J5 `6 `: K现在接下来的数字是7，所以把上述数列中每第七个删除，剩下的数列是：
% W. v& j- _0 yThe next surviving number is now 7, so every seventh number that remains is eliminated:
1                3                                7                9                                13                15                                                21                                25  ……
+ [# l' O' }- F# ^
接下来是9，……
这个过程可以一直无限继续下去，被幸运地留下来的数字就是幸运数。

9 R$ t6 F' q( A& ^' ^1 ~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).
" b: r) M7 X* s$ J. I1 ^在OEIS编号为A000959的数列就是Lucky numbers
上述链接给了一个稍微长一点的幸运数列：
* ?& C1 O5 N0 Q+ n3 M3 K5 o1, 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 ……

有没有同样喜欢看数字的同学告诉我，你看了这个数列发现的是什么呢？
/ R0 ^+ c9 R0 ?
0 E4 M/ Y: ], y" c" F- g% F! Z
5 K" R0 N1 p2 k. u
( H; a) }% A/ K% v4 y2 x第一个短一点的数列，我发现，1，3，5，7的平方（1，9，25，49）都是幸运数，但9的平方81就不是，于是马上想，那么是不是只有奇素数的平方才是幸运数呢？答案是不，11的平方也不是。于是叶子的第一个猜想就在几秒里被叶子证明是错误的。
( R$ I! }2 p3 N, n6 h$ s' J/ h* W4 s
( |) F& t2 u$ T数论里的各种数列是数学里最容易上手理解的，不过最迷人最折磨人的也是它。著名的例子就是哥德巴赫猜想（Goldbach's conjecture）。
% G1 {" V1 c7 s幸运数的挑选过程，类似上面提到过的埃拉托斯特尼筛法挑选素数的过程，同时也和这个著名猜想有关。
另外幸运数也曾经在正式进入书面讨论的时候被建议叫做 "the sieve of Josephus Flavius"，因为它的挑选让大家想到著名的约瑟夫斯问题。
1 [/ o* L5 M. F+ Z# ^
, O* M' u( q# \1 v1 k4 l暂时就到这里吧，接下去要不要继续聊引出来的概念和问题呢？

& Q9 z! }& [$ h- r  q- Z. ~**什么叫做Conjecture？
**约瑟夫斯问题。

到处停留的叶子

猜想（conjecture）和假说（Hypothesis）
1 H% w1 A; m' P9 ?! Q3 J
猜想（conjecture）是一个看上去是真的，但尚未被证明的叙述。比如说上面提到的数学数列，因为它表现的没有规律和无限性，基于观察的某些结论，如果不能用科学逻辑的方法来证明在无限的未来它都是真的，那么之前所观察到的所有事实都仅仅是看上去是正确的。
2 G' f* I8 c1 z, [/ E# ]* M; [
当猜想被证明后，它便会成为定理。猜想一日未成为定理，数学家都要小心在逻辑结构之中使用这些猜想。
4 \+ g* b7 |6 `. Z. |5 a& _
猜想主要因为类比推理和偶然发现的巧合而出现。数学家通常会使用不完全归纳法，来测试自己的猜想。例如费马曾经根据首四个费马数是素数，便猜想所有费马数都是素数（此猜想已被推翻）
. C  j* e. }2 v" t5 Q' u
, B2 s$ V2 a# y. g1 N0 z假说（Hypothesis），即指按照预先设定，对某种现象进行的解释，即根据已知的科学事实和科学原理，对所研究的自然现象及其规律性提出的推测和说明，而且数据经过详细的分类、归纳与分析，得到一个暂时性但是可以被接受的解释。任何一种科学理论在未得到实验确证之前表现为假设学说或假说。

9 h, l  f1 W. h( D* \4 q) c有的假设还没有完全被科学方法所证明，也没有被任何一种科学方法所否定，但能够产生深远的影响。如1900年德国物理学家马克斯·普朗克为解决黑体辐射谱而首先提出量子论（量子假说）。

农民家的狗

不明觉厉

到处停留的叶子

" N4 S5 D% n  `- Z
**约瑟夫斯问题    都教授
$ r, c* l+ ]5 k( \6 v, P$ b: W
我们来聊聊约瑟夫斯问题。

有n个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

6 e& H7 }; S. T; G5 h, {问题是，给定了n和k，一开始要站在什么地方才能避免被处决？
& ~# u# P! }5 l9 }1 ]
, W. o3 m. O# }' ?; y; ~
---------------------------------------不思考的分割线---------------------------------------------
# c3 h3 z' `; ]. {据说这个问题是一个经常出现在计算机算法中的问题，不过当年我读书的时候对它并没有特别注意。在计算机编程的算法中，类似问题又称为约瑟夫环。老兵和神牛肯定比我清楚得多。我就不多说什么算法了。牛教授 兵教授  

---------------------------------------历史八卦的分割线----------------------------------
" H! o/ Y3 Q7 L  G这个问题是以弗拉维奥·约瑟夫斯命名的，他是1世纪的一名犹太历史学家。
5 D0 Z$ j/ ~# N据载，他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意。   

独角兽

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

8 w3 \" v, D9 [! F$ u3 [6 M4 {我们来聊聊约瑟夫斯问题。

9 N" l8 t; \' v, W1 \  |8 E% q1. 经过努力学习，这题我能用java编程做了，oh yeah！
) w; Y/ G7 d, d4 k9 H  c% ~
2. 但叶子问我的不是编程。对于给定的k，我可以用倒推法硬推。但是，想了半天也没有想到不用推的直接算法。
' \1 b0 ?* [% T% @2 i6 l
推的方法如下：
6 C+ m3 |8 ]$ {8 I7 }
/ |! i! K$ H  v$ x0 An=1，就一号，跑不掉的
7 X; d& W4 U$ y4 t- {2 ~/ jn＝2， 要站 （k+1） 模 n 那一号设a(2)，比如 k=2, 则 a2=1 （号）; 若 k=3, 则 a2=2
# A  r5 l! _0 r# l4 i# E* w9 [如此类推，n=i 时，要站在 a(i-1)+k 模 n 那一号。比如，k＝6， n＝19 时 要站在14号。
; E/ M% a9 K! a2 o- C
# V  V/ B- q% X" B3 I6 `3 @2 B- F; C
我算到k=6都找不出更直接的规律，不好玩

到处停留的叶子

独角兽 发表于 2014-7-16 20:30
! h' O# v. ?, y: K# U* z) g; N1. 经过努力学习，这题我能用java编程做了，oh yeah！
' t0 F' x( @5 V! y- H/ f) Q% `4 z
' n, Z$ E3 Q8 u; R. d- G2. 但叶子问我的不是编程。对于给定的k，我可以用 ...

兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答，或者先在网上找找看
, G# c* G, U' e. y/ Y5 G
* b, f5 D( G8 y; k3 t# `在维基上看到K=2的解法和还有K≠2的通用解法，这里摘抄过来那段关于n的有趣分析。

3 d- y1 ?2 E8 V- X: u( t还有下面我抄了两个通用算法，那个java的是不是和你做的一样啊？

4 q( z' {8 Z' S% V; {-----------------------------不动脑筋的分割线--------------------------

* J* o& |0 M9 x) J" }, L) r* L1 y$ g一个小心翼翼的Java例子：
& o: m) u5 \+ V  @+ u5 ^( T
int josephus(int n, int k) {
! T* k+ H2 z5 B3 q2 a+ M        return josephus(n, k, 1);
% u. ~9 e" \' h  n1 l  }
  int josephus(int n, int k, int startingPoint) {
# m9 ~+ O5 C- a      if(n == 1)
          return 1;
      int newSp = (startingPoint + k - 2) % n + 1;

      int survivor = josephus(n - 1, k, newSp);
      if (survivor < newSp) {
: B' l+ y' X6 f: Q& J% M% J          return survivor;
      } else
9 v2 _( T9 k- @$ p5 J' Y- e3 s          return survivor + 1;
5 o: a0 e7 ]* u8 C, K7 @' @  }

另外有个更简洁的例子
; L8 X7 X) i$ N9 H7 j  def josephus(n, k):
    if n ==1:
      return 1
7 }6 u% j9 b8 t% P# `7 k    else:
- H4 H$ l7 h0 t8 x# f* L      return ((josephus(n-1,k)+k-1) % n)+1
% w& X9 _" h. {( Y
（如果n这个数字很大很大，k很小很小，电脑会不会转晕过去呢？）

以上摘自 http://en.wikipedia.org/wiki/Josephus_problem#Solution
, [. O6 q! R) q

8 Z( n  l  B1 v. r# O2 n& Z; O* n关于n的分析：
- `8 O& A! J. J2 m1 F设f(n)为一开始有n个人时，生还者的位置。
: M4 `! y6 G! ^如果一开始有偶数个人，则第二圈时位置为x的人一开始在第2x - 1个位置。因此位置为f(2n)的人开始时的位置为2f(n) - 1。这便给出了以下的递推公式：
! s' B9 J6 i8 C: [! |! X
f(2n)=2f(n)-1
" G5 k4 H/ _8 t+ I如果一开始有奇数个人，则走了一圈以后，最终是号码为1的人被杀。于是同样地，再走第二圈时，新的第二、第四、……个人被杀，等等。在这种情况下，位置为x的人原先位置为2x+1。这便给出了以下的递推公式：

5 I" R, x; d" @5 m1 ~/ [; f, Z8 i0 Hf(2n+1)=2f(n)+1

2 A% B- w0 n9 J9 P
如果我们把n和f(n)的值列成表，我们可以看出一个规律：
5 V* C1 L4 Q$ y1 e: C, g
n    1    2        3        4        5        6        7        8        9        10        11        12        13        14        15    16
& b& ?2 k1 G; R+ @) ^3 of(n) 1    1        3        1        3        5        7        1        3        5        7        9        11        13        15        1

2 |! J% e8 Q3 g- H( c' x从中可以看出，f(n)是一个递增的奇数数列，每当n是2的幂时，便重新从f(n)=1开始。因此，如果我们选择m和l，使得n=2^m+l且0≤ l<2^m，那么f(n)=2 . l+1。显然，表格中的值满足这个方程。可以用数学归纳法给出一个证明。

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

) V8 n4 P  v2 o% J
答案的最漂亮的形式，与n的二进制表示有关：把n的第一位移动到最后，便得到f(n)。这可以通过把n表示为2^m+l来证明。

独角兽

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

在 ...

我的推法就是这个：
- R% L$ \- B3 [. P9 a( t
! t1 e$ h0 |' H. y  return ((josephus(n-1,k)+k-1) % n)+1
3 F& ^$ U* a0 t) Z1 r, ^, ^
' H+ Z- `7 s9 `! ]' e我有一点疏忽是如果整除，模的结果是0，但实际应该取n。所以这个表达式把 "+1"搞到括号外面就完全对了。
! F9 W7 q. ~+ T+ V7 w* Q: y
  s+ E. k' [' C- i0 j9 l! G2的情况我没单拿出来搞。

leekai

绕死了

常挨揍

看不懂
/ }" R+ z* O4 E$ P6 f+ s5 E% K6 s不过今天不幸运数是17

到处停留的叶子

常挨揍 发表于 2014-7-18 09:40
) O. s( ^' m9 Y" a6 {$ A! g看不懂
不过今天不幸运数是17

7月17日成了一个黑色的日子。很让人感觉生命无常。
/ f, ~( X$ ^: [$ e" n
' |% R! w' F- M0 ~. B以后出行挑日子，要找一个幸运数的交集，这里前面的9个数字也可以参考一下：1，3，7，9，13，15，21，25，31
4 P/ p, W& {% x& t
13号如果遇上星期五，还是算了，不要不信邪。