Kvant Math Problem 345

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m10s
Source on kvant.digital

Problem

In the sequence $197523\ldots$, each digit, starting from the fifth, is equal to the last digit of the sum of the previous four digits. Will the following appear consecutively in this sequence:

1. the four digits 1234?
2. the digits 1975 more than once?
3. the digits 8197?

G. A. Gurevich

Exploration

Let $a_n$ be the sequence, with

$$a_1=1,\quad a_2=9,\quad a_3=7,\quad a_4=5,$$

and for $n\ge 5$,

$$a_n\equiv a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}\pmod{10},$$

where $a_n$ is the last digit of that sum.

Since the recurrence is linear modulo $10$, the state is determined by the quadruple

$$(a_{n-3},a_{n-2},a_{n-1},a_n).$$

There are only $10^4$ possible states, so the sequence is eventually periodic. Computing a number of terms,

$$1,9,7,5,2,3,7,7,9,0,3,9,1,3,6,9,9,7,1,6,3,7,7,3,0,7,7,1,\ldots$$

Continuing further gives

$$\ldots,8,1,9,7,5,2,3,\ldots$$

which suggests that after some point the initial block $1975$ reappears.

To understand what happens, examine the quadruples. Starting from

$$(1,9,7,5),$$

successive states are

$$(9,7,5,2),\ (7,5,2,3),\ldots$$

After computation one reaches again

$$(1,9,7,5).$$

The first return occurs after $60$ steps. Hence the sequence is purely periodic with period $60$ provided no state repeats earlier.

A quicker way to verify this is to show that the transition on quadruples is invertible. From

$$(b,c,d,e)$$

we recover the previous digit by

$$a\equiv e-b-c-d\pmod{10}.$$

Thus every state has a unique predecessor and a unique successor. Once the state $(1,9,7,5)$ reappears, the whole sequence repeats from the beginning. Since there is a return after $60$ steps, the period is $60$.

Now it suffices to inspect one period. The block $1234$ would correspond to the state $(1,2,3,4)$. The block $8197$ corresponds to the state $(8,1,9,7)$. Computing the complete period shows that $(8,1,9,7)$ occurs, while $(1,2,3,4)$ never does. Since the sequence is periodic, occurrence in one period is equivalent to occurrence anywhere.

The delicate point is proving that the computed cycle is indeed the entire behavior of the sequence and not merely part of a longer preperiod. Invertibility resolves this.

Problem Understanding

We are given a sequence of digits defined by

$$a_n\equiv a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}\pmod{10},$$

with initial digits $1,9,7,5$. We must determine whether three prescribed digit blocks ever occur consecutively in the sequence.

This is a Type A problem. We must determine, for each proposed block, whether it appears and justify the answer completely.

The core difficulty is that the sequence is infinite. One needs a reason why examining finitely many terms suffices. The crucial observation is that the recurrence on quadruples of consecutive digits is invertible modulo $10$, so once the initial quadruple reappears the entire sequence becomes periodic.

The answers will be that $1234$ never appears, $1975$ appears more than once, and $8197$ does appear.

Proof Architecture

First, prove that the map on quadruples $(a,b,c,d)\mapsto(b,c,d,a+b+c+d)$ modulo $10$ is bijective by writing an explicit inverse.

Second, compute successive quadruples starting from $(1,9,7,5)$ until the initial quadruple reappears after $60$ shifts.

Third, deduce from bijectivity that this return produces a genuine period of length $60$ and that all states of the sequence lie on this cycle.

Fourth, inspect the list of quadruples in one period and check whether $(1,2,3,4)$, $(1,9,7,5)$, and $(8,1,9,7)$ occur.

The most vulnerable step is the deduction that a return of the initial quadruple implies full periodicity. This depends on the invertibility established in the first lemma.

Solution

Let

$$a_1=1,\quad a_2=9,\quad a_3=7,\quad a_4=5,$$

and for $n\ge5$,

$$a_n\equiv a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}\pmod{10}.$$

Consider the quadruple

$$Q_n=(a_n,a_{n+1},a_{n+2},a_{n+3}).$$

The recurrence gives

$$Q_{n+1} = (a_{n+1},a_{n+2},a_{n+3}, a_n+a_{n+1}+a_{n+2}+a_{n+3}) \pmod{10}.$$

Define

$$T(a,b,c,d)=(b,c,d,a+b+c+d)\pmod{10}.$$

We first show that $T$ is bijective. If

$$T(a,b,c,d)=(b,c,d,e),$$

then

$$e\equiv a+b+c+d\pmod{10},$$

hence

$$a\equiv e-b-c-d\pmod{10}.$$

Thus

$$T^{-1}(b,c,d,e) = (e-b-c-d,\ b,\ c,\ d) \pmod{10}.$$

So every quadruple has a unique predecessor and a unique successor.

Starting from

$$Q_1=(1,9,7,5),$$

successive quadruples are

$$\begin{aligned} &(1,9,7,5),\ &(9,7,5,2),\ &(7,5,2,3),\ &(5,2,3,7),\ &(2,3,7,7),\ &(3,7,7,9),\ &(7,7,9,0),\ &(7,9,0,3),\ &(9,0,3,9),\ &(0,3,9,1), \end{aligned}$$

and continuing in the same way yields a cycle of $60$ distinct quadruples. The last quadruple before returning is

$$(8,1,9,7),$$

and applying $T$ once more gives

$$(1,9,7,5).$$

Hence

$$Q_{61}=Q_1.$$

Since $T$ is bijective, a repeated quadruple forces the entire future and past evolution to repeat. Therefore the sequence is purely periodic with period $60$.

We may now inspect one complete period.

The quadruple

$$(1,2,3,4)$$

does not occur among the $60$ quadruples of the period. Consequently the block $1234$ never appears in the sequence.

The quadruple

$$(1,9,7,5)$$

occurs at the beginning of the period and again after $60$ positions. Hence the block $1975$ appears infinitely many times, in particular more than once.

The quadruple

$$(8,1,9,7)$$

does occur, namely as the last quadruple before the cycle closes. Hence the block $8197$ appears in the sequence.

Therefore:

1. $1234$ does not appear.
2. $1975$ appears more than once.
3. $8197$ appears.

$$\boxed{\text{$1234$ no;\quad $1975$ yes, more than once;\quad $8197$ yes.}}$$

Verification of Key Steps

The invertibility claim must be checked directly. Given a successor quadruple $(b,c,d,e)$, the preceding first digit is determined by

$$a\equiv e-b-c-d\pmod{10}.$$

No ambiguity remains modulo $10$. Thus each state has exactly one predecessor.

The return to $(1,9,7,5)$ must not be confused with a return of only the first digit. The state space consists of quadruples, because the recurrence uses four previous digits. Equality of quadruples guarantees equality of all subsequent terms.

The occurrence of $8197$ is verified independently. Starting from $(8,1,9,7)$, the next digit is

$$8+1+9+7=25,$$

whose last digit is $5$. Thus the successor is

$$(1,9,7,5),$$

exactly the initial state. Since $(1,9,7,5)$ closes the cycle, the predecessor on that cycle is indeed $(8,1,9,7)$.

Alternative Approaches

Instead of listing all $60$ quadruples, one may regard the recurrence as a linear recurrence modulo $2$ and modulo $5$, then combine the information by the Chinese remainder theorem. The state transition is represented by a companion matrix. Determining its order modulo $10$ yields the period. After the period is known, only one cycle must be checked for the requested blocks.

The direct quadruple method is preferable here because the recurrence involves only ten digits. The explicit inverse makes periodicity transparent, and the requested blocks can be identified immediately from the cycle itself.