You may also like

problem icon

Whole Number Dynamics I

The first of five articles concentrating on whole number dynamics, ideas of general dynamical systems are introduced and seen in concrete cases.

problem icon

Whole Number Dynamics II

This article extends the discussions in "Whole number dynamics I". Continuing the proof that, for all starting points, the Happy Number sequence goes into a loop or homes in on a fixed point.

problem icon

Whole Number Dynamics III

In this third of five articles we prove that whatever whole number we start with for the Happy Number sequence we will always end up with some set of numbers being repeated over and over again.

Number Chains

Stage: 5 Challenge Level: Challenge Level:1

Thank you to Chris for this solution. Chris has just left school and is about to start his course at Oxford University this month. Balakhrishnan also found the cycles but did not give proofs.

Recursive functions like this can be represented graphically by considering the line $y=x$ and all the points of $f(x)$ as in the graph below:
graph f(x)=2a+3b for x=10a+b
(1) Take your first point from $f(x)$.

(2) Draw a line horizontally to meet the line $y=x$.

(3) Draw a line vertically to meet a point on the line $f(x)$. There will never be more than one point with the same $x$ value as $f(x)$ because $f(x)$ has a unique value.

(4) Repeat steps two and three.

If we take a look at the graphs of $y=x$ and $y=f(x)$ we can see that only a few points of $f(x)$ lie above the line $y=x$. For these points alone $f(x)> x$ as for all other points step 2 will draw a line to the left i.e decreasing in value.

We can see the same thing analytically. The terms increase if and only if $2a + 3b > 10a + b$, that is iff $b > 4a$. As $b$ is a single digit number the only terms that are followed by larger terms are 1, 2, 3, 4, 5, 6, 7, 8, 9, 15, 16, 17, 18, 19 and 29 as seen on the graph.

Large terms reduce by one fifth in order of magnitude, and once the sequence reaches 2 digit numbers the largest value is given by $a=b=9$ which maps to 45. For numbers less than 45 $2a+3b < 33$. As there are a finite number of values the sequence can take, values are repeated and cycles occur.

There are three points that lie on the line $y=x$. These are 0, 14 and 28 for which values $x=f(x)$. Alternatively, we see that for a fixed point $10a + b = 2a + 3b$ so $4a=b$. Hence the only fixed points are 0, 14 and 28.

There are eight distinct loops (five 6-cycles, one 2-cycle and three fixed points) which are:
[0, 0]
[2, 6, 18, 26, 22, 10, 2]
[4, 12, 8, 24, 16, 20, 4]
[5, 15,17, 23, 13, 11, 5]
[7, 21, 7]
[9, 27, 25, 19, 29, 31, 9]
[14, 14]
[28, 28]

Other terms which are not in the cycles but lead into the cycles are:
1,3, $\to$ 9 etc.
30 $\to$ 6 etc.
32 $\to$ 12 etc.
33 $\to$ 15 etc.

We have proved that all higher numbers reduce to 33 or less so sequence with all other starting points enter one of the listed cycles or end up at a fixed point.

Why are all sequences all odd or all even?
even= 0 (mod 2)
odd=1 (mod 2)

When deciding if a number is odd or even we only need to look at the last digit, in this question defined as '$b$'. The only operation on $b$ is $b\to 3b$ and $3\times 0 \equiv 0{\rm mod}\ 2$ so it is even and $3\times 1 =3 \equiv1 {\rm mod}\ 2$ so it is odd. Therefore $f(x) \equiv x {\rm mod}\ 2$.

The sequences are all odd or all even because $$2a + 3b \equiv 10a + b \quad {\rm mod}\ 2.$$