设为首页收藏本站

爱吱声

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

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

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

    [LV.7]分神

    跳转到指定楼层
    楼主
    发表于 2014-7-16 11:30:51 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    上次说到  小小的停留之三 “计算机之父” 天才的数学家冯·诺伊曼6 u$ y3 N- s( W* l8 P1 @: a
    看冯·诺伊曼的故事,他有句名言:“若人们不相信数学简单,只因他们未意识到生命之复杂。”$ h; l7 ]; w, W- }1 f( E) C- G

    % G3 o: W4 w, p6 B: x3 {他有个好朋友,据说是最好的朋友,是生于匈牙利的波兰犹太人数学家乌拉姆,这位先生曾参与曼克顿计划(核武器上有Teller-Ulam design,Teller指爱德华·泰勒)。他亦有参与研究核能推动的航天飞机。在纯数学上,遍历理论、数论、集合论和代数拓扑都有他的足迹。
    & q8 U+ Y0 v1 W7 i7 a
    . h4 k2 m4 Z9 Y' T0 j  y) ~所以我在这里要说的幸运数不是中餐馆的饼干里给你的数字,也不是买彩票开奖的数字,而是在1955年波兰数学家乌拉姆提出的一个自然数列,用类似埃拉托斯特尼筛法的算法后留下的整数集合。" O4 L1 s+ |9 F8 [/ F" o/ e# l
    - m, ^' ?: {( k4 F: C
    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.
    , Z, ]1 i7 u9 b1 B. r
    9 l/ t$ g& d- W; }& T! j8 d幸运数的定义
    4 `! f4 Q$ A$ T8 Q1 N+ H  `1 b2 S* oFORMULA       
    - ?& I4 w; i+ v* E+ H" Y7 ?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.
    , S" U9 K  R: W8 x7 y$ V/ E' P
    ' E, ]* Q: W9 Z' Y7 Y具体一点来说说幸运数列怎么筛选出来的(喜欢数论的同学一定知道挑选素数的埃拉托斯特尼筛法,这个办法是类似的)
    7 M" E8 f$ ^$ h/ e) b: H4 E. l0 G+ b
    初始,从1开始的自然数列:
    ! t" G, ^) c; _6 e8 R) ZBegin with a list of integers starting with 1:6 {" G% @8 J$ X+ x% L& }
    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  ……% N& R' q, J3 a: P$ F
    : o4 S+ |1 b0 q* ^
    开始删除,在这个数列里,从2开始,首先是每隔2个数字,删除第二个数字。剩下来的数字是奇数~~& ?1 m1 O8 t0 W. j" V9 U( H2 i
    剩下的数列如下:1 H5 m2 U# m' K
    Every second number (all even numbers) is eliminated, leaving only the odd integers:
    1 c! V+ m3 S; Z+ P$ z1                3                5                7                9                11                13                15                17                19                21                23                25  ……
    - F4 \  @, h  o% t7 F& a2 h9 D4 f3 G& ~$ k& F' A
    接下来是3,每隔3个数字删除第三个。剩下的数列如下:: v& L- `- T9 }) z  L, v
    The second term in this sequence is 3. Every third number which remains in the list is eliminated:( e8 D2 l, g$ e* X( ]
    1                3                                7                9                                13                15                                19                21                                25  ……
    : g5 g9 V) `6 b7 U' S2 o! v' k8 ~/ e
    " l5 O+ _) |8 G8 j4 R+ m现在接下来的数字是7,所以把上述数列中每第七个删除,剩下的数列是:
    4 }% l( Z6 s4 N9 y# G4 l' {2 fThe next surviving number is now 7, so every seventh number that remains is eliminated:
    " w$ X( i4 G, ^. Z0 m; P1                3                                7                9                                13                15                                                21                                25  ……
    2 q2 b9 a- U4 _# L, o( i8 k( l+ V; t
    3 G3 F; i2 r; P2 ]6 ~' a9 A4 j8 p接下来是9,……3 R, a5 B3 U% y/ S( w
    这个过程可以一直无限继续下去,被幸运地留下来的数字就是幸运数。8 U8 V( H, W4 |, l$ v0 h
      B2 x; H' _! J% S+ r$ b" M
    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).- x" Q, A+ d5 }: O& @$ U
    在OEIS编号为A000959的数列就是Lucky numbers
    $ P; A+ e2 g) `1 {, n上述链接给了一个稍微长一点的幸运数列:
    " Y% e" B. g% E( t" e& B8 Y1, 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 ……% `6 p, F& r) N$ c) u5 ]

    8 O3 }. ?. O' u有没有同样喜欢看数字的同学告诉我,你看了这个数列发现的是什么呢?
    / m: Q' x/ E( n% E
    % L1 ]; B- F# }0 B+ K, q& |; {$ Q8 _* F4 Q
    ! P3 ?; K+ Y: l8 V- j9 B
    第一个短一点的数列,我发现,1,3,5,7的平方(1,9,25,49)都是幸运数,但9的平方81就不是,于是马上想,那么是不是只有奇素数的平方才是幸运数呢?答案是不,11的平方也不是。于是叶子的第一个猜想就在几秒里被叶子证明是错误的。
    3 v& R/ P( Z+ n8 M  [1 u: K& ~' y
    # C+ _4 Y* r! S/ d数论里的各种数列是数学里最容易上手理解的,不过最迷人最折磨人的也是它。著名的例子就是哥德巴赫猜想(Goldbach's conjecture)。3 F8 ~/ @! r8 K) _- {+ v
    幸运数的挑选过程,类似上面提到过的埃拉托斯特尼筛法挑选素数的过程,同时也和这个著名猜想有关。
    / @5 n) v7 i+ ?, k( N6 \另外幸运数也曾经在正式进入书面讨论的时候被建议叫做 "the sieve of Josephus Flavius",因为它的挑选让大家想到著名的约瑟夫斯问题。
    7 @+ \- \$ I' E' Z. t
    * V4 Y# x" p5 i8 V/ i8 M1 S暂时就到这里吧,接下去要不要继续聊引出来的概念和问题呢?0 P3 P" z7 ]0 m6 h1 _# a. n

    ' h' T: n( n% A' D. o8 W: ~**什么叫做Conjecture?
    8 I' g) H0 r) Z' J! g" J, c: A**约瑟夫斯问题。

    评分

    参与人数 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)& e7 H  w$ T6 x/ O3 T$ x2 z

    - B3 f% ]/ r" Y+ `2 O; L猜想(conjecture)是一个看上去是真的,但尚未被证明的叙述。比如说上面提到的数学数列,因为它表现的没有规律和无限性,基于观察的某些结论,如果不能用科学逻辑的方法来证明在无限的未来它都是真的,那么之前所观察到的所有事实都仅仅是看上去是正确的。
    / G" M, D. T2 B- I# ]% K' Z. ]1 O# H+ x0 q
    当猜想被证明后,它便会成为定理。猜想一日未成为定理,数学家都要小心在逻辑结构之中使用这些猜想。
    0 {0 q$ c) o) t( K9 p
    ' r% Y8 A% G2 N2 O猜想主要因为类比推理和偶然发现的巧合而出现。数学家通常会使用不完全归纳法,来测试自己的猜想。例如费马曾经根据首四个费马数是素数,便猜想所有费马数都是素数(此猜想已被推翻)$ |  [5 ^" b+ T" y0 q
    * N/ ~+ v" W9 y% u) o+ @6 a! |
    假说(Hypothesis),即指按照预先设定,对某种现象进行的解释,即根据已知的科学事实和科学原理,对所研究的自然现象及其规律性提出的推测和说明,而且数据经过详细的分类、归纳与分析,得到一个暂时性但是可以被接受的解释。任何一种科学理论在未得到实验确证之前表现为假设学说或假说。3 L& v* {6 R. s: t! w: _4 `
    * @' |6 l; j! U% a8 |4 A2 V
    有的假设还没有完全被科学方法所证明,也没有被任何一种科学方法所否定,但能够产生深远的影响。如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 编辑 6 U: f& H' ?# w

    / U! k( L5 _2 ]) O, w  o5 Z**约瑟夫斯问题    都教授
    1 q: w4 K0 s' Q  Y7 R/ U* V
    ! N9 i' p, h5 `2 }我们来聊聊约瑟夫斯问题。% {( y# H1 }4 \' Z) b

    + q2 b0 d/ Y; D9 V6 i有n个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。
    ; D2 @1 M5 e% a4 A- p, C( R, G" o' p7 [0 v3 Q3 b0 D5 l  r2 v
    问题是,给定了n和k,一开始要站在什么地方才能避免被处决?: d! C5 z$ O, `5 O. o4 u

    ; x; x* E2 b1 F# [+ L- _, t, L* ~# S3 p9 N& I6 ?6 n( z
    ---------------------------------------不思考的分割线---------------------------------------------
    ( w( _' v. r+ J5 c据说这个问题是一个经常出现在计算机算法中的问题,不过当年我读书的时候对它并没有特别注意。在计算机编程的算法中,类似问题又称为约瑟夫环。老兵和神牛肯定比我清楚得多。我就不多说什么算法了。牛教授 兵教授  
    $ A4 V5 ?$ s, f$ }6 N/ G7 \" C$ r& b5 y8 n- {
    ---------------------------------------历史八卦的分割线----------------------------------2 C& U# G* m9 o% ^) A) c/ V
    这个问题是以弗拉维奥·约瑟夫斯命名的,他是1世纪的一名犹太历史学家。
    1 v* l, f7 V3 R7 c, E据载,他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意。   

    该用户从未签到

    5#
    发表于 2014-7-17 09:30:00 | 只看该作者
    到处停留的叶子 发表于 2014-7-17 06:50
    4 r% ]; z& d; i: B# m+ j3 F**约瑟夫斯问题    都教授 # O4 j- x: ^, m- o  t! e$ g
    2 |2 H$ g1 p& M1 ?6 Y
    我们来聊聊约瑟夫斯问题。
      u! O* l. T7 E* a6 q* r6 h
    1. 经过努力学习,这题我能用java编程做了,oh yeah!
    9 h" q& F% @/ ~: S, J9 z& L9 i
    / V, {: u; g2 I- b) |( }. D/ ~2. 但叶子问我的不是编程。对于给定的k,我可以用倒推法硬推。但是,想了半天也没有想到不用推的直接算法。; y7 D5 F& q# g' k

    / S; m$ O5 ^' f! `. p* }2 i( O- V推的方法如下:
    # R/ q" E5 |/ V& Q# v2 A/ f$ j. V( W; j/ C$ R
    n=1,就一号,跑不掉的
    ' f- u6 {3 q' m. o; {: on=2, 要站 (k+1) 模 n 那一号设a(2),比如 k=2, 则 a2=1 (号); 若 k=3, 则 a2=2 5 I/ l# h6 s! R1 N% }! C
    如此类推,n=i 时,要站在 a(i-1)+k 模 n 那一号。比如,k=6, n=19 时 要站在14号。* L$ W2 y, L% j0 a

    ; ~1 C3 R1 o2 t% U3 M' A4 u* A& V% w  ]6 e3 e+ H8 C' k: F
    我算到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 编辑
    # A& {/ n6 X, H$ ?+ n4 g4 L
    独角兽 发表于 2014-7-16 20:30 # ]6 P. u. h7 ~  b
    1. 经过努力学习,这题我能用java编程做了,oh yeah!
    ! g* @! l* A6 }9 v6 g9 k. l: M+ u' Q$ A) t
    2. 但叶子问我的不是编程。对于给定的k,我可以用 ...
    # J* F; P7 \6 _. P+ g
    % M  R$ q0 T" Q: H9 M. W: M
    兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看
    ' I9 g7 Q; i# V6 [0 W# j1 n% @  w0 v& U
    在维基上看到K=2的解法和还有K≠2的通用解法,这里摘抄过来那段关于n的有趣分析。( M) g: l' l' z# _

    # C4 J5 h) e1 Y1 r2 x( a还有下面我抄了两个通用算法,那个java的是不是和你做的一样啊?# A- S6 i: b* ~/ Y7 N7 L2 l' M
    " @; m" ]& I7 C! T7 @
    -----------------------------不动脑筋的分割线--------------------------
    ) R" O9 H* \/ ?* x, v, e( c" Q! V" M7 [# {
    一个小心翼翼的Java例子:* g3 G4 Y- t, r# A1 D) d1 B- I
    - _3 n( l3 w' F! t
    int josephus(int n, int k) {
    5 \8 k# H+ H% {# V- R. Q        return josephus(n, k, 1);# t% ?+ f% Y, c. U0 e
      }
    " p$ ]8 Z5 p3 I7 ~0 j. I  int josephus(int n, int k, int startingPoint) {5 @! y' Y) V4 k* o! |7 ]
          if(n == 1)
    ) Z0 \2 t, u8 i' g! g! o          return 1;
    9 s; _1 p( S; F1 U" Y0 W! q      int newSp = (startingPoint + k - 2) % n + 1;
    ' \7 y$ L. |0 z  E- I( y5 f8 ?
    * v" x7 v5 Z. w7 R" H      int survivor = josephus(n - 1, k, newSp);5 N4 f1 O9 ^: A
          if (survivor < newSp) {' W5 g& M9 B4 F8 V0 |
              return survivor;8 [4 j& f6 T2 u; z5 Z
          } else
    ) L4 K  \, s4 P          return survivor + 1;' E2 U9 A/ ?3 F+ V
      }# ]/ i6 i7 G; j* w: s/ t" o4 ~
    " q# \2 @+ Y$ O7 r, A( r- f
    另外有个更简洁的例子
    : P! G6 A0 J3 q9 V& {+ U  def josephus(n, k):
    ; B2 q2 L. m1 v    if n ==1:
    ) e9 W& _% c  g3 U* G1 ]      return 1' Q7 P/ d( r" p5 X; t; g: R
        else:
    & B/ q2 V& ~. W$ g" A4 }      return ((josephus(n-1,k)+k-1) % n)+12 Z, ?- e% n7 s7 k' A: }4 t0 Q
    % i' m' W* G& o! z1 h
    (如果n这个数字很大很大,k很小很小,电脑会不会转晕过去呢?)) u* K* @" Y3 V# G8 p% Z
    8 a- s! `$ D- v2 r2 |& k' _
    以上摘自 http://en.wikipedia.org/wiki/Josephus_problem#Solution
    8 H7 `6 f0 _- I9 t4 s4 T; Q
    7 v4 s$ r; m5 y+ s4 p0 T' ]8 l% M+ h9 \
    关于n的分析:
    ; W% [& F* \0 U- ^" ]% w1 K设f(n)为一开始有n个人时,生还者的位置。
    8 Z; r2 `9 x% p6 Z+ }: @如果一开始有偶数个人,则第二圈时位置为x的人一开始在第2x - 1个位置。因此位置为f(2n)的人开始时的位置为2f(n) - 1。这便给出了以下的递推公式:
    3 e' d- v3 u' G& k; Y5 r" u+ t9 [( i' |
    f(2n)=2f(n)-1
    ! X% i; x" A5 `2 j+ ?如果一开始有奇数个人,则走了一圈以后,最终是号码为1的人被杀。于是同样地,再走第二圈时,新的第二、第四、……个人被杀,等等。在这种情况下,位置为x的人原先位置为2x+1。这便给出了以下的递推公式:% c) |$ K" y' k" b2 Y+ R
      z! B9 m0 G  S5 [7 O; n
    f(2n+1)=2f(n)+1
    7 f; m/ U, ~8 `) g2 q
    ! Z6 W# W7 X2 n0 L) T
    + A+ i) M: T# O( h如果我们把n和f(n)的值列成表,我们可以看出一个规律:
    0 a  F3 X* B% ?- T* u* _
    ! H6 K( c. M' ?. U* _$ s8 G- x4 _n    1    2        3        4        5        6        7        8        9        10        11        12        13        14        15    163 m2 m3 ^5 b* F4 `7 b" `
    f(n) 1    1        3        1        3        5        7        1        3        5        7        9        11        13        15        1; ]: `- U9 I6 @6 R3 ^7 e

    # c  i1 Y4 g: n) o$ @1 W$ e/ M从中可以看出,f(n)是一个递增的奇数数列,每当n是2的幂时,便重新从f(n)=1开始。因此,如果我们选择m和l,使得n=2^m+l且0≤ l<2^m,那么f(n)=2 . l+1。显然,表格中的值满足这个方程。可以用数学归纳法给出一个证明。$ t& R; d4 f6 |; v' Q% K

    0 }* [2 ?9 ]) K: g定理:如果n=2^m+l且0≤ l<2^m,则f(n) = 2.l+1。
    $ s5 {# `  h' y1 o$ [5 x; l- U& X! |. Q+ r0 e# R0 A" Y

    $ S: u- R, h* g* Z' f  O答案的最漂亮的形式,与n的二进制表示有关:把n的第一位移动到最后,便得到f(n)。这可以通过把n表示为2^m+l来证明。

    该用户从未签到

    7#
    发表于 2014-7-17 11:19:06 | 只看该作者
    到处停留的叶子 发表于 2014-7-17 11:02
    : E+ T1 V! \8 l) H* Y, g兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看
    2 v0 J& r. Y( u$ n- f' l; e) H$ s! x- A1 T$ ~
    在 ...

    / `7 P6 {+ r# Q6 \: F我的推法就是这个:% G  D0 a. J& B
    9 a/ U: L7 t1 O" V7 `; a2 V+ A
      return ((josephus(n-1,k)+k-1) % n)+1, |8 G" N' b: `# S

    6 k7 l. p: ~4 _" S2 J我有一点疏忽是如果整除,模的结果是0,但实际应该取n。所以这个表达式把 "+1"搞到括号外面就完全对了。
    . L0 f1 C1 ~' B: z# R
    & M6 ^# T+ P% c# f* `2的情况我没单拿出来搞。
  • TA的每日心情
    慵懒
    2020-5-10 00:00
  • 签到天数: 1237 天

    [LV.10]大乘

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

    [LV.Master]无

    9#
    发表于 2014-7-18 22:40:37 | 只看该作者
    看不懂
    # |$ D7 u+ \' s不过今天不幸运数是17
  • TA的每日心情
    擦汗
    2020-3-23 00:29
  • 签到天数: 134 天

    [LV.7]分神

    10#
     楼主| 发表于 2014-7-19 03:04:00 | 只看该作者
    常挨揍 发表于 2014-7-18 09:40
    ) N9 S& l) {5 O* c看不懂
    7 @* C$ H+ h6 J' o8 v+ N/ k6 a不过今天不幸运数是17

    & U5 J: D/ {+ h% b) @& x, u7月17日成了一个黑色的日子。很让人感觉生命无常。
    % J& K0 [$ n( f9 h  P! W. r# ^  d/ [' D; N4 _% Q
    以后出行挑日子,要找一个幸运数的交集,这里前面的9个数字也可以参考一下:1,3,7,9,13,15,21,25,31
    3 D( T1 b7 z( E8 ]5 Y4 c! {+ _/ q5 O$ u' W; }+ E, P
    13号如果遇上星期五,还是算了,不要不信邪。

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

    GMT+8, 2025-4-26 13:29 , Processed in 0.045089 second(s), 22 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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