gmf@uvacs.UUCP (05/10/84)
In the magazine * Abacus * for Winter, 1984 (v. 1, no. 2, Springer-Verlag)
there is the following problem on p. 73 (attributed to Dr. Herta Freitag
(Hollins College, retired):
Let N(0) be an integer > 1. Define N(K+1) as the sum of the * digits *
of the divisors of N(K) [not the sum of the divisors!!] . Prove or
disprove that all such sequences end up with N(K+1) = 15, which then
repeats. Example with N(0) = 12:
K N(K) Divisors of N(K)
----------------------------------------
0 12 1 2 3 4 6 12
1 19 1 19
2 11 1 11
3 3 1 3
4 4 1 2 4
5 7 1 7
6 8 1 2 4 8
7 15 1 3 5 15
8 15 which repeats forever
I ran a couple of hundred on a machine and it worked every time (didn't
always arrive at 15 in the same way, but arrived). Does anyone know why
this is?
Gordon Fisherpizer@ecsvax.UUCP (07/22/84)
References: <uvacs.1297> I don't have a definite answer to the problem, I do however have some idea. The easiest way to take this problem is to look at different ranges of numbers and make general assumptions. First of all, any incredibly high number (ie above 1000) would have to decrease as the function progressed. Take the number 5000, for example, the biggest divisor is only 2500, and since you are adding up only the digits up to get the next number, you only have the number 7 so far. Even if a large number had a divisor like 592347, the sum of the digits (30) is nothing compared to the number itself. So we can assume, at least for large numbers, the number will decrease. Below 1000, the same holds true, all the way down to the number 15. There are a few exceptions where the number will increase (for example 16 becomes 22, 24 becomes 33), however the next number will decrease (22 will become 9, 33 will become 12), or if not the next number, the one after that. Below 15, the numbers will increase (except for 10, 11 and 13, which then go down but come back up again). At 15, which seems to be the only number that does this, it will reproduce itself. I didn't study this problem for an incredibly long period of time, so there may be errors in my reasoning, but I will be happy to accept remarks and criticism. Billy Pizer (pizer@ecsvax)
howard@metheus.UUCP (Howard A. Landman) (07/28/84)
Here is an outline of a proof which I am too lazy right now to complete.
(1) Prove that for some N, for all M > N, K(M) < M.
This establishes that the sequences for all sufficiently large
numbers will eventually enter (and STAY in) the set of numbers < N.
Thus we only need to consider sequences which start with < N.
(2) Any sequence which remains in a finite set must eventually repeat an
element. Because of the way this series is calculated, such a repeat
means that the series will then repeat a sequence or a single number
forever.
(3) Prove by exhaustive examination of the cases that there are no such
cycles other than 15. (If the statement is false, of course, it is
here that you will discover the counterexample.)
Howard A. Landman
ogcvax!metheus!howard