| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Newsgroups: net.math
Path: decwrl!decvax!mcnc!ncsu!uvacs!gmf
Subject: Divisor-Sum Problem
Posted: Sat Jul 21 14:06:26 1984
From: gmf Thu May 10 14:58:25 1984
(uvacs.1297) net.math : Iterated sums of digits of divisors
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 Fisher
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 109.1 | HARE::STAN | Mon Jul 30 1984 00:25 | 23 | ||
Newsgroups: net.math
Path: decwrl!decvax!tektronix!ogcvax!metheus!howard
Subject: Re: Iterated sums of digits of divisors
Posted: Fri Jul 27 16:45:48 1984
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
| |||||
| 109.2 | TURTLE::GILBERT | Tue Jul 31 1984 13:27 | 70 | ||
Let f(x) = the number of prime factors of x f(x) <= log x, where p is the smallest prime factor of x p Let g(x) = the number of divisors of x (including 1 and itself) g(x) <= 2 ^ f(x) g(p^k * y) <= (k+1) * g(y), where p is a prime Let h(x) = the sum of the digits of the divisors of x h(x) <= g(x) * 9 * (1+log x) 10 Let n = 2^p * 3^q * r, where r is not divisible by 2 or 3. We want to choose M such that n >= M implies h(n) < n. We have: h(n) <= (p+1) * (q+1) * 2^log r * 9 * (1+log n) 5 10 2^log r = 2^log (n * 2^-p * 3^-q) 5 5 = n^(log 2) * (2^log 2)^-p * (2^log 3)^-q 5 5 5 (p+1) * (2^log 2)^-p < 1.66 5 (q+1) * (2^log 3)^-q < 1.25 5 h(n) < n^(log 2) * (1+log n) * 1.66 * 1.25 * 9 5 10 < n^(log 2) * (1+log n) * 18.68 5 10 We want to choose M so that n >= M implies: h() < n^(log 2) * (1+log n) * 18.68 < n 5 10 18.68 * (1+log n) < n^(1-log 2) 10 5 This is true if n >= 2268, so we take M = 2500. (a better analysis could reduce 18.68 by about a factor of 2, yielding M < 600, which would put the problem in the paper/pencil/pocket-calculator category). A computer program was used to check 1 <= n <= 2500. The following table summarizes all the cases with h(n) >= n. More values are given in the third column than are needed for a proof; they're FYI. n h(n) h(h(n)), h(h(h(n))), ... 1 1 1 2 3 4, 7, 8,15 3 4 7, 8,15 4 7 8,15 5 6 12,19,11, 3, 4, 7, 8,15 6 12 19,11, 3, 4, 7, 8,15 7 8 15 8 15 15 9 13 5, 6,12,19,11, 3, 4, 7, 8,15 12 19 11, 3, 4, 7, 8,15 14 15 15 15 15 15 16 22 9,13, 5, 6,12,19,11, 3, 4, 7, 8,15 18 30 27,22, 9,13, 5, 6,12,19,11, 3, 4, 7, 8,15 24 33 12,19,11, 3, 4, 7, 8,15 28 29 12,19,11, 3, 4, 7, 8,15 36 46 18,30,27,22, 9,13, 5, 6,12,19,11, 3, 4, 7, 8,15 48 52 26,16,22, 9,13, 5, 6,12,19,11, 3, 4, 7, 8,15 Thus, all numbers > 1 eventually get into the "15" cycle. - Gilbert | |||||