Problem of the week, 137

A former colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his US Naval Academy students, giving a prize of a cookie if they could solve it. One of them is given below.

Chain addition is a technique employed in cryptography for extending a short sequence of digits, called the seed to a longer sequence of pseudorandom digits. Quoting David Kahn (in Kahn on Codes, MacMillan, New York, 1983, p. 154), “the first two digits of the [seed] are added together modulo 10 [which means they are added and the carry is neglected] and the result placed at the end of the [sequence], then the second and third digits are added and the sum placed at the end, and so forth, using also the newly generated digits when the [seed] is exhausted, until the desired length is obtained”. Thus, the seed 3964 yields the sequence 3964250675632195… .

Periodic pattern

Periodic pattern

a. Show that this sequence eventually repeats itself.
b. Show that the sequence begins repeating itself with “3964”.
c. EXTRA CREDIT: How many digits are there before the first repetition of “3964”?

One thought on “Problem of the week, 137

  1. Dear Prof. Joyner, I found your interesting blog and this problem caught my the attention, mainly because of its numeration, 137, which is commonly associated, in physics, to the “fine-structure constant”, so I tried to solve it. After some thoughts I realize that the answers for the first two items are actually easy. Let us first consider a simpler case, which we may call the “Modular Fibonacci sequence”. This is almost the same as the problem above, except that the sequence begins with just two numbers, say, a b. Then, the sequence generated would be as: a b x_1 x_2 x_3 … Notice that the digit x_n is generated only by x_{n-1} and x_{n-2}. The sequence will be periodic if some pair of adjacent digits, say [x_{n-1} , x_n] equals another previous pair of adjacente digits. However, there is only 100 possible pairs (from 00 to 99), hence, if the sequence is greater than 100 digits, necessarily some pair will be the same as another previous one, and consequently the sequence will be periodic. To show that the sequence begins to repeat from the first numbers a b, we should realize that, if [x_{n-1},x_n] is a repeated pair, the same will be true for [x_{n-2},x_{n-1}] (due to recursive way on which the sequence is generated) and this will continue until we arrive to the first numbers [a,b]. For the case indeed discussed on the problem, the same argument works, but now we need to consider four adjacent digits, since the sequence begins with a b c d. Hence, a sequence with more than 10^4 terms will be necessarily periodic, and the first digits to be repeated will be the first numbers a b c d. The last item, however, seems to be more intricate. Ricardo S. Vieira.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s