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.
Starter: We shall try powers of 2 first - the idea is as follows:
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!
Sum of Cubes: 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:
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