设为首页收藏本站

爱吱声

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

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

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

    [LV.7]分神

    跳转到指定楼层
    楼主
    发表于 2014-7-16 11:30:51 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    上次说到  小小的停留之三 “计算机之父” 天才的数学家冯·诺伊曼$ a# x7 t6 X& G6 B# ~7 n
    看冯·诺伊曼的故事,他有句名言:“若人们不相信数学简单,只因他们未意识到生命之复杂。”8 t7 E) m9 V- \- U) y( Y/ h
    ; J* G' k7 G# n- n
    他有个好朋友,据说是最好的朋友,是生于匈牙利的波兰犹太人数学家乌拉姆,这位先生曾参与曼克顿计划(核武器上有Teller-Ulam design,Teller指爱德华·泰勒)。他亦有参与研究核能推动的航天飞机。在纯数学上,遍历理论、数论、集合论和代数拓扑都有他的足迹。( c5 i5 r+ i( @) U

    ( w7 I' b: e: k* ?5 k* j所以我在这里要说的幸运数不是中餐馆的饼干里给你的数字,也不是买彩票开奖的数字,而是在1955年波兰数学家乌拉姆提出的一个自然数列,用类似埃拉托斯特尼筛法的算法后留下的整数集合。7 ~. s9 y6 u6 j+ w6 A: \7 n: R8 |

    % d% K6 y# T/ x: XIn 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.
    ( |0 E4 _; z9 c9 z; a
    / ?# {/ v$ C+ ~幸运数的定义
    - H8 L. B2 Z1 ^0 U! c, V5 }FORMULA        7 f4 Y9 S) Y. l2 b
    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.
    $ A! q! ]  P0 }6 y) c, G! o1 A; w, `3 h
    具体一点来说说幸运数列怎么筛选出来的(喜欢数论的同学一定知道挑选素数的埃拉托斯特尼筛法,这个办法是类似的)
    . q- M3 ^( s4 E& _9 u
    ; L. H% \/ ~2 j% a2 |' g5 I5 D9 \2 i初始,从1开始的自然数列:
    ! w' K" v/ P" @" }, ^4 SBegin with a list of integers starting with 1:
    / h* J. a8 R' G& ~( d# C( l1        2        3        4        5        6        7        8        9        10        11        12        13        14        15        16        17        18        19        20        21        22        23        24        25  ……
    0 ?: v" D/ s7 L5 w: C5 ~4 j' i  J3 G3 y* Z
    开始删除,在这个数列里,从2开始,首先是每隔2个数字,删除第二个数字。剩下来的数字是奇数~~. m8 D; {7 S- G( @! Y
    剩下的数列如下:2 i" e5 X: w, G
    Every second number (all even numbers) is eliminated, leaving only the odd integers:
    0 r$ D% }( s+ m: y) s2 {4 A8 q1                3                5                7                9                11                13                15                17                19                21                23                25  ……
    * [9 q0 ^0 ?6 X- T; d  y" f7 j) C6 M: z* F4 ~
    接下来是3,每隔3个数字删除第三个。剩下的数列如下:
    0 p; V: D: Y- o6 K7 ?The second term in this sequence is 3. Every third number which remains in the list is eliminated:
    2 Y' ^1 c6 R8 i1                3                                7                9                                13                15                                19                21                                25  ……
    $ E& ^3 G/ r' X! x0 Y& k% ]! H6 N( E8 A- x. u0 R
    现在接下来的数字是7,所以把上述数列中每第七个删除,剩下的数列是:
    " K" I. d' g1 `The next surviving number is now 7, so every seventh number that remains is eliminated:
    % l, u! p0 ~$ J4 E1                3                                7                9                                13                15                                                21                                25  ……
      h/ T0 Q0 c' e* g* R/ s8 u$ V6 [7 G$ L0 ]$ w( [: t+ _& {4 m( I* _/ k
    接下来是9,……
    ! c8 T: x0 `) G; e$ ?0 ]* C这个过程可以一直无限继续下去,被幸运地留下来的数字就是幸运数。
    2 u7 L( ^5 j4 A% H9 h1 x3 t7 ]1 R: u' G8 z. m! o+ y* |
    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).6 P% ~5 E% e* a0 b4 g: i
    在OEIS编号为A000959的数列就是Lucky numbers
    % J1 J# C- H$ r: i) v上述链接给了一个稍微长一点的幸运数列:
    * F4 ]% @7 `' g  O/ q2 B1, 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 ……
    ! V& y6 v) p" _) N+ L+ Q2 C3 F1 q1 {; \- r/ {# _
    有没有同样喜欢看数字的同学告诉我,你看了这个数列发现的是什么呢?
    * ^3 I+ n! c2 e4 o. [
    $ Q. M2 G* U: P: I: o9 O( X6 A1 V6 @, A! v8 p7 V; Y( U
    , I+ x5 [9 n0 H/ h3 N) B
    第一个短一点的数列,我发现,1,3,5,7的平方(1,9,25,49)都是幸运数,但9的平方81就不是,于是马上想,那么是不是只有奇素数的平方才是幸运数呢?答案是不,11的平方也不是。于是叶子的第一个猜想就在几秒里被叶子证明是错误的。
    0 ~- E1 Z% E5 t6 z8 R  ?
    0 |2 G( a; {* e2 B* M数论里的各种数列是数学里最容易上手理解的,不过最迷人最折磨人的也是它。著名的例子就是哥德巴赫猜想(Goldbach's conjecture)。/ Q8 g) J( P$ p: H) x
    幸运数的挑选过程,类似上面提到过的埃拉托斯特尼筛法挑选素数的过程,同时也和这个著名猜想有关。
    # j8 B* A- D* W6 ?另外幸运数也曾经在正式进入书面讨论的时候被建议叫做 "the sieve of Josephus Flavius",因为它的挑选让大家想到著名的约瑟夫斯问题。
    / }; h! H1 u0 {8 l% M$ f% [! z2 @$ F) R8 j2 l/ J$ K
    暂时就到这里吧,接下去要不要继续聊引出来的概念和问题呢?: G. y( p/ D0 B$ T# E; b' e* A
    2 X# j, M' I. }9 F1 g+ s
    **什么叫做Conjecture?
    * _# j, K; g2 b9 {$ l# I**约瑟夫斯问题。

    评分

    参与人数 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)
    - c0 P' {% j" }; [) \# W0 v
    ) l" {+ F' @" c( X3 g+ X1 Z猜想(conjecture)是一个看上去是真的,但尚未被证明的叙述。比如说上面提到的数学数列,因为它表现的没有规律和无限性,基于观察的某些结论,如果不能用科学逻辑的方法来证明在无限的未来它都是真的,那么之前所观察到的所有事实都仅仅是看上去是正确的。
    , g  `% S8 i& j7 p; }
    . H. K- r" o$ z" w9 }3 f当猜想被证明后,它便会成为定理。猜想一日未成为定理,数学家都要小心在逻辑结构之中使用这些猜想。0 c- B' `( Q$ B/ p  k, x" w
    4 O! v6 f1 Z& O# z. {
    猜想主要因为类比推理和偶然发现的巧合而出现。数学家通常会使用不完全归纳法,来测试自己的猜想。例如费马曾经根据首四个费马数是素数,便猜想所有费马数都是素数(此猜想已被推翻)1 k, T% J7 q4 e8 T) ?( |: C

    " g+ J( a$ N1 r4 N假说(Hypothesis),即指按照预先设定,对某种现象进行的解释,即根据已知的科学事实和科学原理,对所研究的自然现象及其规律性提出的推测和说明,而且数据经过详细的分类、归纳与分析,得到一个暂时性但是可以被接受的解释。任何一种科学理论在未得到实验确证之前表现为假设学说或假说。1 x* p; U; i# V8 f8 m

    3 p6 S& P$ i! ^9 b* E0 M  ?1 B有的假设还没有完全被科学方法所证明,也没有被任何一种科学方法所否定,但能够产生深远的影响。如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 编辑 2 i7 m5 |! `8 @5 `
    4 K6 U% q4 s- t8 m  \
    **约瑟夫斯问题    都教授 ( m) P" ?, x( `. ?# S- k
    1 M/ t0 Q9 D: |7 X1 c2 Y
    我们来聊聊约瑟夫斯问题。
    1 e: W! J9 f8 [  T7 a0 U9 a8 @  x$ W. \. T9 {- q; ?1 C
    有n个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。
    : Y9 ~4 B4 ~5 n, P6 M
    8 [0 {* l) R+ E问题是,给定了n和k,一开始要站在什么地方才能避免被处决?) D* r; A, D" U; V2 ^5 Z

    1 y* q8 r; L* J" d" M
    # d, F1 G( p: z* e9 I: F---------------------------------------不思考的分割线---------------------------------------------
    ; U# A5 N6 e& c! n- O: C4 g据说这个问题是一个经常出现在计算机算法中的问题,不过当年我读书的时候对它并没有特别注意。在计算机编程的算法中,类似问题又称为约瑟夫环。老兵和神牛肯定比我清楚得多。我就不多说什么算法了。牛教授 兵教授  - Q  u( q+ u1 R- J9 c2 X
    8 q* L6 |8 B' K1 x. g5 q; U
    ---------------------------------------历史八卦的分割线----------------------------------
    7 e, K* V1 g' J; a3 X这个问题是以弗拉维奥·约瑟夫斯命名的,他是1世纪的一名犹太历史学家。
    ! B- u# x, N6 f6 s0 \6 u据载,他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意。   

    该用户从未签到

    5#
    发表于 2014-7-17 09:30:00 | 只看该作者
    到处停留的叶子 发表于 2014-7-17 06:50 6 M7 w( L  }+ t$ x. \
    **约瑟夫斯问题    都教授
    4 @# l$ s  X% q( U7 \1 N2 S+ J! ^( e8 b" U  e- O' S3 J
    我们来聊聊约瑟夫斯问题。

    8 E. O. L, z3 `( V* B1. 经过努力学习,这题我能用java编程做了,oh yeah!% @, }$ ?! }; t8 i- ]# W& e7 Q

    ' D  K! o4 w2 q# @, r' a4 P, q; [2. 但叶子问我的不是编程。对于给定的k,我可以用倒推法硬推。但是,想了半天也没有想到不用推的直接算法。7 \( s) V+ F- a* V. Z- \4 F
    $ E1 K" K: m% j% B) }# ~
    推的方法如下:
    0 x3 f# h6 R# |  C/ i
      I9 Z0 U( G6 H0 k8 N' Mn=1,就一号,跑不掉的
    ' J! u  H( t$ }" Rn=2, 要站 (k+1) 模 n 那一号设a(2),比如 k=2, 则 a2=1 (号); 若 k=3, 则 a2=2
    / c# S, a3 F5 h8 U/ S; |5 d如此类推,n=i 时,要站在 a(i-1)+k 模 n 那一号。比如,k=6, n=19 时 要站在14号。' j5 B$ f! k2 L. n0 x+ n( W$ R
    2 j+ {: F1 N: p% n5 r) I

    $ G  ?. z; c+ y( {# M& k, L5 X. s我算到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 编辑
    5 j; b9 g* D5 O2 t4 R
    独角兽 发表于 2014-7-16 20:30 7 p% S8 k) l4 ]: [5 t
    1. 经过努力学习,这题我能用java编程做了,oh yeah!& I8 f. n7 ~- w; L4 f8 x& a: h3 }( i

    ( R/ {# ?" I# x8 N. ?2. 但叶子问我的不是编程。对于给定的k,我可以用 ...

    # p7 ?4 L8 I/ H6 b) F" n* g4 f
    ( y% u7 a8 \# }$ z* ?7 a7 t$ |3 i兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看# {+ _5 p0 t5 Y( X# P

    7 L- k8 I5 J4 p+ u在维基上看到K=2的解法和还有K≠2的通用解法,这里摘抄过来那段关于n的有趣分析。2 u  c' k, M1 t1 w  Y2 t0 V. ~
    1 M  w) t; z& R3 J4 m' f  [
    还有下面我抄了两个通用算法,那个java的是不是和你做的一样啊?6 F, m5 {# D: H2 H% N: [
      E3 G, [- O% }) Q7 j# R- t+ @
    -----------------------------不动脑筋的分割线--------------------------" y4 Y; p. x  g: G7 D
    8 |( r8 y) e& u# N% C6 h* i
    一个小心翼翼的Java例子:( L1 Z$ q2 j0 {+ {
    ) J) P! t' q- S, a5 C- {) ^7 r
    int josephus(int n, int k) {+ a8 C) Y4 z$ f& d% q7 u; X0 ]
            return josephus(n, k, 1);
    * m% H2 X+ n: Y- o  }& |9 \5 H# q+ L1 g+ F% D
      int josephus(int n, int k, int startingPoint) {- N5 I7 Z3 t- y  H
          if(n == 1)
    ' G- u& G' D! h. }          return 1;% o$ H( [4 ^: n5 J8 |! e" Z
          int newSp = (startingPoint + k - 2) % n + 1;& p0 _, g) v  k5 ^
      h( s/ f9 d/ }( U* a
          int survivor = josephus(n - 1, k, newSp);$ K$ X, h" `8 T, R0 E" X- k
          if (survivor < newSp) {+ B( `  F) Z0 X1 J
              return survivor;$ l! K# H3 [& M; g! Q. |
          } else1 q5 |3 K* v0 E) n7 v2 l5 W
              return survivor + 1;
    / ]. ?0 |% L  a  }) E/ G: W! }' k' c; x9 V% f
    8 o/ e0 c' o6 {& @4 t
    另外有个更简洁的例子
    : z- L4 I: {: y, _: B+ d# ^  def josephus(n, k):1 s2 Q: X) y' K' p
        if n ==1:0 J4 N( t6 G( t4 h
          return 1
    ! N# @  @# R5 g8 p+ Y- G& p0 g    else:
    8 k& |- y# B, _/ _" x' t/ q      return ((josephus(n-1,k)+k-1) % n)+1
    : ?4 g. r" a) h- b5 X% ]$ a+ Q
    3 c0 Y0 M" {; _; v" c1 Z( G8 }(如果n这个数字很大很大,k很小很小,电脑会不会转晕过去呢?)
    : X4 p2 R& d5 k8 t' `9 ~' ?* f" z4 A. t; f0 x
    以上摘自 http://en.wikipedia.org/wiki/Josephus_problem#Solution
    . j8 J  k  A. K% V
    + b6 N) [4 {0 \  W8 {4 w
    + E. S& e0 s# g8 w( J* E/ b& Z关于n的分析:& t. P* D5 C# y
    设f(n)为一开始有n个人时,生还者的位置。
    : U" ?  m: y  I& S如果一开始有偶数个人,则第二圈时位置为x的人一开始在第2x - 1个位置。因此位置为f(2n)的人开始时的位置为2f(n) - 1。这便给出了以下的递推公式:
    & B. O, Q3 W5 V% X" n: `1 u1 T" N- W$ U' g; D; U
    f(2n)=2f(n)-1
      f/ y; K6 ?9 q+ M. N) }如果一开始有奇数个人,则走了一圈以后,最终是号码为1的人被杀。于是同样地,再走第二圈时,新的第二、第四、……个人被杀,等等。在这种情况下,位置为x的人原先位置为2x+1。这便给出了以下的递推公式:' Y3 ]4 X3 {9 _5 m, n% J
    7 D/ b9 H. y% q
    f(2n+1)=2f(n)+12 h2 F: M1 ?: Z- ~4 q

    ! p) K5 @( [3 V$ M$ x+ A7 v) o0 K* @
    如果我们把n和f(n)的值列成表,我们可以看出一个规律:
    ! q8 l) ?, Z3 _+ ~; s
    - s! ?' l8 ~& \0 M( ~' jn    1    2        3        4        5        6        7        8        9        10        11        12        13        14        15    16
    % p. q# N- K7 s3 n2 l( E, s8 kf(n) 1    1        3        1        3        5        7        1        3        5        7        9        11        13        15        1
    ( @5 I2 a6 e! b) q9 M3 K; }3 X$ ?" C0 Z+ a3 z5 w% w3 C
    从中可以看出,f(n)是一个递增的奇数数列,每当n是2的幂时,便重新从f(n)=1开始。因此,如果我们选择m和l,使得n=2^m+l且0≤ l<2^m,那么f(n)=2 . l+1。显然,表格中的值满足这个方程。可以用数学归纳法给出一个证明。" {: i; m  G. ]: f, B9 b* r

    ( Q2 D' t: M) S定理:如果n=2^m+l且0≤ l<2^m,则f(n) = 2.l+1。; [: k( \: |6 i0 B) a
    4 y  H& D5 n! @' g. J
    $ e  y  `5 Y$ F5 O+ }" p
    答案的最漂亮的形式,与n的二进制表示有关:把n的第一位移动到最后,便得到f(n)。这可以通过把n表示为2^m+l来证明。

    该用户从未签到

    7#
    发表于 2014-7-17 11:19:06 | 只看该作者
    到处停留的叶子 发表于 2014-7-17 11:02 9 t# I) y( {7 ~; b1 ?4 u
    兽兽真是爱动脑筋啊~~我现在遇到这类问题第一想到的是打电话找高手解答,或者先在网上找找看) Z4 M& r1 `0 C& r; K$ S/ i
    1 `! j& j& e8 b8 C4 k
    在 ...

    - D% X" s" j; D. d7 j5 D( _我的推法就是这个:: `8 T, A% G9 h/ a# ]& K

    6 K4 j8 V& n- v4 {. F& X0 {  return ((josephus(n-1,k)+k-1) % n)+1! y( a% r4 S3 y
    & g# }5 b. ^- l, {9 U7 v: o
    我有一点疏忽是如果整除,模的结果是0,但实际应该取n。所以这个表达式把 "+1"搞到括号外面就完全对了。
    9 d1 c7 n# t, w! m/ a; B1 Y; ]( a
    ! J& n# q* n  ^$ W. K2的情况我没单拿出来搞。
  • TA的每日心情
    慵懒
    2020-5-10 00:00
  • 签到天数: 1237 天

    [LV.10]大乘

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

    [LV.Master]无

    9#
    发表于 2014-7-18 22:40:37 | 只看该作者
    看不懂
    7 r- O8 i6 Z. ^5 R' v- r4 ^不过今天不幸运数是17
  • TA的每日心情
    擦汗
    2020-3-23 00:29
  • 签到天数: 134 天

    [LV.7]分神

    10#
     楼主| 发表于 2014-7-19 03:04:00 | 只看该作者
    常挨揍 发表于 2014-7-18 09:40
    7 X1 h5 ~6 S2 U% H9 A2 b5 Y$ T& F看不懂/ G( @0 g; t5 R, Y
    不过今天不幸运数是17

    : S6 N% }9 X: u% Z, Y. i+ c) t7月17日成了一个黑色的日子。很让人感觉生命无常。7 |4 x: Q" Y; U4 @9 a2 _

    ) N: S/ s$ R% b* y+ A5 \以后出行挑日子,要找一个幸运数的交集,这里前面的9个数字也可以参考一下:1,3,7,9,13,15,21,25,31
    : s% T; h9 e! z) M6 U. e( _9 O
    7 |. D4 V; h% h' h2 \% |& [; }2 n13号如果遇上星期五,还是算了,不要不信邪。

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

    GMT+8, 2026-2-8 14:01 , Processed in 0.102203 second(s), 22 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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