Skip to content

Problem 5: Hailstone (100pts)

Problem

Douglas Hofstadter's Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle.

  1. Pick a positive integer \(x\) as the start.
  2. If \(x\) is even, divide it by 2.
  3. If \(x\) is odd, multiply it by 3 and add 1.
  4. Continue this process until \(x\) is 1.

The number \(x\) will travel up and down but eventually end at 1 (at least for all numbers that have ever been tried -- nobody has ever proved that the sequence will terminate). Analogously, a hailstone travels up and down in the atmosphere before eventually landing on earth.

Breaking News (or at least the closest thing to that in math). There has been a recent development in the hailstone conjecture that shows that almost all numbers will eventually get to 1 if you repeat this process. This isn't a complete proof but a major breakthrough.

Breaking News (or at least the closest thing to that in math). There has been a recent development in the hailstone conjecture that shows that almost all numbers will eventually get to 1 if you repeat this process. This isn't a complete proof but a major breakthrough.

Hailstone sequences can get quite long! Try 27. What's the longest you can find?

道格拉斯·霍夫斯塔特（Douglas Hofstadter）荣获普利策奖的著作《哥德尔、埃舍尔、巴赫》（Gödel, Escher, Bach）提出了以下数学谜题。

  1. 选择一个正整数 \(x\) 作为起点。
  2. 如果 \(x\) 是偶数，则将其除以 2。
  3. 如果 \(x\) 是奇数，则将其乘以 3 并加 1。
  4. 重复此过程直到 \(x\) 等于 1。

数字 \(x\) 会上下波动，但最终会以 1 结束（至少对于所有已尝试过的数字来说是如此——没有人证明过这个序列一定会终止）。类似地，冰雹在最终落到地面之前，会在大气层中上下运动。

劲爆消息！（或者至少是数学领域最劲爆的消息）。关于冰雹序列猜想（Hailstone Conjecture）最近有了新的进展，表明如果你重复这个过程，几乎所有数字最终都会达到 1。这并非一个完整的证明，但却是一个重大的突破。

冰雹序列可能会相当长！试试 27。您能找到的最长序列是多长？

def hailstone(x):
    """Print the hailstone sequence starting at x and return its
    length.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    "*** YOUR CODE HERE ***"

Hints

  • 你可能需要使用 while 循环。

  • 这个函数只有一个参数，可能不太适合用递归来做（但也不是不能做）

  • 注意如果你在运算中使用了单除号 /，那么结果会变成浮点数！不管能不能整除！

Solutions