Problem of the Month (February 2000)

For integer n, let f(n) be the concatenation of the sums of every pair of consecutive digits of n. For example, f(82671)=108138, since 8+2=10, 2+6=8, 6+7=13, and 7+1=8. If n is a single digit, define f(n)=0.

Question #1:

What is the range of f? That is, which integers n have a k so that f(k)=n?

Question #2:

What are the periodic points of the iteration of f? That is, if f¹(n)=f(n) and f^k+1(n)=f(f^k(n)), which integers n have a k so that f^k(n)=n?

Question #3:

Which integers n have a k so that f^k(n)=0? There is no largest such number, as 10ⁿ+1 shows. What is the largest such number consisting of 3 non-zero digits? What is the largest such number consisting of no zeroes?

Question #4:

What are the answers to these questions if we sum 3 or more consecutive digits?

Question #5:

What are the answers to these questions in other bases?

Question #6:

What else can you tell me about this function?

ANSWERS

Question #1:

Berend Jan van der Zwaag found that 110 is the smallest number not in the range of f. He says that the 3 digit numbers not in the range of f are those where the middle digit is at least as big as the sum of the other two.

Trevor Green claimed that:

Theorem: If Y is not in the range of f, and X does not end in 1, then XY is not in the range of f.

Theorem: If X is not in the range of f, and does not end in 1, then XY is not in the range of f.

and wondered whether:

Conjecture: If X is not in the range of f, then X has a substring of length 3 that is not in the range of f.

David Wilson noted that a finite state machine can be constructed which accepts the string representations of the elements in the range of f, or in the complement of the range of f, and that this still holds true in any base, and if any number of consecutive digits are added.

Question #2:

Joseph DeVincentis, Trevor Green, Brendan Owen, and Berend Jan van der Zwaag found the following periodic cycles:

99(a+1) → 181a → 99(a+1) [where 0≤a≤8]

3333(a+1) → 666(a+4) → 12121a → 3333(a+1) [where 0≤a≤5]

Philippe Fondanaiche found some of these. Berend Jan van der Zwaag found that 733 numbers end in the first cycle and 222 numbers end in the second cycle.

Trevor Green conjectured that these are the only periodic points in base 10. He also made the observation that every periodic cycle includes a number that starts with 1.

Question #3:

Joseph DeVincentis, Trevor Green, and Berend Jan van der Zwaag found that the smallest number that diverges to ∞ when f is iterated is 1496.

Joseph DeVincentis and Berend Jan van der Zwaag gave the largest number containing no zeroes that converges to 0 (831112), and Berend Jan van der Zwaag gave the largest number that does not contain 2 consecutive zeroes which conveges to 0 (8010120). Joseph DeVincentis gave a short proof that every number smaller than 991 converges to 0.

Trevor Green conjectured that there are only finitely many numbers in any base that go to 0 besides the numbers a0...0b, which he calls bodiless numbers. Berend Jan van der Zwaag confirmed this, and gave the complete list. Trevor Green gives the following list:

Largest Non-Bodiless Numbers Converging to Zero in Base b

base	2	3	4	5	6	7	8	9	10	11
n	10²+10	2×10⁵+10	3×10⁷+10	10¹⁰+10	2×10¹⁰+10	4×10¹²+10	7×10¹³+10	3×10¹⁵+10	9×10¹⁶+10	4×10¹⁸+10

Berend Jan van der Zwaag claims the largest number with 3 non-zero digits which converges to 0 is 11×10¹⁵+8.

Brendan Owen and Berend Jan van der Zwaag gave a list of the smallest n for which f^k(n)=0:

Smallest Numbers Requiring k Iterations to Reach Zero

k	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
n	0	1	10	19	109	149	197	399	694	796	893	897	1167	1579	1596	1667	1790	1777	2859	1779	1778	1873	3679	5926	11289	9539

k	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	>40
n	13551	4589	5960	12066	12265	19119	10927	12379	11742	65220	34038	40390	1110025	10100023	91000021	1000...0009

Question #4:

Joseph DeVincentis conjectured that if you add more than 2 consecutive digits, there will be no small periodic points.

Berend Jan van der Zwaag confirmed this for some small cases. When adding 3 consecutive digits, numbers smaller than 10889 converge to 0, 10889 converges to ∞, and the smallest periodic cycle is 125610 → 813127 → 125610. When adding 4 consecutive digits, numbers smaller than 1005952 converge to 0 except for the few fixed point mentioned below, 1005952 converges to ∞, and the smallest fixed points are 18181a. He also found some periodic points:

8888888(a+8) → 323232323(a+2) → 1010101010101a → 2222222222(a+2) → 8888888(a+8)

666666(a+4) → 2424242(a+2) → 121212121a → 666666(a+4).

Question #5:

Joseph DeVincentis and Trevor Green noted that if f^k(n) contains the digits n in order (this includes periodic points and also numbers like 1111111), then f^ck(n) will also, and therefore n doesn't converge to 0. Trevor Green called these numbers expansive.

He used this observation to completely analyze the binary case. He proved that 1000...0001, 1000...000, 11, 1, and 110 go to 0, 111, 1010, and 1100 end up in the 111 → 1010 → 111 loop, and every other number diverges!

Brendan Owen gave a list of periodic points in bases no more than 10. In every base b, there are (b–1) 2-cycles of the form (b–1)(b–1)c → 1(b–2)1(c–1) → (b–1)(b–1)c, where 1≤c≤b–1. These also appear to be the only 2-cycles. Here is the list of the other known periodic points in other small bases:

Other Periodic Points in Various Bases

Base	Larger Cycles
4	(2222,101010,11111), (2223,101011,11112)
5	(2331,10114,11210)
7	(4443,111110,22221), (4444,111111,22222), (4445,111112,22223), (4446,111113,22224)
8	(10101010,1111111,222222,44444), (10101011,1111112,222223,44445), (10101012,1111113,222224,44446), (10101013,1111114,222225,44447)
9	(6627,113810,412101,53311,8642,15116), (6628,13811,412102,53312,8643,15117)
10	(33331,6664,121210), (33332,6665,121211), (33333,6666,121212), (33334,6667,121213), (33335,6668,121214), (33336,6669,121215)

Trevor Green found that if a and n are given, the number consisting of 2n+1 digit a's has period n in base a(2ⁿ–1) + 1. He points out that base 16 has 3 of these cycles, base 64 has 4, and base 316 has 5. He asks whether all cycles which are not 2-cycles are of this form, but doubts the answer is yes.

Question #6:

Berend Jan van der Zwaag has found that apparently all numbers fall into 3 categories: those that have f^k(n)=0 for some k, those that have f^k(n)=n for some k, and those for which f^k(n) goes to ∞ and f^c+k(n) starts with the same digits as f^k(n) for some c and k. He conjectures that there are precisely 23 different expanding periodic loops, starting from the numbers 3871, 7777, 9911, 9921, 9922, 9931, 9933, 9941, 9951, 9955, 9961, 9971, 9977, 9981, 9988, 9999, 66642, 66651, 66661, 66666, 66678, 66681, and 66691.

In 2011, Lars Blomberg sent me this information about this problem.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 8/27/11.