4 ms·
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 tha
by jwilk 9y ago
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.
- mannykannot 9y agoGood 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.
- resource0x 9y ago> 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).
- Someone 9y agoBecause 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?