爱吱声

标题: 小小的停留之四 幸运数 [打印本页]

作者: 到处停留的叶子    时间: 2014-7-16 11:30
标题: 小小的停留之四 幸运数
上次说到  小小的停留之三 “计算机之父” 天才的数学家冯·诺伊曼
/ @7 z: D5 L7 v, V, H( q+ _/ O看冯·诺伊曼的故事,他有句名言:“若人们不相信数学简单,只因他们未意识到生命之复杂。”
0 a4 l, N3 ^: p7 C' Z' m4 A3 y7 Y" O8 P# s' Y! b
他有个好朋友,据说是最好的朋友,是生于匈牙利的波兰犹太人数学家乌拉姆,这位先生曾参与曼克顿计划(核武器上有Teller-Ulam design,Teller指爱德华·泰勒)。他亦有参与研究核能推动的航天飞机。在纯数学上,遍历理论、数论、集合论和代数拓扑都有他的足迹。
% x. v4 J$ ~+ B+ R
) C# l: u" C- J所以我在这里要说的幸运数不是中餐馆的饼干里给你的数字,也不是买彩票开奖的数字,而是在1955年波兰数学家乌拉姆提出的一个自然数列,用类似埃拉托斯特尼筛法的算法后留下的整数集合。
2 T  h  Q' E6 e: |5 @+ j9 ?6 ]: s7 t$ }& d+ C& u2 k1 z
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.9 ?5 w- q4 }" T: S& c
0 o! y0 y4 a+ z9 W. ]
幸运数的定义/ F& x- @. n1 E- @3 w) o
FORMULA        : l* y; T) |$ R; x: o
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.
3 J( i6 l  S' r& X! Y. p+ P0 A7 {- s1 c! j& l& o
具体一点来说说幸运数列怎么筛选出来的(喜欢数论的同学一定知道挑选素数的埃拉托斯特尼筛法,这个办法是类似的)
% u+ h# `7 y/ |/ y' B9 p' @0 d/ `
" \  V- }- \8 o- n* G" B/ t; C初始,从1开始的自然数列:( r9 G8 u# u4 c6 I
Begin with a list of integers starting with 1:) J3 n% H, L% W) ]0 n. R& _' Q
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  ……, q7 c* U& E# o1 v7 a. f

8 c, N. o; B1 t$ N) v开始删除,在这个数列里,从2开始,首先是每隔2个数字,删除第二个数字。剩下来的数字是奇数~~
$ J8 J/ j& h! }( {8 B  H# C1 E剩下的数列如下:
, S. [2 V# h& O# H! H0 bEvery second number (all even numbers) is eliminated, leaving only the odd integers:
6 w5 |% c; K- t% [3 {2 W  x1                3                5                7                9                11                13                15                17                19                21                23                25  ……! }& {# y4 d* B& N6 r
, b/ [6 g# ~$ i5 z4 S
接下来是3,每隔3个数字删除第三个。剩下的数列如下:3 M6 @! S. D- _' u5 `' r/ \
The second term in this sequence is 3. Every third number which remains in the list is eliminated:- T6 a0 F1 k; d# C: J2 o
1                3                                7                9                                13                15                                19                21                                25  ……
/ e1 U$ {, q# U' Z! w% D) j
; t. h( E8 r1 w3 e1 l0 ]  y现在接下来的数字是7,所以把上述数列中每第七个删除,剩下的数列是:
! V* S$ A, L; C/ p- H7 vThe next surviving number is now 7, so every seventh number that remains is eliminated:
1 n& ^& _% G. D; ]7 U* h6 e/ b1                3                                7                9                                13                15                                                21                                25  ……
" j3 E8 M: X1 T6 k7 l
, A3 d9 P) ?; G" t5 C5 s/ Y. r3 U. x接下来是9,……$ R  b  R1 x* w6 A: n8 ?
这个过程可以一直无限继续下去,被幸运地留下来的数字就是幸运数。
4 `. _2 Z- d2 I1 O, l. Q; ?4 }& g& S& P; a( T. N! T* d
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).3 k9 u' e- C6 i2 g8 \% E/ s
在OEIS编号为A000959的数列就是Lucky numbers
! z: Y' m% B9 L: s6 C上述链接给了一个稍微长一点的幸运数列:
2 P' v- Y$ x3 f' l: ~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 ……" a) _1 }) ]* k1 n3 x
. K. A. Z: \4 R
有没有同样喜欢看数字的同学告诉我,你看了这个数列发现的是什么呢?
- D+ |- P& |0 e0 g( c; J" H) y) d% F( W$ e' Q$ Q& J
; F0 d1 |; K; }

& k4 @& `5 w7 ]7 `4 O6 D第一个短一点的数列,我发现,1,3,5,7的平方(1,9,25,49)都是幸运数,但9的平方81就不是,于是马上想,那么是不是只有奇素数的平方才是幸运数呢?答案是不,11的平方也不是。于是叶子的第一个猜想就在几秒里被叶子证明是错误的。
) J! j9 H$ }9 @. x, @
5 x6 Q4 H  q: w8 U数论里的各种数列是数学里最容易上手理解的,不过最迷人最折磨人的也是它。著名的例子就是哥德巴赫猜想(Goldbach's conjecture)。1 ]( M, N) f- U' `( r
幸运数的挑选过程,类似上面提到过的埃拉托斯特尼筛法挑选素数的过程,同时也和这个著名猜想有关。  J; X2 `" B3 S3 D: F5 [
另外幸运数也曾经在正式进入书面讨论的时候被建议叫做 "the sieve of Josephus Flavius",因为它的挑选让大家想到著名的约瑟夫斯问题。
7 E: s3 Z0 I9 g
1 E! ~9 T! d; _( H* d" ~暂时就到这里吧,接下去要不要继续聊引出来的概念和问题呢?
! G; K* X0 A' B6 o0 E( k2 `+ Q! w1 ~- H9 y" k
**什么叫做Conjecture?
$ [& O. o+ E4 i* V$ f( |% b' `7 Q**约瑟夫斯问题。
作者: 到处停留的叶子    时间: 2014-7-16 21:26
猜想(conjecture)和假说(Hypothesis)
5 `6 p; p; T; L3 Z. h" B( ^7 W- \8 t+ _
猜想(conjecture)是一个看上去是真的,但尚未被证明的叙述。比如说上面提到的数学数列,因为它表现的没有规律和无限性,基于观察的某些结论,如果不能用科学逻辑的方法来证明在无限的未来它都是真的,那么之前所观察到的所有事实都仅仅是看上去是正确的。  M, F' u% O7 ]% A

" s3 H. M0 H* K5 P# M: L# A: N9 p5 e当猜想被证明后,它便会成为定理。猜想一日未成为定理,数学家都要小心在逻辑结构之中使用这些猜想。- A: q3 g* W% G4 k8 \

* e. O6 h9 E; c) Z- U7 N猜想主要因为类比推理和偶然发现的巧合而出现。数学家通常会使用不完全归纳法,来测试自己的猜想。例如费马曾经根据首四个费马数是素数,便猜想所有费马数都是素数(此猜想已被推翻): Q: ]! g7 s' E, z: v5 V5 z- b

8 z& ^$ n8 ~3 S4 w; g$ e; B假说(Hypothesis),即指按照预先设定,对某种现象进行的解释,即根据已知的科学事实和科学原理,对所研究的自然现象及其规律性提出的推测和说明,而且数据经过详细的分类、归纳与分析,得到一个暂时性但是可以被接受的解释。任何一种科学理论在未得到实验确证之前表现为假设学说或假说。
) ~9 S" l0 W( q6 v1 n, D9 c. A$ I( S' ~! f
有的假设还没有完全被科学方法所证明,也没有被任何一种科学方法所否定,但能够产生深远的影响。如1900年德国物理学家马克斯·普朗克为解决黑体辐射谱而首先提出量子论(量子假说)。
作者: 农民家的狗    时间: 2014-7-16 21:58
不明觉厉
作者: 到处停留的叶子    时间: 2014-7-17 06:50
本帖最后由 到处停留的叶子 于 2014-7-16 17:53 编辑
$ J1 k7 G" A( k; S& {& t1 v% _! r# s( `) s, Y& b$ r" S
**约瑟夫斯问题    都教授 : y' v% j" {2 O# t" ~

4 f. k! Z2 V! k8 A; C2 k我们来聊聊约瑟夫斯问题。
( s: R$ J& I! C7 `$ w' `  P
% P) h0 n  t( @  T# E' I: Q有n个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。
. C% a, z8 H- o- n3 {' Q+ u! G$ k* p/ ^; k+ m+ ]
问题是,给定了n和k,一开始要站在什么地方才能避免被处决?
* Q3 y5 }4 u% \) k) }+ M% _' U0 _* E  B

$ N5 {: K9 z# f. o% B5 }* c---------------------------------------不思考的分割线---------------------------------------------
* l* s9 I& o! V据说这个问题是一个经常出现在计算机算法中的问题,不过当年我读书的时候对它并没有特别注意。在计算机编程的算法中,类似问题又称为约瑟夫环。老兵和神牛肯定比我清楚得多。我就不多说什么算法了。牛教授 兵教授  . B/ Q. C" ^& [7 J* r4 u
: e- E2 u6 K9 S- G+ `
---------------------------------------历史八卦的分割线----------------------------------) w# b$ ~; e- y9 E/ m
这个问题是以弗拉维奥·约瑟夫斯命名的,他是1世纪的一名犹太历史学家。
( \# |: t9 J0 h" r据载,他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意。   
作者: 独角兽    时间: 2014-7-17 09:30
到处停留的叶子 发表于 2014-7-17 06:50 - w% n: m/ f, r: X% t8 q0 |
**约瑟夫斯问题    都教授 $ L% a5 a; T2 A2 g5 W+ A: C* W
. A2 w6 O; U9 ~1 y& r4 l9 }
我们来聊聊约瑟夫斯问题。

& u) u( Y1 K7 T' O# Z* i( ?$ s1. 经过努力学习,这题我能用java编程做了,oh yeah!) \9 F, O! \# h1 a7 X
2 q' y; \4 g  J) ~$ b
2. 但叶子问我的不是编程。对于给定的k,我可以用倒推法硬推。但是,想了半天也没有想到不用推的直接算法。
0 {, |7 e) F( u. ?* X, i7 f7 h2 [7 w  z" q; o" v+ p: A  e6 G
推的方法如下:
+ a5 V  O  Z* z3 E1 T8 H% R5 T) P8 D0 t% @7 g+ P
n=1,就一号,跑不掉的# O; j7 e9 T5 q& ?& M
n=2, 要站 (k+1) 模 n 那一号设a(2),比如 k=2, 则 a2=1 (号); 若 k=3, 则 a2=2
! P" ?4 N4 Y( t; A, J- W0 v如此类推,n=i 时,要站在 a(i-1)+k 模 n 那一号。比如,k=6, n=19 时 要站在14号。. t, S' a( t0 m7 x. |" a
& j; h" L0 i& a# M0 `. r( ?
9 Z$ ^- [; E% k' ]
我算到k=6都找不出更直接的规律,不好玩
作者: 到处停留的叶子    时间: 2014-7-17 11:02
本帖最后由 到处停留的叶子 于 2014-7-16 22:06 编辑
2 p' C- N5 b4 |( `
独角兽 发表于 2014-7-16 20:30 % T$ n, ~' {4 L5 [: m
1. 经过努力学习,这题我能用java编程做了,oh yeah!
& J, k; A: x$ B0 A8 b9 n- x' L6 m% f
7 e! e0 A3 o0 m) d" Y2. 但叶子问我的不是编程。对于给定的k,我可以用 ...
. @% }5 M/ s, w3 \% y: c- y0 Y, G

. d/ |2 _5 y7 I. \2 t兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看
6 E9 i: _7 q  O- [- Q; w
0 ]3 {/ B( {0 H, [: o在维基上看到K=2的解法和还有K≠2的通用解法,这里摘抄过来那段关于n的有趣分析。6 [' m; i. V* |+ i9 r

$ l* `5 |5 ?& ^) v0 b" ^+ \  F$ v4 k还有下面我抄了两个通用算法,那个java的是不是和你做的一样啊?: a% H% \) N- ], n' e5 Q' c3 U
# \1 p" n2 |' [3 e& a. F: B' L& ~; x  b
-----------------------------不动脑筋的分割线--------------------------
' X4 a3 }3 m7 m; M4 M4 v4 i8 \/ l% e- R  w
一个小心翼翼的Java例子:
" Z- R* b, p9 _7 o+ ?% ]6 v/ |: ?& _8 |% N  V
int josephus(int n, int k) {$ \, U, k+ l& K* \
        return josephus(n, k, 1);0 n# ]$ ?) ?. A6 q* X. d
  }1 L- X, S2 W+ U) }, B7 s. q8 @
  int josephus(int n, int k, int startingPoint) {3 @. `* E' K* u$ M" {) A
      if(n == 1)
8 `" f' T. T2 _6 r! _/ N$ d; H          return 1;
" U! e; [0 r4 [* z& {      int newSp = (startingPoint + k - 2) % n + 1;4 x5 ?# G7 ^1 Z, j
  J/ b7 x7 L; f0 `
      int survivor = josephus(n - 1, k, newSp);: c4 t. `4 E, @3 y% e6 g' Y
      if (survivor < newSp) {0 i, @- A" ]* I7 X
          return survivor;
- ?2 Q; t& i* ~% O/ X) i      } else
9 V' B* k. {; h) l7 n          return survivor + 1;: w/ m. G, W/ O8 b
  }
. O! ?+ M" @- H! n% x, ?) g; z
& J4 C, L5 F/ G( o0 n另外有个更简洁的例子
' V) t/ u% b+ `1 c) p3 a  def josephus(n, k):
. `' C5 j0 z) s    if n ==1:
  F' x7 u' d  k3 c2 M) L; \+ Z      return 1
* l; v6 {+ i* P; Z+ [; m    else:* b2 M7 ^4 q1 y( Q+ x
      return ((josephus(n-1,k)+k-1) % n)+18 T& e- h$ w1 m0 C2 o
7 Q! ~  M) g9 O
(如果n这个数字很大很大,k很小很小,电脑会不会转晕过去呢?), z# j: y# Q4 X7 F# b2 ?

$ H) Z; x$ j* b: O# Y( U4 G以上摘自 http://en.wikipedia.org/wiki/Josephus_problem#Solution
6 S# y* ~+ t. K- v7 e
; x& @  H; R! l  R/ Q
  ?( o: ^6 z# L0 C* D关于n的分析:* e; ~+ T0 ^- T  I( b
设f(n)为一开始有n个人时,生还者的位置。! D; J1 `: d2 R0 o
如果一开始有偶数个人,则第二圈时位置为x的人一开始在第2x - 1个位置。因此位置为f(2n)的人开始时的位置为2f(n) - 1。这便给出了以下的递推公式:
; |" `: v* E/ X* N9 ~5 d0 g2 E9 H( S) a
f(2n)=2f(n)-1
* q5 s& u- w6 D2 ~# }如果一开始有奇数个人,则走了一圈以后,最终是号码为1的人被杀。于是同样地,再走第二圈时,新的第二、第四、……个人被杀,等等。在这种情况下,位置为x的人原先位置为2x+1。这便给出了以下的递推公式:
& T/ w! T! l2 C* v& Z
" L' r6 g% Q) J! w# g# A" @( W  x2 p1 [f(2n+1)=2f(n)+1
' ]% R( e: S3 i2 Y, {0 M% [
" [0 [# r( h# C  w* }2 x- z" C/ |: f" ^9 i+ ?3 z5 `" o* C
如果我们把n和f(n)的值列成表,我们可以看出一个规律:
& i; X/ v- _, B) u0 }, y! J3 s! a* ^; P
n    1    2        3        4        5        6        7        8        9        10        11        12        13        14        15    16
  E/ B7 _9 i: K3 R/ Df(n) 1    1        3        1        3        5        7        1        3        5        7        9        11        13        15        1
' J% l) x3 v- p; G0 @9 ^  S
9 ~1 N' V7 O& h$ V( x5 W  V' U1 D从中可以看出,f(n)是一个递增的奇数数列,每当n是2的幂时,便重新从f(n)=1开始。因此,如果我们选择m和l,使得n=2^m+l且0≤ l<2^m,那么f(n)=2 . l+1。显然,表格中的值满足这个方程。可以用数学归纳法给出一个证明。
8 X" H2 M- e6 C- M0 B, n0 m- K- o! P9 P( `7 s) I
定理:如果n=2^m+l且0≤ l<2^m,则f(n) = 2.l+1。
0 C. Z( D6 H2 D- _) V, k1 U7 |3 \1 o* B
( o1 N% f; D" `; d
答案的最漂亮的形式,与n的二进制表示有关:把n的第一位移动到最后,便得到f(n)。这可以通过把n表示为2^m+l来证明。
作者: 独角兽    时间: 2014-7-17 11:19
到处停留的叶子 发表于 2014-7-17 11:02
; ^3 d) x; p" X  F5 G  o: Z兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看6 w7 Y$ {8 I: t# }6 \

3 X4 F% W+ Q2 t* k; `' S8 j3 Q6 q在 ...

+ K2 l: U/ b/ N0 B. L- U- T1 c我的推法就是这个:6 [; X5 c, L9 C; A) k! }# e1 W

( x2 Q& E6 o. @3 r  Z* n  return ((josephus(n-1,k)+k-1) % n)+1! R! A8 X4 k; _, w" \
, d# q- q  \8 E! F+ m
我有一点疏忽是如果整除,模的结果是0,但实际应该取n。所以这个表达式把 "+1"搞到括号外面就完全对了。; s- d+ R  b* z0 U0 V
7 u9 G) a: m5 v( ]0 ^7 q
2的情况我没单拿出来搞。
作者: leekai    时间: 2014-7-18 09:47
绕死了
作者: 常挨揍    时间: 2014-7-18 22:40
看不懂, Y) y% n4 b0 O
不过今天不幸运数是17
作者: 到处停留的叶子    时间: 2014-7-19 03:04
常挨揍 发表于 2014-7-18 09:40 3 H9 W0 ~% z% `2 {9 f) w8 @! z+ E
看不懂
- T6 q! y  m- d, X; \7 g不过今天不幸运数是17

$ ]8 l) X8 K/ \4 i! V2 y7月17日成了一个黑色的日子。很让人感觉生命无常。: S4 A* i, f) j9 b1 C; p; y! a
2 U' [& V) G/ W
以后出行挑日子,要找一个幸运数的交集,这里前面的9个数字也可以参考一下:1,3,7,9,13,15,21,25,31
! e6 D1 x) Y% c9 t. Y, Y+ k
5 ?/ G4 O+ @: V; Q13号如果遇上星期五,还是算了,不要不信邪。




欢迎光临 爱吱声 (http://aswetalk.net/bbs/) Powered by Discuz! X3.2