*Who am I? Index of Blogs*

*I recently came across a paper by Paul Yiu entitled 'Iterations of Sum of Powers of Digits'. I thought that it was a delightful play on numbers and after trying it out on my 13 years old grand-daughter, I decided that everybody can enjoy the quaint results (presented in a formal way in the paper).*

I shall attempt to present the discussion in a more layman friendly jargon - enjoy!

See also the article in Wiki on Happy Numbers.

**We shall try powers of 2 first - the idea is as follows:**

__Starter:____Choose a number N,__

__Sum the square of digits in the number N to obtain S1__

__Sum the square of digits in S1 to obtain S2__

__Continue doing this ...__

__What do you get ??__

Best to check it out - Let N = 239

Then S1 = 2^2 + 3^2 + 9^2 = 4 + 9 + 81 = 94

S2 = 9^2 + 4^2 = 81 + 16 = 97

S3 = 9^2 + 7^2 = 81 + 49 = 130

S4 = 1^2 + 3^2 + 0^2 = 1 + 9 +0 = 10

S5 = 1^2 + 0^2 = 1

Any further iterations will leave the sum at 1.

*Digit one is a fixed Point.*

If we start with any of following numbers, then we shall obtain the fixed point equal to 1.

*1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 97, 91, 100*

*These are also known as Happy Numbers.*

The happiness of a number is unaffected by rearranging the digits, and by inserting or removing any number of zeros in the number.

Numbers in red are prime numbers and are called Happy Primes.

*What about the remaining numbers - the so-called*

*sad numbers*.

Nothing better than trying it out. Let us choose N = 83

Then S1 = 8^2 + 3^2 = 64 + 9 = 73

S2 = 7^2 + 3^2 = 49 + 9 = 58

Likewise... S3 = 89, S4 = 145, S5 = 42, S6 = 20,

S7 = 4, S8 = 16, S9 = 37 and S10 = 58

**Notice that S10 = 58 = S2.**

*This simply means that further iterations will repeat the sequence from S2 to S10 - indefinitely. Sad numbers are trapped in a cycle - let us call it a limit cycle.*

**For the sum of squares of the digits in a number,**

**the limit cycle is****58, 89, 145, 42, 20, 4, 16, 37, 58.**

Where one enters the limit cycle depends on the starting number

*(Click on the slide to view full page image, press Escape to return to text)*

**The fixed point 1 and the limit cycle are the only final outcomes of iterations of sum of squares of digits in any number!**

**There are five fixed points and four limit cycles in this case. 85.5% end up in fixed points and only 14.5% end in limit cycles. They are best shown in the following slide:**

__Sum of Cubes:__

__An examples__: Let us start with N = 275

Then S1 = 2^3 + 7^3 + 5^3 = 8 + 343 + 125 = 476

S2 = 64 + 343 + 216 =623

S3 = 216 + 8 + 27 = 351

S4 = 27 + 125 + 1 = 153

S5 = 1 + 125 + 27 = 153

__A Fixed Point__

__See also where a short computer program is also provided to calculate the fixed points and limit cycles.__

__Sum of Fourth Powers:__There are 4 fixed points and 2 limit cycles in this case. Vast majority of iterations ( ~ 79%) end up in a limit cycle with 7 nodes (shown in the slide below).

The fixed point 8208 occurs with overwhelming frequency (> 90%) relative to other fixed points.

__Why do Fixed Points and Limit Cycles Happen?__**I now wish to find out why we get fixed points and limit cycles.**

Let us consider the example of a number that is made of 5 digits and consider that we are iterating with sum of each digit raised to the power 3.

The maximum possible sum of the cubes of digits in a 5 digit number (for N = 99999) is 5 x 9^3 = 3645

The smallest 5 digit number is 10,000 which is larger than 3645.

An iteration reduces the magnitude of the number.

*This is true for any number that has 5 or more digits*.

For a number with 4 digits,

the maximum possible sum of cube of digits is 4 x 9^3 = 2916.

*Some 4-digit number (1,000 to 2915) are indeed less than 2916 and the value of a 4-digit number is not necessarily reduced after an iteration.*

Therefore, a sum of cubes iteration on an arbitrarily large number (of 5 or more digits) will always result in a smaller number (the final theoretical maximum value of the sum being 2916) but not for a number with four or fewer digits.

The sum of cubes is a finite set of numbers, from 1 to 2916, and an iteration will eventually reproduce a value that is already achieved in a previous iteration - a limit cycle is formed.

Fixed points are special cases of a limit cycle with just one element or node.

Likewise, for sum of squares,

the theoretical maximum value of the sum is 3 x 9^2 = 243

*It may be shown that for an n digit number N, if n > k + 1 where k is the power to which each digit is raised, N is always greater than the sum of kth power of digits. Fixed points and limit cycles will lie in the range from 1 to (k+1) x 9^k.*

__Sum of first Powers (Sum of digits)__: This is a special case and I have left its discussion to this last section.

Iterations of the sum of the digits in a number result in fixed points from 1 to 9.

*Fixed Points: 1, 2, 3, 4, 5, 6, 7, 8 and 9*

*Let us consider the case of a five digit number N =*

*abcde*

This is

*N = 10000 a + 1000 b + 100 c + 10 d + e*

*Sum of digits S1 is*

*S1 = a + b + c + d + e*

*N - S1 = 9999 a + 999 b + 99 c + 9 d*

*We notice that N - S1 is completely divisible by 9.*

Essentially, the first iteration on N has reduced its value by an amount that is a multiple of 9.

Depending on the initial number of digits in N, S1 will have a much smaller number of digits let us say that

*S1 = fgh or S1 = 100 f + 10 g + h*

*The next iteration will reduce S1 by a multiple of 9 and will, in general, leave a fixed point remainder.*

*Summing digits may be used to find the remainder (in the range from 1 to 8) when the number is divided by 9.*

A remainder equal to 9 means that the original number is divisible by 9

*Example:*Consider a number N = 659824753

*Sum of digits S1 = 49*

*Next iteration S2 = 13*

*Next iteration S3 = 4*

*If N is divided by 9 then the remainder will be 4*

*http://ektalks.blogspot.co.uk/2017/10/blogger-profile-about-me-my-name-is.html*

## No comments:

Post a Comment