设为首页收藏本站

爱吱声

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

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

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

    [LV.7]分神

    跳转到指定楼层
    楼主
    发表于 2014-7-16 11:30:51 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    上次说到  小小的停留之三 “计算机之父” 天才的数学家冯·诺伊曼
    / W8 `* B) J- z4 E看冯·诺伊曼的故事,他有句名言:“若人们不相信数学简单,只因他们未意识到生命之复杂。”
    , \/ k6 d9 x3 A: P  P3 e0 e; ]  v
    他有个好朋友,据说是最好的朋友,是生于匈牙利的波兰犹太人数学家乌拉姆,这位先生曾参与曼克顿计划(核武器上有Teller-Ulam design,Teller指爱德华·泰勒)。他亦有参与研究核能推动的航天飞机。在纯数学上,遍历理论、数论、集合论和代数拓扑都有他的足迹。
    5 K3 ^7 ?0 ~% Z* A$ N( J1 J) x# @1 M8 U/ X4 e+ K& }/ r  x
    所以我在这里要说的幸运数不是中餐馆的饼干里给你的数字,也不是买彩票开奖的数字,而是在1955年波兰数学家乌拉姆提出的一个自然数列,用类似埃拉托斯特尼筛法的算法后留下的整数集合。
    ! ~( l. R. y0 @$ U( H+ e& J. Z/ n0 K2 O3 j
    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.5 x: R8 |: Y/ h  q# O$ p
    8 ~9 l, S* y1 x9 R5 n) I7 G0 O6 i( y
    幸运数的定义
    $ u$ y; A  S: K# X- YFORMULA        / @* I' |9 y) v6 @
    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.
    6 R3 Q# t. x# X1 W6 N( p8 P1 e$ k
    6 @1 F7 D' j/ T7 @7 C& T具体一点来说说幸运数列怎么筛选出来的(喜欢数论的同学一定知道挑选素数的埃拉托斯特尼筛法,这个办法是类似的)3 W( o0 Q& h. T: t7 l6 ^
    + V  ^6 e& ~% ]( b2 {& n8 J
    初始,从1开始的自然数列:6 \! r! L1 }* ?/ x: E; p6 Z8 V
    Begin with a list of integers starting with 1:  R9 f! I. w0 ]9 p9 t
    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  ……1 ]/ ?4 [4 F* R+ Q% [
    % m- H' q& o6 T% ]2 W5 {6 n( _6 ]
    开始删除,在这个数列里,从2开始,首先是每隔2个数字,删除第二个数字。剩下来的数字是奇数~~$ Q$ h# _8 _$ T: O
    剩下的数列如下:* t( j6 [% t3 J2 p0 r
    Every second number (all even numbers) is eliminated, leaving only the odd integers:
    4 a) M" j$ Q$ x3 [5 M" l1                3                5                7                9                11                13                15                17                19                21                23                25  ……. @/ T% I3 P6 Z3 q% F' z: A

      K8 m2 ^1 b/ A7 \' Z# M7 e接下来是3,每隔3个数字删除第三个。剩下的数列如下:; S1 _# m$ _/ N- p
    The second term in this sequence is 3. Every third number which remains in the list is eliminated:
    / [, c. {0 A7 P: [1                3                                7                9                                13                15                                19                21                                25  ……
    * J+ u( }0 @. D8 V1 e9 b4 K. R# e, D% T5 v1 V) ~* R5 L) l
    现在接下来的数字是7,所以把上述数列中每第七个删除,剩下的数列是:
    . y. E; J6 I; n4 p* u  T/ m* v# PThe next surviving number is now 7, so every seventh number that remains is eliminated:) C$ `# C# K* [- j4 D8 `8 |, n
    1                3                                7                9                                13                15                                                21                                25  ……' ?; V9 b0 p# p: z8 c
    2 t; o0 `; F6 q7 D, X7 a
    接下来是9,……
    $ {# k. |1 T' n$ s7 |5 a这个过程可以一直无限继续下去,被幸运地留下来的数字就是幸运数。% |% m: c; Z; x* n/ g
    : G2 e, F9 r# h
    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).& \$ F) T. c+ V0 u+ R% x
    在OEIS编号为A000959的数列就是Lucky numbers
    5 w: e: Q! l9 S( c" C上述链接给了一个稍微长一点的幸运数列:- I6 U4 Q9 s; \- N  e8 [
    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 ……
    & r4 i6 Q; a" ~+ \3 D* X% ], A% B) f
    有没有同样喜欢看数字的同学告诉我,你看了这个数列发现的是什么呢?
    * Q. a0 E2 r4 q% B% Z( q' U' U5 ]1 n' R" L
    8 t5 Z5 Y5 ^! \9 s
    ; H% b* C2 b7 X$ F3 ^: z# u  D
    第一个短一点的数列,我发现,1,3,5,7的平方(1,9,25,49)都是幸运数,但9的平方81就不是,于是马上想,那么是不是只有奇素数的平方才是幸运数呢?答案是不,11的平方也不是。于是叶子的第一个猜想就在几秒里被叶子证明是错误的。
    5 ^: x$ h$ u8 U0 }- i1 R
    & o  H+ v1 ?) b& p: b8 h数论里的各种数列是数学里最容易上手理解的,不过最迷人最折磨人的也是它。著名的例子就是哥德巴赫猜想(Goldbach's conjecture)。7 r/ J! J' {+ p+ D  ]( [
    幸运数的挑选过程,类似上面提到过的埃拉托斯特尼筛法挑选素数的过程,同时也和这个著名猜想有关。+ C0 P4 F3 \6 h, t
    另外幸运数也曾经在正式进入书面讨论的时候被建议叫做 "the sieve of Josephus Flavius",因为它的挑选让大家想到著名的约瑟夫斯问题。
    % i0 }: W; u  b' ]" X( w  }. \5 e7 @
    暂时就到这里吧,接下去要不要继续聊引出来的概念和问题呢?
    8 r: ^2 p" m8 _. P, u% d/ J, W+ ]$ S4 c
    **什么叫做Conjecture?
      \, Z1 ^% p5 ?  T/ r; {! D7 x$ I, Y**约瑟夫斯问题。

    评分

    参与人数 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), ?; P% A3 M4 ]
      W  U( M+ {1 D- A  G
    猜想(conjecture)是一个看上去是真的,但尚未被证明的叙述。比如说上面提到的数学数列,因为它表现的没有规律和无限性,基于观察的某些结论,如果不能用科学逻辑的方法来证明在无限的未来它都是真的,那么之前所观察到的所有事实都仅仅是看上去是正确的。
    0 f, v6 f4 u: b+ }
    ; l- v0 ]0 j; t+ p' h, ]7 D) o# G9 ^当猜想被证明后,它便会成为定理。猜想一日未成为定理,数学家都要小心在逻辑结构之中使用这些猜想。) P3 x9 r" h: L- y* ~

    7 i" M3 @3 Q) y) ?8 _7 i% g* {) o猜想主要因为类比推理和偶然发现的巧合而出现。数学家通常会使用不完全归纳法,来测试自己的猜想。例如费马曾经根据首四个费马数是素数,便猜想所有费马数都是素数(此猜想已被推翻)6 @: E3 V! {( [, f( ~1 A7 A

    * ]6 }) Q8 _* X; {, t假说(Hypothesis),即指按照预先设定,对某种现象进行的解释,即根据已知的科学事实和科学原理,对所研究的自然现象及其规律性提出的推测和说明,而且数据经过详细的分类、归纳与分析,得到一个暂时性但是可以被接受的解释。任何一种科学理论在未得到实验确证之前表现为假设学说或假说。
    " ?- |( P' v* y( N4 @" ^; G$ Y1 M/ J
    有的假设还没有完全被科学方法所证明,也没有被任何一种科学方法所否定,但能够产生深远的影响。如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 编辑
    * K4 H$ \0 W$ y* n- Y  x2 i
    1 Z  h9 u4 R( z4 p$ m5 L**约瑟夫斯问题    都教授
    5 S! W  _7 H! Z+ H* ^: M
    2 h( p9 s6 }6 n我们来聊聊约瑟夫斯问题。2 o9 }+ k) n' P# e

    5 l3 F+ |2 W9 |0 @0 O有n个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。0 g6 R3 v, T1 g  b; U8 D

    # S& d+ E- y5 n$ X! ?# Q/ `问题是,给定了n和k,一开始要站在什么地方才能避免被处决?) a  i. y7 `' p5 R" A; s& a

    4 ^! D0 y7 C: ]+ T
    0 W4 D! C% u+ x, D% L" V/ Q( P" Y. W$ s---------------------------------------不思考的分割线---------------------------------------------
    3 |: R0 ?1 W( @, n6 t据说这个问题是一个经常出现在计算机算法中的问题,不过当年我读书的时候对它并没有特别注意。在计算机编程的算法中,类似问题又称为约瑟夫环。老兵和神牛肯定比我清楚得多。我就不多说什么算法了。牛教授 兵教授  
    : W  Q/ W6 W3 Z' `; K( I4 g- p. c0 B# f3 c- H- O/ I
    ---------------------------------------历史八卦的分割线----------------------------------
    ( s8 v4 m7 j% ^" I. o( ^8 I这个问题是以弗拉维奥·约瑟夫斯命名的,他是1世纪的一名犹太历史学家。  _& z7 Y' H  ?& H# P# G
    据载,他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意。   

    该用户从未签到

    5#
    发表于 2014-7-17 09:30:00 | 只看该作者
    到处停留的叶子 发表于 2014-7-17 06:50 6 I& K2 |7 ]# w7 Q% T* _
    **约瑟夫斯问题    都教授
    1 T5 V  n) D$ s" m) n+ O& }5 }. L& s, H0 P) A( z" p
    我们来聊聊约瑟夫斯问题。
    0 A- [; a7 S9 X
    1. 经过努力学习,这题我能用java编程做了,oh yeah!
      F3 Y8 H2 L8 g0 S2 D$ g$ Q
    & S& I  l& D  q7 N  S' f2. 但叶子问我的不是编程。对于给定的k,我可以用倒推法硬推。但是,想了半天也没有想到不用推的直接算法。- t: P: ~$ D: m! A9 O
    / k1 F4 W/ q3 W* X; c8 L6 T4 Q
    推的方法如下:6 {6 C. N7 P& i
      j* m7 }9 G  X4 b1 e
    n=1,就一号,跑不掉的& _: `5 y+ c' P4 U
    n=2, 要站 (k+1) 模 n 那一号设a(2),比如 k=2, 则 a2=1 (号); 若 k=3, 则 a2=2
    ( q+ \* [  K0 u; C9 o如此类推,n=i 时,要站在 a(i-1)+k 模 n 那一号。比如,k=6, n=19 时 要站在14号。
    / H  @& u6 Q" H% \* U+ b6 _6 o9 ?0 |: t$ i

    " ~( n8 X5 P, p+ M; k7 H. c我算到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 编辑
    , s. o6 O3 G& e3 w. m' b# I6 Q$ y
    独角兽 发表于 2014-7-16 20:30
    9 S5 x% u8 Q8 }$ e  N+ H& N/ b1. 经过努力学习,这题我能用java编程做了,oh yeah!
    + V' z2 v$ E% I
    : H: J6 H9 z2 D! F" g0 |2. 但叶子问我的不是编程。对于给定的k,我可以用 ...
    4 {! S& r$ R# G0 I2 l' Y- ]

      K; J. l" \: g! S  \兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看
    7 L' n- ?4 _' u3 f# P
      m. ^4 n0 }4 M9 R/ o在维基上看到K=2的解法和还有K≠2的通用解法,这里摘抄过来那段关于n的有趣分析。
      N1 A' b" P" D4 |( b  }6 o
    3 `. M  s" H1 r还有下面我抄了两个通用算法,那个java的是不是和你做的一样啊?
    3 E; Z1 I; y* m) e0 u
    9 M) v8 k8 u2 [, ~0 T; n3 e4 b/ v-----------------------------不动脑筋的分割线--------------------------$ W3 @' b3 F/ X, c! w
    5 E% g8 ~, y" H; {
    一个小心翼翼的Java例子:6 g6 ]& H- U) `; V- n( D  z
    ' E' b) u$ w, Y4 X8 i8 B, T) d
    int josephus(int n, int k) {2 {$ Z" M! _) R. c# C, v0 y7 I2 z
            return josephus(n, k, 1);
    ! v6 l* n" i% V( T. U, \  }
    6 B5 g$ V) C- m4 T5 L, ]4 S* G+ b  int josephus(int n, int k, int startingPoint) {; Q# I' D% H# {* J
          if(n == 1)
    9 j. i, O( p$ [2 A5 ^$ t          return 1;# r4 e# d) u- \
          int newSp = (startingPoint + k - 2) % n + 1;* f8 o" j5 J4 q6 W: _7 R6 C6 M

    7 r. @, ~& P" E      int survivor = josephus(n - 1, k, newSp);4 H7 C0 Q* o1 u3 Y7 M! k  }$ D
          if (survivor < newSp) {* n" }5 \5 m. j+ @! \' `6 F
              return survivor;
    $ s7 R+ M  o1 C, f* c6 o1 w      } else5 i8 v) l+ [. E/ q6 p! `
              return survivor + 1;- K3 \( g) m1 m2 ]. K
      }1 J. V9 r+ @; Z0 N, N+ h% G
    ( {" P% H3 r8 p- j$ r
    另外有个更简洁的例子$ K# |3 C: U) l0 c0 S
      def josephus(n, k):
    " g6 |8 j) z: J+ N( i    if n ==1:
    9 b! b4 c! p' f: {3 O      return 1
    ! r0 U  w; Z8 r5 o) ?    else:+ U* ^( Z$ k  [$ l4 H! T9 J, G
          return ((josephus(n-1,k)+k-1) % n)+1
    4 n3 K, t& j! W3 `! z* X
    6 o( t3 f2 I) g9 O; @(如果n这个数字很大很大,k很小很小,电脑会不会转晕过去呢?)+ M# g' k" o& A/ s0 v
    " C. f+ ?2 G# L( _; o% }
    以上摘自 http://en.wikipedia.org/wiki/Josephus_problem#Solution4 S" y% ^  {% k+ ^* U. l5 `
    1 Y9 N+ f2 U3 U" |7 r2 V
    7 s$ W! {& ]' |9 }/ L
    关于n的分析:7 W+ v+ G* \  J7 d0 M
    设f(n)为一开始有n个人时,生还者的位置。- m. @4 k& S/ S0 R+ I0 b! ?# p
    如果一开始有偶数个人,则第二圈时位置为x的人一开始在第2x - 1个位置。因此位置为f(2n)的人开始时的位置为2f(n) - 1。这便给出了以下的递推公式:- Z$ ]" ]+ W3 ]' n

    9 M6 r* w, _0 |8 E0 u8 C  Nf(2n)=2f(n)-1
    5 ^5 j' b& v  y( c, Q; F- J1 V如果一开始有奇数个人,则走了一圈以后,最终是号码为1的人被杀。于是同样地,再走第二圈时,新的第二、第四、……个人被杀,等等。在这种情况下,位置为x的人原先位置为2x+1。这便给出了以下的递推公式:, r, E4 U* |" f" D8 d0 y0 N

    ' S& h. Y/ n* m) k* k# A8 uf(2n+1)=2f(n)+1. A: T5 X$ Q3 z, o; K
    % H3 s" x) d' g% i- R2 D  w& [+ R

    + U7 E  ^2 {: e9 [- o( M如果我们把n和f(n)的值列成表,我们可以看出一个规律:
    " l: D5 o" Y/ c: x1 A. c% x5 \
    % K: ]2 Y9 b/ z4 Cn    1    2        3        4        5        6        7        8        9        10        11        12        13        14        15    16) `7 f3 A! W: B) P0 d+ E
    f(n) 1    1        3        1        3        5        7        1        3        5        7        9        11        13        15        1
    ) o+ ]# q# G+ Y4 s4 B
    + E' P3 y" a7 @8 ^6 W从中可以看出,f(n)是一个递增的奇数数列,每当n是2的幂时,便重新从f(n)=1开始。因此,如果我们选择m和l,使得n=2^m+l且0≤ l<2^m,那么f(n)=2 . l+1。显然,表格中的值满足这个方程。可以用数学归纳法给出一个证明。$ Z, j/ ]0 z" d9 s7 p2 i* d
    5 x3 P4 C4 h: A" }1 [; c6 c' S1 ~
    定理:如果n=2^m+l且0≤ l<2^m,则f(n) = 2.l+1。( K& |( R0 A  m0 q6 H# S

    * {; r4 M9 B( U5 }! M+ t3 g
    3 P& s' Z) D5 T& m8 |) _7 E答案的最漂亮的形式,与n的二进制表示有关:把n的第一位移动到最后,便得到f(n)。这可以通过把n表示为2^m+l来证明。

    该用户从未签到

    7#
    发表于 2014-7-17 11:19:06 | 只看该作者
    到处停留的叶子 发表于 2014-7-17 11:02 $ d7 _& z1 q" W
    兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看
    + h! ]' i: [+ z% I- ~# P
    5 g6 [6 ?5 R, s$ e' m在 ...
    9 m% a4 T6 X6 k" @$ s! i% M
    我的推法就是这个:
    1 z# R9 F- B/ o+ f+ [
    5 e$ z3 d& j6 ?) z$ N1 t  }  return ((josephus(n-1,k)+k-1) % n)+1- V5 c+ f  {8 M3 K, h
    3 L4 O0 K, t7 t3 M0 t8 d
    我有一点疏忽是如果整除,模的结果是0,但实际应该取n。所以这个表达式把 "+1"搞到括号外面就完全对了。$ k- _3 ~) t1 T1 m7 U' d* z8 P0 Y

    ! n2 Z* x8 I3 r% I2的情况我没单拿出来搞。
  • TA的每日心情
    奋斗
    前天 12:07
  • 签到天数: 1359 天

    [LV.10]大乘

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

    [LV.Master]无

    9#
    发表于 2014-7-18 22:40:37 | 只看该作者
    看不懂
    . G$ K! v9 U: r) Y6 O0 ]6 f不过今天不幸运数是17
  • TA的每日心情
    擦汗
    2020-3-23 00:29
  • 签到天数: 134 天

    [LV.7]分神

    10#
     楼主| 发表于 2014-7-19 03:04:00 | 只看该作者
    常挨揍 发表于 2014-7-18 09:40
    3 ]4 f' |. }$ K) ~) }( |看不懂: t* H. r4 x6 e9 @) g  e
    不过今天不幸运数是17
    $ X  C- \# t) @6 s
    7月17日成了一个黑色的日子。很让人感觉生命无常。1 t1 T  t3 {6 }- T- e
    % c# J" r; A, Q3 M; o, y% H
    以后出行挑日子,要找一个幸运数的交集,这里前面的9个数字也可以参考一下:1,3,7,9,13,15,21,25,31
    2 h: v. Z4 E! ]4 ^9 J* G/ Q' v* r% `3 U2 N2 y/ T5 Y
    13号如果遇上星期五,还是算了,不要不信邪。

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

    GMT+8, 2026-6-28 02:56 , Processed in 0.069645 second(s), 22 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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