Trying to define a way to generate the terms of a sequence, and starting with the number 5, I found, surprisingly, that the way I used generated this sequence:
5, 8, 11, 5, 8, 11, 5, 8, 11, ...
And these 3 numbers repeat in this order indefinitely.
Define a simple way to generate this sequence.
The official solution is to square the number, add up the digits in the square and add 1 to that sum to get the next term in the sequence.
The conjecture is that regardless of the starting value, you'll always get to the 3-value sequence shown.
The following program verifies the sequence is entered (specifically the value 5 is reached at some point) for all starting numbers up to 1,000,000:
10 for I=1 to 1000000
20 V=I
30 while V<>5
40 V=cutspc(str(V*V))
45 T=0
50 for J=1 to len(V)
60 T=T+val(mid(V,J,1))
70 next
80 V=T+1
90 wend
95 if I@100=0 then print I
100 next I
as the program does terminate.
For any n-digit number, the square will have at most 2n digits, which can total no more than 18n. The number of digits in that value will not exceed ceil(log(18n)) where common logs are used.
So for a 6-digit number, the next value will have at most ceil(log(18*6)) = 3 digits.
table:
n-digit number results in at most m-digit number
n m
1 2
2 2
3 2
4 2
5 2
6 3
7 3
8 3
9 3
10 3
11 3
12 3
13 3
14 3
15 3
16 3
17 3
18 3
19 3
20 3
so eventually we get down to a 2-digit number, but just to be safe we've already verified up to 1,000,000, so the conjecture is proved.
|
|
Posted by Charlie
on 2009-03-11 10:55:45 |
to the question posed in the official solution (spoiler)
