The Nonlinear Classroom

So, where is the mystery number 3 mentioned in the post title? Viewed through the proper lens the ones’ sequence collapses in on itself and leaves us just a 3. What lens is that now?

Modular Arithmetic

Before we can unravel the mystery of the 3, we need to go one number higher and say something about the number 4. Fours have mysteries of their own you know:

For example, 7 squared is 49, which upon division by 4 gives a remainder of 1. If you’ve never seen this before, it’s worth pausing to bang out a bit of algebra to convince yourself that it is true (and work out the analogous statement for the even squares).

Now, since every number in the sequence of ones is odd, we can prove that none of them are squares by showing that upon division by 4 none has a remainder of 1.

Check out the remainders for the first few elements in the sequence: \begin{aligned} 11 &= 4 \cdot 2 + 3 \\ 111 &= 4 \cdot 27 + 3 \\ 1111 &= 4 \cdot 277 + 3\end{aligned} So, we can be sure that 11, 111, and 1111 are not squares, since each gives a remainder of 3.

But… do those 3’s make a pattern? Viewed through the lens of arithmetic modulo 4, it is indeed the case that every number in the sequence of ones has a remainder of 3, and therefore no element in the ones’ sequence is a perfect square.

I’ll prove this below:

This Problem is about Fixed Points?!

The ones’ sequence is generated by the update function f(n) = 10 \cdot n + 1 . This is the rule that tells how to get from any number in the sequence to the next, and it’s a simple rule:

For example, to get from 11 to 111, we compute f(11) = 10 \cdot 11 + 1 = 111 .

Now, to find the remainders of the elements in the ones’ sequence, consider the behavior of f with all arithmetic computed modulo 4: \begin{aligned}f(3) \text{ mod }4 &= 10 \cdot 3 + 1 \text{ mod 4 }\\ &= 31 \text{ mod }4 \\ &= 3 \end{aligned}

Taken modulo 4, if you plug 3 into f, you get a 3 back out. This is called a fixed point of the function. Said another way, when you plug any whole number into f that has a remainder 3, you get out a number that also has remainder 3.

But 11 has remainder 3, and repeatedly applying f traces out the entire ones’ sequence, so we can rest easy knowing that all numbers in the ones’ sequence have remainder 3. That’s the power of a fixed point!

---

*If you aren’t familiar with modular arithmetic, then you should learn asap. To say that a whole number is congruent to 3 mod 4 is just a fancy way of saying it has remainder 3 when divided by 4

This problem caught me off guard – I simply didn’t expect it to be about fixed points! But, I gained insight and had fun analyzing the dynamics of f , which also led to some good follow up questions.

The Dynamics of f

The sequence 7, 71, 711, 7111, \ldots doesn’t contain any squares. Nor does the sequence 23, 231, 2311, 23111, \ldots . Why is that?

By changing the input to the update function f , we find an entire family of related sequences – the two sequences above come from the starting points 7 and 23 respectively.

But, both 7 and 11 are congruent to 3 modulo 4, therefore so too are the rest of the numbers in the respective sequences.

What if we generate a sequence with f but start with a number not congruent to 3 modulo 4? Does the same property, that no elements are squares, hold true?

Here’s a flow diagram showing what the update function does to an input with arithmetic modulo 4^*

Notice that 3 is the only fixed point (the self-loop in the picture).

In other words, no matter what number we start with, we eventually get pushed into a loop of 3’s. For example, if we start at 0 and apply f, we first go to 1 and then to 3, where we remain for time immemorial.

Because we can’t apply f more than two times before hitting the black hole of 3’s, no square number can appear past the second position in any sequence generated by f, which gets me curious.

Help Solve this Diophantine Equation

Besides the pair: \left( 0, 01 \right) , can anyone out there find a square number which, upon appending a trailing 1 (applying f ), produces another square number?

By the dynamics of f , it’s clear that we will need to start with an even square (congruent to 0) which upon application of f gives an odd square (congruent to 1).

Here’s a square pair to get things started: 36, 361 are the squares 6^2, 19^2 .

How many more solutions are there? Do the solutions have a nice characterization? Hit the comments section to straighten me out!

---

*In fancier language: project onto the group \mathbb{Z}/4

Can You Find a Different Proof?

I’d love to see a proof of this problem that doesn’t use arithmetic mod 4.

The closest I could get was to show that none of the numbers 11, 1111, 111111, \ldots are squares (that is, the elements of the ones’ sequence with an even number of digits).

This is easy to see if you multiply the sequence by 9: 99, 999, 9999, \ldots In the new sequence, each element is 1 less than a power of 10. e.g. 99 = 10^2 – 1 .

Every even power of of 10 is a square, and one less than a square is never itself a square because the gaps between squares grows too quickly (aside from the pair 1 and 0 of course). Thus, nothing in the even digit 9’s sequence is square.

But because 9 is itself a square, the even digit ones’ sequence are also not squares because the product of two squares is always another square (and we’ve shown that the product is not a square).

Alas, I haven’t found a way to get the odd digit elements of the ones’ sequence. Help!

---

I found this problem in this problems book by esteemed mathematician (and verified Martian) George Polya.