Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Sketch of a proof:

Let f(n) be the sum the squares of digits of n.

For k-digit number: f(n) ≤ 81k.

That is: f(n) ≤ 81 × (1 + ⌊log₁₀n⌋)

It's pretty clear that if n≥1000, f(n) < n. So the n, f(n), f(f(n)), ... sequence will eventually reach a number below 1000.

Mechanical proof for numbers below 1000 is in the article.



Because f(n) = log(n) eventually grows arbitrarily slower then f(n) = n, no matter what the base of that logarithm is, you can generalize that to arbitrary number base b > 2 and arbitrary powers p > 2, and show that any starting number will eventually reach a cycle.

Now, one can ask question such as:

- for which (number base, power) pairs is that cycle unique?

- for which (number base, power) pairs is that cycle shortest? (For example, 153 = 1³ + 5³ + 3³, so if (base 10, power 3) has only one such cycle, it has length 1. Similarly, 4150 = 4^⁵ + 1^⁵ + 5^⁵ + 0^⁵ could be the unique cycle of length 1 for base 10, power 5.

- what does the function f(base, power) look like?


> if n≥1000, f(n) < n

And this is what makes the setup not very interesting. Compare with 3x+1 problem, where the sequence can grow, but eventually comes down (there's a simple probabilistic argument for that, but no formal proof).


Good point. The first response to the original article mentions 162 (2 * 81) as a value that the process will always eventually fall below, presumably arrived at by this argument.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: