设为首页收藏本站

爱吱声

 找回密码
 注册
搜索
查看: 5359|回复: 9
打印 上一主题 下一主题

[科教沙龙] 小小的停留之四 幸运数

[复制链接]
  • TA的每日心情
    擦汗
    2020-3-23 00:29
  • 签到天数: 134 天

    [LV.7]分神

    跳转到指定楼层
    楼主
    发表于 2014-7-16 11:30:51 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    上次说到  小小的停留之三 “计算机之父” 天才的数学家冯·诺伊曼8 n5 ]: y* @) U# j% l
    看冯·诺伊曼的故事,他有句名言:“若人们不相信数学简单,只因他们未意识到生命之复杂。”& |, G$ `( B( A+ D. \1 j

    6 I3 S' ~" U' j5 Q$ v5 K  K7 ?他有个好朋友,据说是最好的朋友,是生于匈牙利的波兰犹太人数学家乌拉姆,这位先生曾参与曼克顿计划(核武器上有Teller-Ulam design,Teller指爱德华·泰勒)。他亦有参与研究核能推动的航天飞机。在纯数学上,遍历理论、数论、集合论和代数拓扑都有他的足迹。
      r8 @& u+ l0 k3 `/ @) t( b; w# Z3 i
    所以我在这里要说的幸运数不是中餐馆的饼干里给你的数字,也不是买彩票开奖的数字,而是在1955年波兰数学家乌拉姆提出的一个自然数列,用类似埃拉托斯特尼筛法的算法后留下的整数集合。4 P  j! I1 [) d4 T& y0 F
    * H+ ]7 X' h& z9 E
    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.
    2 K4 V5 F; C- i4 L5 W1 `0 |6 S8 Z
    幸运数的定义
    2 Z3 X2 _* I5 o% C5 W( @( P5 C8 z7 DFORMULA       
    ( D3 X* N  Y9 c5 l* ~$ W: l- u$ jStart 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./ v5 D) d* `" W8 t* q* [
    9 e& C2 e7 I" R
    具体一点来说说幸运数列怎么筛选出来的(喜欢数论的同学一定知道挑选素数的埃拉托斯特尼筛法,这个办法是类似的): b* ?& w6 ?- y$ C8 c" r
    ) ^: Y8 n5 q3 s' f
    初始,从1开始的自然数列:+ j9 b+ c% G3 o* E1 u: `3 t* t
    Begin with a list of integers starting with 1:/ C; }$ N0 h& x
    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  ……
    " D# P1 z. t5 q9 q, r
    4 x. O# n9 J0 g, _! @2 ]开始删除,在这个数列里,从2开始,首先是每隔2个数字,删除第二个数字。剩下来的数字是奇数~~
    4 Q) k. O0 Y% r/ F剩下的数列如下:
    : k% ~- m* T0 N; G6 B& q, gEvery second number (all even numbers) is eliminated, leaving only the odd integers:
    : ^9 D5 K1 B$ ]% k* @1                3                5                7                9                11                13                15                17                19                21                23                25  ……' s4 g7 g) v2 o% m

    6 s% \$ R% J" I$ \' ~( r接下来是3,每隔3个数字删除第三个。剩下的数列如下:
    * h0 w* p  X) ^, S, x  tThe second term in this sequence is 3. Every third number which remains in the list is eliminated:) x' t1 `1 g  k
    1                3                                7                9                                13                15                                19                21                                25  ……
    : }; _0 ^$ N: l! u; D8 D
    4 O- T1 |7 F( A( G8 t现在接下来的数字是7,所以把上述数列中每第七个删除,剩下的数列是:
    * _1 u* f# V4 ]4 q/ c. [6 qThe next surviving number is now 7, so every seventh number that remains is eliminated:( P: |  Q  X+ Q# s
    1                3                                7                9                                13                15                                                21                                25  ……
    ; O& ]5 S! E4 v, P% f& f& G
    * `5 ?$ {  f& ?3 j7 D' ^接下来是9,……
    % [, E' r3 q5 F* O: m6 d0 {这个过程可以一直无限继续下去,被幸运地留下来的数字就是幸运数。2 j! M3 V& z" y) Q6 y8 g7 n& M9 D  Y

    ) o0 N# v6 b- b. n1, 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).
    0 k6 H1 `6 Q% o' H: E/ }# w2 R9 ^在OEIS编号为A000959的数列就是Lucky numbers
    * d/ `2 [  T- ^6 L) E7 K上述链接给了一个稍微长一点的幸运数列:, i0 O; C4 w4 {" R. x/ s6 G4 v
    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 ……  g& W9 }, K, T
    " U7 p& g  @& f, P: x$ m
    有没有同样喜欢看数字的同学告诉我,你看了这个数列发现的是什么呢?# K; K/ q6 B- p+ u* b& n8 J" w

    ' R/ }! G& M! H3 z  U& {; b) p. E7 d& ]1 b1 E7 r
    " i4 P' N9 I# Y! I- i/ ]. w5 n3 u
    第一个短一点的数列,我发现,1,3,5,7的平方(1,9,25,49)都是幸运数,但9的平方81就不是,于是马上想,那么是不是只有奇素数的平方才是幸运数呢?答案是不,11的平方也不是。于是叶子的第一个猜想就在几秒里被叶子证明是错误的。& m. b; B6 S1 R4 w6 W9 D0 q- G: j

    3 k: \% s8 A/ [* W" k( Y数论里的各种数列是数学里最容易上手理解的,不过最迷人最折磨人的也是它。著名的例子就是哥德巴赫猜想(Goldbach's conjecture)。
    + s4 ~! j. n- m4 D! l幸运数的挑选过程,类似上面提到过的埃拉托斯特尼筛法挑选素数的过程,同时也和这个著名猜想有关。
    # q6 h( Y' B! N) v/ g' @) o另外幸运数也曾经在正式进入书面讨论的时候被建议叫做 "the sieve of Josephus Flavius",因为它的挑选让大家想到著名的约瑟夫斯问题。0 g' h0 |' `- A) N5 r3 o" l
    ! P% f* v: ]8 P. U# l3 z% h( j0 q
    暂时就到这里吧,接下去要不要继续聊引出来的概念和问题呢?& U. E$ |/ ]5 u9 v4 h

    2 L2 ^. n" i% V$ B2 A1 q**什么叫做Conjecture?5 m4 q* o7 j: q
    **约瑟夫斯问题。

    评分

    参与人数 9爱元 +49 收起 理由
    韦红雪 + 8
    喜欢就捧捧场 + 6 涨姿势
    独角兽 + 4 涨姿势
    Pipilu + 2 涨姿势
    农民家的狗 + 4

    查看全部评分

  • TA的每日心情
    擦汗
    2020-3-23 00:29
  • 签到天数: 134 天

    [LV.7]分神

    沙发
     楼主| 发表于 2014-7-16 21:26:40 | 只看该作者
    猜想(conjecture)和假说(Hypothesis)1 |4 l2 j7 ?+ k! ~$ f. N/ \
    3 h* H& A) Z) g5 c# L  U
    猜想(conjecture)是一个看上去是真的,但尚未被证明的叙述。比如说上面提到的数学数列,因为它表现的没有规律和无限性,基于观察的某些结论,如果不能用科学逻辑的方法来证明在无限的未来它都是真的,那么之前所观察到的所有事实都仅仅是看上去是正确的。# B' z0 j' Q- G, a" L

    ; b  O* ~  ]: ^3 W: s当猜想被证明后,它便会成为定理。猜想一日未成为定理,数学家都要小心在逻辑结构之中使用这些猜想。. g# U8 Q( s* b$ x6 }  F: d) i4 {) l

    2 Q- c' H1 ^3 w猜想主要因为类比推理和偶然发现的巧合而出现。数学家通常会使用不完全归纳法,来测试自己的猜想。例如费马曾经根据首四个费马数是素数,便猜想所有费马数都是素数(此猜想已被推翻)1 a0 I- E# v0 Z  D1 P& N
    # Q1 R1 z8 j1 I8 `0 n
    假说(Hypothesis),即指按照预先设定,对某种现象进行的解释,即根据已知的科学事实和科学原理,对所研究的自然现象及其规律性提出的推测和说明,而且数据经过详细的分类、归纳与分析,得到一个暂时性但是可以被接受的解释。任何一种科学理论在未得到实验确证之前表现为假设学说或假说。# u/ f8 O8 l% I+ s
    4 y: z4 }( q; C5 C, u8 j" q
    有的假设还没有完全被科学方法所证明,也没有被任何一种科学方法所否定,但能够产生深远的影响。如1900年德国物理学家马克斯·普朗克为解决黑体辐射谱而首先提出量子论(量子假说)。

    评分

    参与人数 1爱元 +4 收起 理由
    独角兽 + 4 涨姿势

    查看全部评分

  • TA的每日心情
    慵懒
    2018-2-25 20:16
  • 签到天数: 128 天

    [LV.7]分神

    板凳
    发表于 2014-7-16 21:58:32 | 只看该作者
    不明觉厉

    点评

    你是先入为主地封闭了自己的思考。这个数列的筛选规则,只要会数数都能看懂的吧??  发表于 2014-7-17 06:46
  • TA的每日心情
    擦汗
    2020-3-23 00:29
  • 签到天数: 134 天

    [LV.7]分神

    地板
     楼主| 发表于 2014-7-17 06:50:45 | 只看该作者
    本帖最后由 到处停留的叶子 于 2014-7-16 17:53 编辑 . a+ y! ^) n+ T$ Y( M

    3 C& s% k1 k+ d: r8 x**约瑟夫斯问题    都教授 0 E7 Q$ \( `- Z# h
    & v) N/ g3 {# X
    我们来聊聊约瑟夫斯问题。+ `9 K, {( e$ f/ j( t$ n! Z+ w

    : q/ t" l# w" w  z) ?, M1 m有n个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。
    0 A: l. K1 Q+ W& v9 q7 [, K
    ; d. p  q% v" i  T0 L问题是,给定了n和k,一开始要站在什么地方才能避免被处决?
    9 ]8 h9 D- \% R
    . b6 u" k, `( j% e: P5 [3 `' N* n0 a
    ---------------------------------------不思考的分割线---------------------------------------------
    ! [% p1 K( `$ o8 Y+ W据说这个问题是一个经常出现在计算机算法中的问题,不过当年我读书的时候对它并没有特别注意。在计算机编程的算法中,类似问题又称为约瑟夫环。老兵和神牛肯定比我清楚得多。我就不多说什么算法了。牛教授 兵教授  - X+ ]6 ~, w+ e) I0 V
    ) J  C- y/ B% A& U$ g
    ---------------------------------------历史八卦的分割线----------------------------------4 [! F! V- F+ Q
    这个问题是以弗拉维奥·约瑟夫斯命名的,他是1世纪的一名犹太历史学家。4 V" M& C. {% `  j- w) N
    据载,他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意。   

    该用户从未签到

    5#
    发表于 2014-7-17 09:30:00 | 只看该作者
    到处停留的叶子 发表于 2014-7-17 06:50 5 I9 L9 g6 A; N0 K2 m! }
    **约瑟夫斯问题    都教授
    0 [3 ~1 T8 j  \, E! W& @
    / j+ \8 G, |9 F/ I我们来聊聊约瑟夫斯问题。
    " r# n& g/ R! E1 }& {4 c* o- K+ q
    1. 经过努力学习,这题我能用java编程做了,oh yeah!( s: D2 T- `- q

    $ X0 G4 y, B# @1 t2. 但叶子问我的不是编程。对于给定的k,我可以用倒推法硬推。但是,想了半天也没有想到不用推的直接算法。5 ^# P' K! y1 f; P( A! t
    ) Y0 @' h. B- d  y$ n0 y
    推的方法如下:
    / _8 c. q* |* i( G" F# c: t' g
    ( Q/ H1 M& \: n. Tn=1,就一号,跑不掉的
    0 o" K/ h6 J7 u! zn=2, 要站 (k+1) 模 n 那一号设a(2),比如 k=2, 则 a2=1 (号); 若 k=3, 则 a2=2 6 K# j! l% N. \; w2 ~
    如此类推,n=i 时,要站在 a(i-1)+k 模 n 那一号。比如,k=6, n=19 时 要站在14号。
    1 w# {3 P2 E, t  L$ I- I1 [8 Y
    " V* _9 g  @; E# x) G- n
      b3 u; F# P9 P5 ?* F# K我算到k=6都找不出更直接的规律,不好玩

    评分

    参与人数 1爱元 +6 收起 理由
    到处停留的叶子 + 6 哇!!!

    查看全部评分

  • TA的每日心情
    擦汗
    2020-3-23 00:29
  • 签到天数: 134 天

    [LV.7]分神

    6#
     楼主| 发表于 2014-7-17 11:02:58 | 只看该作者
    本帖最后由 到处停留的叶子 于 2014-7-16 22:06 编辑
    6 U" f) N; ?* C2 Z( V# c: M6 t1 Y
    独角兽 发表于 2014-7-16 20:30 9 _3 I& U5 [: A: Q' G7 I0 m7 F2 w
    1. 经过努力学习,这题我能用java编程做了,oh yeah!; }8 l5 [: j$ K  X6 G0 P
    9 O/ p+ u2 K3 l: F, E  v/ M7 N; e
    2. 但叶子问我的不是编程。对于给定的k,我可以用 ...

    $ G/ b1 w7 U! r  O8 f& H6 }9 u# `# i( f5 ~* m; q
    兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看; Z. V$ P" P8 {2 _
      F; \8 Y7 [2 O' H0 O  Z0 J2 j
    在维基上看到K=2的解法和还有K≠2的通用解法,这里摘抄过来那段关于n的有趣分析。! _# z+ [, T: U7 N( L
    ! x. r, y1 d% x6 _- Q
    还有下面我抄了两个通用算法,那个java的是不是和你做的一样啊?
    4 M/ m% T8 V) |# E% x& u* a! F- R8 n- O9 x  k
    -----------------------------不动脑筋的分割线--------------------------) q; g. H1 U: \# _

    3 X- f0 T% e# x+ }1 [一个小心翼翼的Java例子:+ w  U; X* ?9 P9 c( n
    8 n2 L. b1 s+ m. ~. _( J: B  @
    int josephus(int n, int k) {
    ' Y) o+ W! U3 ~, ~$ d5 H1 h3 o0 t        return josephus(n, k, 1);8 Y6 r+ N4 n2 d# X& W7 k) m
      }! P. @& y* P& _' K9 @2 G, U
      int josephus(int n, int k, int startingPoint) {" e6 ^+ T7 h, Q1 A7 x
          if(n == 1)1 [8 H, h% ]% }3 ], B2 h
              return 1;4 W' o# K3 ^" B
          int newSp = (startingPoint + k - 2) % n + 1;4 p2 D; U& L  k
    ! a. u% c2 M7 z9 R: t
          int survivor = josephus(n - 1, k, newSp);$ s' E1 B) p5 N5 h3 J
          if (survivor < newSp) {
    ! K* n5 ?, G6 Q: q. h3 i( K! _/ [' _5 e          return survivor;
    8 R) C6 N# A" s* D. D      } else9 [2 N+ p1 W# O) {* g
              return survivor + 1;
    5 ^3 s2 A3 |1 X% v! ~  }) k% X( z2 S1 i4 ]
    7 |/ f& u8 @& J- s& K6 @1 f
    另外有个更简洁的例子
    4 }; Z/ D6 k1 Y( `  def josephus(n, k):
    * B/ d9 ]% l1 Y1 D, \    if n ==1:# i4 A8 q6 Q5 R
          return 1
    4 c$ q% H( ^! I, N( i    else:( s1 Q& |/ o* D7 d- p
          return ((josephus(n-1,k)+k-1) % n)+1/ R: f, q! R& c5 V, B, _
    ! a: v2 _8 G# P- Z
    (如果n这个数字很大很大,k很小很小,电脑会不会转晕过去呢?), Q& c! [! s1 N

    : v1 g# Y" p& l; q以上摘自 http://en.wikipedia.org/wiki/Josephus_problem#Solution& ~3 o8 `; |5 q& k7 W+ s6 ^5 a! w

    6 X+ t) Y% Q$ m7 O: M6 W( h
    ( p) b' n. E2 n, [" `2 D2 e关于n的分析:
    5 Y3 |% A5 _5 G% k. ~8 q, h/ M! C设f(n)为一开始有n个人时,生还者的位置。+ A. k* e$ y' Z5 M: n7 C; ~
    如果一开始有偶数个人,则第二圈时位置为x的人一开始在第2x - 1个位置。因此位置为f(2n)的人开始时的位置为2f(n) - 1。这便给出了以下的递推公式:
    ; `& R& m& u5 X4 y2 x- S
    ) d. ?* l2 I2 g% df(2n)=2f(n)-1
    2 i& G8 c- C7 X7 t( d$ s! g如果一开始有奇数个人,则走了一圈以后,最终是号码为1的人被杀。于是同样地,再走第二圈时,新的第二、第四、……个人被杀,等等。在这种情况下,位置为x的人原先位置为2x+1。这便给出了以下的递推公式:
      k4 m1 w& `2 i5 W5 N
    : c; A+ w2 S+ Qf(2n+1)=2f(n)+11 E1 Q$ L- @5 y; b* u, C/ ^

    ; _4 E7 |, T5 X' W! G* I- O' W- Y. |1 x# r0 K
    如果我们把n和f(n)的值列成表,我们可以看出一个规律:
    - Y4 s, f9 A3 e6 P
      S1 `* g' o8 j3 w' Q; d6 Q: vn    1    2        3        4        5        6        7        8        9        10        11        12        13        14        15    16- h) D+ n* Z' K& P% F1 ~
    f(n) 1    1        3        1        3        5        7        1        3        5        7        9        11        13        15        1# M+ [& c1 h' C; b' b. ^
    9 S2 `9 P$ `; R4 o
    从中可以看出,f(n)是一个递增的奇数数列,每当n是2的幂时,便重新从f(n)=1开始。因此,如果我们选择m和l,使得n=2^m+l且0≤ l<2^m,那么f(n)=2 . l+1。显然,表格中的值满足这个方程。可以用数学归纳法给出一个证明。
    # g7 F3 _! x" F6 H' U2 K  R& U! ^% R2 W' w2 ?' c3 v
    定理:如果n=2^m+l且0≤ l<2^m,则f(n) = 2.l+1。6 Q$ Q! \9 H2 I4 W
    + |7 y* k0 n, ]0 n: C

    7 p9 u/ H6 H- n" D- V答案的最漂亮的形式,与n的二进制表示有关:把n的第一位移动到最后,便得到f(n)。这可以通过把n表示为2^m+l来证明。

    该用户从未签到

    7#
    发表于 2014-7-17 11:19:06 | 只看该作者
    到处停留的叶子 发表于 2014-7-17 11:02 . w% D, A6 ]0 i. ~7 i
    兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看
    $ l. F  r# M$ m' G5 V
      I, M/ `0 {6 l3 \" V: q4 n在 ...

    * y1 D8 K! `1 Y8 X$ J我的推法就是这个:6 H3 R, ]8 s4 K! e# P1 n& y

    + n. R1 d- R) J* Z* ^. L/ u  return ((josephus(n-1,k)+k-1) % n)+1% I5 i; r5 D; ^/ j0 a& k
    4 s# _/ V& Q2 `$ h  c; |; z3 ]
    我有一点疏忽是如果整除,模的结果是0,但实际应该取n。所以这个表达式把 "+1"搞到括号外面就完全对了。: w9 W3 z  O  E$ U

    8 E% d! o; V4 ]2 ?) ]1 e2的情况我没单拿出来搞。
  • TA的每日心情
    慵懒
    2020-5-10 00:00
  • 签到天数: 1237 天

    [LV.10]大乘

    8#
    发表于 2014-7-18 09:47:20 | 只看该作者
    绕死了
  • TA的每日心情
    慵懒
    前天 08:37
  • 签到天数: 2165 天

    [LV.Master]无

    9#
    发表于 2014-7-18 22:40:37 | 只看该作者
    看不懂, V' u. n% c$ E% C0 {, S& g) G
    不过今天不幸运数是17
  • TA的每日心情
    擦汗
    2020-3-23 00:29
  • 签到天数: 134 天

    [LV.7]分神

    10#
     楼主| 发表于 2014-7-19 03:04:00 | 只看该作者
    常挨揍 发表于 2014-7-18 09:40 3 O1 n% f* `$ Y* i5 n( Z
    看不懂
    0 l  r% K0 j3 z& i不过今天不幸运数是17
    . v4 c( Q$ ~$ o: [. ^) m' g
    7月17日成了一个黑色的日子。很让人感觉生命无常。; K& N& W( \, |1 O& y
    8 `) M  K) [1 P, ^( o6 U! W
    以后出行挑日子,要找一个幸运数的交集,这里前面的9个数字也可以参考一下:1,3,7,9,13,15,21,25,31
    # {' Z* n5 B( j* F1 o( [* w6 k+ a; Q3 w7 Z/ p* q1 |  k
    13号如果遇上星期五,还是算了,不要不信邪。

    手机版|小黑屋|Archiver|网站错误报告|爱吱声   

    GMT+8, 2025-10-3 06:18 , Processed in 0.042593 second(s), 28 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表