Problem of the Month (February 2000)

For integer n, let f(n) be the concatenation of the sums of every pair of consecuitve 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 f1(n)=f(n) and fk+1(n)=f(fk(n)), which integers n have a k so that fk(n)=n?

Question #3:

Which integers n have a k so that fk(n)=0? There is no largest such number, as 10n+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

base234567891011
n102+102*105+103*107+101010+102*1010+104*1012+10 7*1013+103*1015+109*1016+104*1018+10

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

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

Smallest Numbers Requiring k Iterations to Reach Zero

k01234567 891011121314151617 1819202122232425
n011019109149197399 694796893897116715791596166717901777 285917791778187336795926112899539

k2627 28293031323334353637 383940>40
n13551 45895960120661226519119109271237911742 652203403840390111002510100023910000211000...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 fk(n) contains the digits n in order (this includes periodic points and also numbers like 1111111), then fck(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

BaseLarger 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*(2n-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 fk(n)=0 for some k, those that have fk(n)=n for some k, and those for which fk(n) goes to ∞ and fc+k(n) starts with the same digits as fk(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.