设为首页收藏本站

爱吱声

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

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

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

    [LV.7]分神

    跳转到指定楼层
    楼主
    发表于 2014-7-16 11:30:51 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    上次说到  小小的停留之三 “计算机之父” 天才的数学家冯·诺伊曼
    4 p  ~# |9 T; p1 W( J看冯·诺伊曼的故事,他有句名言:“若人们不相信数学简单,只因他们未意识到生命之复杂。”
    % S1 ]4 E! S  Y+ Y+ a' b
    : o+ i/ p! M& N6 v# P他有个好朋友,据说是最好的朋友,是生于匈牙利的波兰犹太人数学家乌拉姆,这位先生曾参与曼克顿计划(核武器上有Teller-Ulam design,Teller指爱德华·泰勒)。他亦有参与研究核能推动的航天飞机。在纯数学上,遍历理论、数论、集合论和代数拓扑都有他的足迹。5 X6 `) c5 ]3 [

    8 Y) Y+ f. _6 {9 |: t: s所以我在这里要说的幸运数不是中餐馆的饼干里给你的数字,也不是买彩票开奖的数字,而是在1955年波兰数学家乌拉姆提出的一个自然数列,用类似埃拉托斯特尼筛法的算法后留下的整数集合。
    * O" Y: e1 v4 P6 w
    ; ]. f! a% D8 X& }$ m) }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., i, c+ z- m+ A% L
    : j4 `, V, U- ]1 @* ^2 \
    幸运数的定义5 E( K( u! f* u; E
    FORMULA       
    $ r% y/ w! M+ f% ]# s4 zStart 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.
    9 t1 q, J' g7 ?7 ?% X  [. D$ Z: T- Z( g
    具体一点来说说幸运数列怎么筛选出来的(喜欢数论的同学一定知道挑选素数的埃拉托斯特尼筛法,这个办法是类似的)( [, T& J. D5 J$ g) a, s4 \8 s

    / U/ [% A/ j. e9 y6 K% ~& c初始,从1开始的自然数列:
    # k% {0 v' @4 Y2 `# s) e' V" ~Begin with a list of integers starting with 1:
    ) w, z. }2 z% _4 E% X: x1        2        3        4        5        6        7        8        9        10        11        12        13        14        15        16        17        18        19        20        21        22        23        24        25  ……
    ! k4 i3 B- `3 V# X9 h8 A+ c! H6 p- m; W: x* [
    开始删除,在这个数列里,从2开始,首先是每隔2个数字,删除第二个数字。剩下来的数字是奇数~~. y- c* K$ {" |  Q$ Y
    剩下的数列如下:7 }4 F" \& Q' V
    Every second number (all even numbers) is eliminated, leaving only the odd integers:+ i  L' f; C: K$ I
    1                3                5                7                9                11                13                15                17                19                21                23                25  ……
    0 C# o! L8 M) a/ I# [5 Q# ]% g+ {' V$ w. m& h# t1 E
    接下来是3,每隔3个数字删除第三个。剩下的数列如下:  J2 @4 P2 G0 [8 X& ]8 Z
    The second term in this sequence is 3. Every third number which remains in the list is eliminated:7 J) R" K- q2 m6 O9 V
    1                3                                7                9                                13                15                                19                21                                25  ……& o: O/ o0 p! Q3 u
    5 K$ C4 l) \; s
    现在接下来的数字是7,所以把上述数列中每第七个删除,剩下的数列是:! C7 z/ W( ?3 S) O% @$ j
    The next surviving number is now 7, so every seventh number that remains is eliminated:
    ! S- |! d4 e/ M3 {2 d/ b1                3                                7                9                                13                15                                                21                                25  ……
    + b! [7 S. X  s- Y5 N6 J2 |
    - j2 o1 q6 P: p; o/ N$ G4 \接下来是9,……
    : n1 m. J( U* A1 U; r+ Y  r这个过程可以一直无限继续下去,被幸运地留下来的数字就是幸运数。
    ( c* d6 i( j9 a/ i9 |0 W- F# Z7 l4 h) ?% k
    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).
    ( ~  H+ x5 m$ v在OEIS编号为A000959的数列就是Lucky numbers
    6 p$ V0 v/ w; g# O上述链接给了一个稍微长一点的幸运数列:
    . n3 R9 r1 w; m$ S7 V9 `- @; C1, 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 ……
    ' d5 P3 F( v8 s+ [4 U
    . C- p! J( H2 a: r有没有同样喜欢看数字的同学告诉我,你看了这个数列发现的是什么呢?
    ; u, T( A5 `) \7 g2 l) W9 i6 j
    5 \& g9 L) ^8 g/ w2 b& a
    ( Z4 `) n- j5 `! }( M3 X! i/ A9 d6 ]* k0 I
    第一个短一点的数列,我发现,1,3,5,7的平方(1,9,25,49)都是幸运数,但9的平方81就不是,于是马上想,那么是不是只有奇素数的平方才是幸运数呢?答案是不,11的平方也不是。于是叶子的第一个猜想就在几秒里被叶子证明是错误的。% T" H+ X+ z: q. I7 a' g& s

    ( n. b- l& P, {数论里的各种数列是数学里最容易上手理解的,不过最迷人最折磨人的也是它。著名的例子就是哥德巴赫猜想(Goldbach's conjecture)。
    # Q, `9 z7 ?% j& m; r) w* ?幸运数的挑选过程,类似上面提到过的埃拉托斯特尼筛法挑选素数的过程,同时也和这个著名猜想有关。& n( O' z* Q: d$ o4 [. Z) q
    另外幸运数也曾经在正式进入书面讨论的时候被建议叫做 "the sieve of Josephus Flavius",因为它的挑选让大家想到著名的约瑟夫斯问题。; m, B) M$ J3 v$ L/ L$ ~: r3 W6 Z+ d

    " u; R7 w3 @9 g2 s4 G9 P暂时就到这里吧,接下去要不要继续聊引出来的概念和问题呢?
    , @1 {; k8 I/ u7 \- Z* c8 c# m, [& G
    **什么叫做Conjecture?: Q/ |( F" h) N) F
    **约瑟夫斯问题。

    评分

    参与人数 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)
    - H6 X* M' n: r9 D
    , j0 @- G8 Y# ?  |1 z5 J% J& N+ b猜想(conjecture)是一个看上去是真的,但尚未被证明的叙述。比如说上面提到的数学数列,因为它表现的没有规律和无限性,基于观察的某些结论,如果不能用科学逻辑的方法来证明在无限的未来它都是真的,那么之前所观察到的所有事实都仅仅是看上去是正确的。
    7 y, I7 w4 F; O) M: E
    ) _* e+ M- S+ G4 ?$ S4 Z) \当猜想被证明后,它便会成为定理。猜想一日未成为定理,数学家都要小心在逻辑结构之中使用这些猜想。, p1 C  X2 X4 M. t+ B
    ) D& s) X9 |; u! E
    猜想主要因为类比推理和偶然发现的巧合而出现。数学家通常会使用不完全归纳法,来测试自己的猜想。例如费马曾经根据首四个费马数是素数,便猜想所有费马数都是素数(此猜想已被推翻)
    ( c( [8 X5 ?: q' O/ v9 |. N# \. \! X" m" U& _4 Z0 f
    假说(Hypothesis),即指按照预先设定,对某种现象进行的解释,即根据已知的科学事实和科学原理,对所研究的自然现象及其规律性提出的推测和说明,而且数据经过详细的分类、归纳与分析,得到一个暂时性但是可以被接受的解释。任何一种科学理论在未得到实验确证之前表现为假设学说或假说。
    , C: }  u4 K; m9 k
    - o  z) B# P. H6 [有的假设还没有完全被科学方法所证明,也没有被任何一种科学方法所否定,但能够产生深远的影响。如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 编辑
    : u2 m+ ?- d$ l9 T8 f9 Q$ ?! ^# O, g  k' Z$ I4 P! E
    **约瑟夫斯问题    都教授 ; d# H) k6 |7 C* A

    / P1 m9 s- z3 i* B) Y我们来聊聊约瑟夫斯问题。' `" q2 A3 c# I  z
    , ?4 W% y" X9 L6 |: F
    有n个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。; M: `+ D) A2 T# ^: A1 N0 E( @- e

    9 ~$ y4 G! F7 O( \  h0 C; F问题是,给定了n和k,一开始要站在什么地方才能避免被处决?9 ]: W, |- Q# g: e, v

    6 P& X# b" w( x6 p; }9 B, r
    - t7 L) p% v( ~% C/ ~, y. t/ z---------------------------------------不思考的分割线---------------------------------------------
    ! W1 M$ S0 {! M* `" K; `% ~据说这个问题是一个经常出现在计算机算法中的问题,不过当年我读书的时候对它并没有特别注意。在计算机编程的算法中,类似问题又称为约瑟夫环。老兵和神牛肯定比我清楚得多。我就不多说什么算法了。牛教授 兵教授  : @" l3 f5 H  k' i2 o
    " I, l5 p6 R: n
    ---------------------------------------历史八卦的分割线----------------------------------
    ) G! V# O2 B1 ^, z8 e这个问题是以弗拉维奥·约瑟夫斯命名的,他是1世纪的一名犹太历史学家。# a/ ~) v# G/ R4 Y
    据载,他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意。   

    该用户从未签到

    5#
    发表于 2014-7-17 09:30:00 | 只看该作者
    到处停留的叶子 发表于 2014-7-17 06:50
    + s# M# ?2 Z' I5 m3 S# @; A**约瑟夫斯问题    都教授
    ; a8 c- D, m! ]* y$ S: `# U. b& X# j. J" }& e% C
    我们来聊聊约瑟夫斯问题。
    ) U) |7 g$ }. T, X% L& c7 O
    1. 经过努力学习,这题我能用java编程做了,oh yeah!6 I# B1 I6 g6 G- P0 E) A' ~
    9 `$ B- m/ b& W! A! A/ k6 Z1 x
    2. 但叶子问我的不是编程。对于给定的k,我可以用倒推法硬推。但是,想了半天也没有想到不用推的直接算法。
    % j0 M  `6 V4 ]; O
    - d" S" w5 |' U: U! O( U3 \推的方法如下:
    9 h. @) [! e. Q8 |4 w- F4 ?2 {5 c1 k: B4 \
    n=1,就一号,跑不掉的
    7 Q1 ]: m2 J* |5 yn=2, 要站 (k+1) 模 n 那一号设a(2),比如 k=2, 则 a2=1 (号); 若 k=3, 则 a2=2   N# a  k" W6 B2 m! x; q
    如此类推,n=i 时,要站在 a(i-1)+k 模 n 那一号。比如,k=6, n=19 时 要站在14号。7 U/ T# P3 `5 [& t3 u  z
    ' h$ W9 i8 W) s) a6 C

    $ w9 Y, ~# @3 L2 b我算到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 编辑
    2 V* U' q  B: n- n% s1 B% @
    独角兽 发表于 2014-7-16 20:30
    % q: Q% O6 V1 j3 w8 J4 Y5 X9 J1. 经过努力学习,这题我能用java编程做了,oh yeah!
    1 O; o* @- u- D) e( a5 \5 p- Q
    3 H# ]# N& U% X" s  I7 Q7 F2. 但叶子问我的不是编程。对于给定的k,我可以用 ...

    " N+ {) r, L4 P* U9 @$ Z: e, y. p  L; ?2 P
    兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看# ^$ B' }3 S' p1 i. N7 ~

    ' {( F7 ~% u' C/ P; E/ j在维基上看到K=2的解法和还有K≠2的通用解法,这里摘抄过来那段关于n的有趣分析。- W$ `! i, p% {& n" |- K
    ' E6 e0 w2 w8 E! W$ L
    还有下面我抄了两个通用算法,那个java的是不是和你做的一样啊?) _/ b5 i( B$ s) P

    ' }0 i# Z3 A2 z7 x$ k-----------------------------不动脑筋的分割线--------------------------% j- N  k1 e( `( }
    . M2 E, j& d% Y- {2 w2 l
    一个小心翼翼的Java例子:+ w0 v& [+ T+ J
    ' ]) |$ n: d9 ^
    int josephus(int n, int k) {9 }% \. @" Z3 H; c) S, y& q
            return josephus(n, k, 1);
      ~8 d% f% z+ t; o- z9 O7 h$ t  }: l& z+ S: C" Q! ?) T. ]: `4 d
      int josephus(int n, int k, int startingPoint) {& b% c" H; \# ^' d$ P0 c% K3 d2 p
          if(n == 1)8 [. q! n; D$ G+ z- ~
              return 1;1 `) A0 I) Y0 X/ s  `4 a
          int newSp = (startingPoint + k - 2) % n + 1;
    : \8 g  X; h# P, J, E$ Z$ l
    , M! N7 U5 J+ g" P      int survivor = josephus(n - 1, k, newSp);
    0 f& M/ N2 j1 T9 m      if (survivor < newSp) {
    * Q; c' o! a' A  b4 p          return survivor;
    6 [- M; m& t. d. Z      } else
    % n; i4 W/ r# a7 R8 ?+ L0 Z" h          return survivor + 1;
    + F' J7 ]; H  E/ e9 h0 G  }6 s* w1 V8 n* U) k: x- M$ ?( J# q
    " b' N& l- ]: w/ u
    另外有个更简洁的例子
    " f- M0 @) d. d4 m  def josephus(n, k):! z% D# a7 w/ ~! t8 S
        if n ==1:- A' ]' q$ w+ R% Y$ Z
          return 1
    1 }8 O3 e" f5 E5 h  B: H: M    else:. w1 ~( P" Y+ N' A; C" H. X
          return ((josephus(n-1,k)+k-1) % n)+1
    ! |/ A" \8 l( R$ G4 P( G5 F; @: c! T
    (如果n这个数字很大很大,k很小很小,电脑会不会转晕过去呢?)
    0 c% x/ Y- H) `7 u" N/ B) t6 D
    ; I( M' }; A* j; S9 F以上摘自 http://en.wikipedia.org/wiki/Josephus_problem#Solution
    + B- h& K- v! s
    " `, ]% z8 p% }8 ^7 j( A( ]8 a$ _5 a% S* p( a$ G
    关于n的分析:
    ( G3 a. }9 N! q. y设f(n)为一开始有n个人时,生还者的位置。
    $ R6 I9 H' P/ K& p如果一开始有偶数个人,则第二圈时位置为x的人一开始在第2x - 1个位置。因此位置为f(2n)的人开始时的位置为2f(n) - 1。这便给出了以下的递推公式:
    6 o1 `4 ~0 d* u9 X6 L
    , S4 d7 M' B7 k* Q5 h9 n" w" of(2n)=2f(n)-12 H8 a" i  i, U
    如果一开始有奇数个人,则走了一圈以后,最终是号码为1的人被杀。于是同样地,再走第二圈时,新的第二、第四、……个人被杀,等等。在这种情况下,位置为x的人原先位置为2x+1。这便给出了以下的递推公式:/ K5 a' A" X) M1 U& L: r2 h
    7 U2 V& ^2 X, m; e
    f(2n+1)=2f(n)+1
    & A/ C3 z5 d- k2 C0 T2 j- U( w. l1 w9 c) Y" l

    4 j7 p4 U' F) [( a% C2 \! o. V如果我们把n和f(n)的值列成表,我们可以看出一个规律:
    , B/ l6 u! X5 _! Z( K# u
    2 R' n" E7 Y3 ~: n( t! e0 B4 c1 on    1    2        3        4        5        6        7        8        9        10        11        12        13        14        15    16
      H: Z- Q/ o1 f6 vf(n) 1    1        3        1        3        5        7        1        3        5        7        9        11        13        15        1& V1 p+ i" q% Q: A6 ?, {( q) ^

    ( a5 P# u' {3 ]7 x! N- U5 j+ l从中可以看出,f(n)是一个递增的奇数数列,每当n是2的幂时,便重新从f(n)=1开始。因此,如果我们选择m和l,使得n=2^m+l且0≤ l<2^m,那么f(n)=2 . l+1。显然,表格中的值满足这个方程。可以用数学归纳法给出一个证明。
    ( L8 W3 v, t, W# a: f
    - U0 v4 ~9 u9 L; V/ ?, ]3 c定理:如果n=2^m+l且0≤ l<2^m,则f(n) = 2.l+1。* a) E8 v" n1 u+ ]

    + U7 e2 s' x  d+ o! u: h0 P# d+ i* }9 j) c. x; C( r* i
    答案的最漂亮的形式,与n的二进制表示有关:把n的第一位移动到最后,便得到f(n)。这可以通过把n表示为2^m+l来证明。

    该用户从未签到

    7#
    发表于 2014-7-17 11:19:06 | 只看该作者
    到处停留的叶子 发表于 2014-7-17 11:02 ' T' N' K5 {9 \$ f9 o9 N, d
    兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看
      A) u9 I# g0 A9 g5 V3 C7 G# ~6 c! e& r+ y( K' r, v6 i
    在 ...
    ! G# @; J  \  Z& d. ]+ |
    我的推法就是这个:
    / ~9 c  W: ~$ c9 l" i$ d
    & ]5 g- y; N8 S+ X' o  return ((josephus(n-1,k)+k-1) % n)+1/ m# s2 d- |3 I

    ' I5 b1 Q1 t. r! f$ V% p  L我有一点疏忽是如果整除,模的结果是0,但实际应该取n。所以这个表达式把 "+1"搞到括号外面就完全对了。# H6 t4 ]2 O+ ~* f3 h
    . f1 y; {; f  J
    2的情况我没单拿出来搞。
  • TA的每日心情
    慵懒
    2020-5-10 00:00
  • 签到天数: 1237 天

    [LV.10]大乘

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

    [LV.Master]无

    9#
    发表于 2014-7-18 22:40:37 | 只看该作者
    看不懂
    * E6 ^. z: b4 r9 q$ {/ Z6 ]0 X/ i不过今天不幸运数是17
  • TA的每日心情
    擦汗
    2020-3-23 00:29
  • 签到天数: 134 天

    [LV.7]分神

    10#
     楼主| 发表于 2014-7-19 03:04:00 | 只看该作者
    常挨揍 发表于 2014-7-18 09:40
    : P7 s9 z' ?( q4 g( c$ v+ W看不懂
    ! d- w$ F% z& k+ n% D, S# ~3 Y不过今天不幸运数是17
    5 b* n# `9 }" F# {
    7月17日成了一个黑色的日子。很让人感觉生命无常。
    1 k* P1 ?; K& ^" _
    5 k' G7 ?7 a; ]! r5 `+ B; e以后出行挑日子,要找一个幸运数的交集,这里前面的9个数字也可以参考一下:1,3,7,9,13,15,21,25,31& T5 [' z  ]" |' r/ \
    . ~" P  O* o  m0 g7 J  N
    13号如果遇上星期五,还是算了,不要不信邪。

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

    GMT+8, 2025-4-2 18:24 , Processed in 0.053566 second(s), 23 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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