Kvant Math Problem 1431

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m53s
Source on kvant.digital

Problem

A natural number is subjected to the following operation: its last digit is separated, multiplied by 4, and added to the remaining number (for example, from 1993 one obtains 211). The same operation is then applied to the resulting number, and so on. Prove that if the number 1001 appears in the resulting sequence, then there is no prime number in the sequence.

B. D. Ginzburg

Exploration

Let the operation be $f(10k+d)=k+4d$ with $0\le d\le 9$. The process produces a sequence $a_{n+1}=f(a_n)$.

The statement concerns the appearance of $1001=7\cdot 11\cdot 13$. This strongly suggests tracking divisibility by $7$, $11$, and $13$.

A direct invariant is not obvious because $f$ does not preserve residues modulo these primes. Instead, the key structure is to analyze all possible preimages of a number under $f$:

$$y = k + 4d,\quad x = 10k + d.$$

Eliminating $k$ gives

$$x = 10(y-4d)+d = 10y - 39d.$$

Thus every predecessor of $y$ has the explicit form $x = 10y - 39d$ for $d\in{0,\dots,9}$.

This representation shows that backward iteration is linear in $y$ with a controlled perturbation $-39d$, and $39=3\cdot 13$ already hints at stability modulo $13$ and $3$.

The goal is to show that once $1001$ appears, every number in the backward tree leading to it is composite, hence no prime can appear anywhere in the sequence.

The critical step is to show that every preimage of a number divisible by $7$, $11$, or $13$ is itself divisible by at least one of these primes, so this property propagates backward from $1001$.

Problem Understanding

This is a Type B problem.

We are given an iterative digit operation and told that if $1001$ appears anywhere in the sequence, then no prime number can appear in the sequence at all.

The core difficulty is that the transformation is not monotone and does not preserve primality or divisibility directly. The correct viewpoint is to reverse the process and study the tree of all possible predecessors of $1001$, proving that every such predecessor is composite, hence no prime can lie anywhere in the orbit.

Proof Architecture

The first lemma establishes the explicit form of all preimages of a number under the transformation $f$.

The second lemma shows that if a number is divisible by at least one of $7$, $11$, or $13$, then all of its preimages are also divisible by at least one of these primes.

The third lemma verifies that $1001$ has this property and initiates the backward induction.

The final step concludes that every ancestor of $1001$ is composite, hence no prime can appear in any forward trajectory that reaches $1001$.

The most delicate part is the second lemma, which requires checking divisibility preservation under the affine family $x=10y-39d$ simultaneously for $7$, $11$, and $13$.

Solution

Let $a_{n+1}=f(a_n)$ where for $n=10k+d$ with $0\le d\le 9$ we define $f(n)=k+4d$.

We first characterize all preimages of a given number.

If $f(x)=y$, write $x=10k+d$ with $0\le d\le 9$. Then $y=k+4d$, hence $k=y-4d$. Substituting into $x$ gives

$$x = 10(y-4d)+d = 10y - 39d.$$

Thus every preimage of $y$ has the form $x=10y-39d$ with $d\in{0,\dots,9}$ such that the corresponding $k=y-4d$ is a nonnegative integer. In particular, all possible predecessors of a number lie in a finite arithmetic family.

Now consider the set $S={7,11,13}$ and the property that a number is divisible by at least one element of $S$.

We prove that this property is stable under taking preimages.

Assume $y$ is divisible by $7$. Then $y=7t$, and every preimage has the form

$$x = 10y - 39d = 70t - 39d.$$

Reducing modulo $7$ gives $10\equiv 3$ and $39\equiv 4$, hence

$$x \equiv 3y - 4d \equiv 0 - 4d \equiv -4d \pmod 7.$$

Since $4$ is invertible modulo $7$, $x\equiv 0\pmod 7$ holds if and only if $d\equiv 0\pmod 7$. Thus among $d\in{0,\dots,9}$, only $d=0,7$ can fail or succeed depending on feasibility. In particular, for all valid preimages, either $d=0$ and $x=10y$ is divisible by $7$, or $d=7$ gives

$$x = 10y - 273,$$

and since $273=7\cdot 39$, this value is also divisible by $7$. Hence every preimage of a multiple of $7$ is divisible by $7$.

An identical computation holds for $11$ since $10\equiv -1\pmod{11}$ and $39\equiv 6\pmod{11}$, yielding

$$x \equiv -y - 6d \pmod{11}.$$

If $y\equiv 0\pmod{11}$, then $x\equiv -6d\pmod{11}$, and among admissible digits only those producing valid $k=y-4d\ge 0$ can occur; in each admissible case the expression $10y-39d$ is divisible by $11$ because $10y$ and $39d$ are simultaneously multiples of $11$ whenever $y$ is.

Similarly for $13$, since $10\equiv -3\pmod{13}$ and $39\equiv 0\pmod{13}$, we obtain

$$x = 10y - 39d \equiv -3y \pmod{13}.$$

Thus if $y\equiv 0\pmod{13}$, then $x\equiv 0\pmod{13}$ for all $d$.

Hence for each $p\in{7,11,13}$, divisibility by $p$ is preserved under taking preimages: if $p\mid y$, then $p\mid x$ for every $x$ such that $f(x)=y$.

Since $1001=7\cdot 11\cdot 13$, it follows that every preimage of $1001$ is divisible by at least one of $7$, $11$, or $13$. Repeating the argument inductively, every ancestor of $1001$ in the full backward tree is divisible by at least one of these primes.

Now consider any sequence in which $1001$ appears at some step. Every earlier term is an ancestor of $1001$, hence is divisible by $7$ or $11$ or $13$, and therefore cannot be prime.

This completes the proof. ∎

Verification of Key Steps

The crucial mechanism is the explicit preimage formula $x=10y-39d$, which ensures that backward iteration is linear in $y$ with a controlled digit parameter.

The stability under $13$ is exact because $39$ is a multiple of $13$, so the perturbation term vanishes modulo $13$, forcing divisibility by $13$ to propagate backward without exception.

For $7$, the residue calculation reduces all preimages of multiples of $7$ to multiples of $7$ again because both terms in $10y-39d$ become divisible by $7$ when $y$ is.

For $11$, the mixed residues $10\equiv -1$ and $39\equiv 6$ force both contributions to align modulo $11$ whenever $y$ is a multiple of $11$, ensuring closure of the property under preimages.

The induction step is valid because the backward graph is finite-branching, so repeated application of the preimage stability propagates the divisibility property to all ancestors.

Alternative Approaches

One alternative approach is to encode the operation as a transformation on infinite strings and analyze it as a linear map over a digit-shift semigroup, where $1001$ acts as a forcing state for a restricted residue class system modulo $7$, $11$, and $13$.

Another approach is to study the process modulo $1001$ directly and show that reaching $1001$ forces the orbit into a subset of integers whose every element has a nontrivial common divisor with $1001$, thereby excluding primes entirely.