Reply to thread

Message: [QUOTE="Jacob Fugal, post: 4525300"] The period cannot be any larger than 1000. The largest period is probably quite a bit smaller than this, but this is a upper bound. Why? Some definitions, first. Let's define g(x) as the function that takes a number to it's successor. For example, g(42) = 4^2 + 2^2 = 20. For a variable x, we will denote the result of applying our function as x'. That is, x' = g(x). Let Mi = 10^i - 1 for all i. For example, M4 = 9999. Each Mi is the number made up of i nines. Mi' is then 81 * i. Let Qi = { x | M(i-1) < x <= Mi }. For example, Q4 is the range of integers from 1000 to 9999. It's easy to see that the union of all Qi's cover the natural numbers and that they are all disjoint. So the set of all Qi's is a partitioning of the natural numbers. For each x in Qi, it is easy to see that x' <= Mi'. Now, take any i >= 4. For all x in Qi, x' <= Mi' = 81 * i. But 81 * i < 10^(i-1) (see below), so 81 * i <= M(i-1), and x' <= M(i-1) for all x in Qi. But since x > M(i-1) by our choice, we know that x' < x. This is true for *all* x > 999. So, for those of you glossing over the math, the conclusion is that applying the "happy function" to any number greater than or equal to 1000 will necessarily result in a smaller number. Since the sequence can't loop if we're constantly decreasing (until we get down to 999 or less), none of the numbers in a period can be greater than 999 -- there's no way to get back *up* to any of those numbers. So, for any loop resulting from a number, the space of numbers liable to be in that loop is no larger than 1000 number (0 through 999). So no loop can have a period greater than 1000. Jacob Fugal [/QUOTE]

Verification