SietieBook

The Đx Problem

Introduction

Imagine yourself as I found myself some August afternoon in 2023. Having forged way ahead in the worksheet your Calc 2 class was working on that day, you had nothing left to do but twiddle your thumbs, wait for the class to catch up over the course of an hour and doodle. So you write down the letter "a" in the margins of your worksheet.

Imagine the alphabet as inscribed around a torus. It starts a, b, c, and so on until x, y, z, and back to a again. Picture now your "a" in place between the previous alphabet's "z" and the current one's "b."

Now bored out of any reason, you decide to form a pattern by writing the additive combination of each two adjacent letters bellow each pair. It's sort of like Pascal's triangle, in a way. Of course, you add letters together by adding their ordered placements in the alphabet together (a=1, b=2, z=26, etc). a+b=c, but what is a+z? There isn't a 27th letter in the alphabet, so count past all 26 letters in the alphabet and reach the first letter in the next alphabet, "a."

As you continue this pattern, you wonder when exactly each letter in the alphabet will have appeared at least once in this growing triangle of letters. You find this happens on the triangle's 14th row.

But why? Why should the 14th row be the first row of the triangle for which the whole triangle contains within it each letter in the alphabet? Why not the 13th or 15th? As you know intimately, every natural pattern and function in this world is made of math and can, in theory be described in math. So, how do we use math to describe what's going on in this instance?

Getting Our Bearings

First, you translate the letters of the triangle to a more easily parseable form.

Immediately, three things strike you. First off, the leftmost entry of any row is 1. This makes sense seeing that (1 + 26)mod26 = 1. Next off, the second entry of any row starts at 3 on row 2 and grows by 1 each row. This also makes sense, since n + 1 = (n+1). Lastly, you notice that for each row, the rightmost entry is precisely (2^x - 1)mod26 where x indicates the row. For example, the last entry of the 4th row is (2^4 - 1)mod26, or 15. This also makes sense as n + (n+1) = 2n + 1 = 2m - 1 where m = n + 1. Since the first such value of n is 1, the only entry of row 1, the first such value of m is 2. The next value of m will then be 2^2, then 2^3 and so on.

Imagine if you will, each row of the triangle as a set of length x, and the triangle as the union of all such sets from the first to the last row. Let's now call the last row x and each row in between the first (1) and the last (x) will be some xi. Now imagine some equation that gives the value of any entry on the triangle from its row xi and column yi alone. Let's call this function P(xi,yi) with the P standing for position.

Thus, the set of any row xi, which we'll write as đxi, can be described as the iterated union Uxiyi=1{P(xi,yi)}.

Then the whole triangle, which we'll write as Đx = Uxxi=1Uxiyi=1{P(xi,yi)}.

The precise function P(xi,yi) may be found by either of two ways: by taking a P(x,y) and following its parents up the triangle or by taking a P(x,y) and following its neighbors across their row. I'll demonstrate only the second way here as it is much quicker to demonstrate, though trying the first way leads to the more marvelous proof.

Finding P(xi,yi)

Allow me to draw your attention to the third row {1,4,7}. Notice that the difference between 1 and 4 and 4 and 7 is the same. Let's look at the fifth row {1,6,16,26,31}. 6-1=31-26 and 16-6=26-16. Let's write the differences between neighboring values in between said values.

Let's include the difference values of the edges of the triangle with those of their imagined neighbors, for grins.

To make things easier to read, I'll clear the actual triangle's values, leaving only the values of the differences between neighboring values.

Look familiar?

From this, we find that each successive P(xi,yi) = P(xi,yi-1) + Some value in Pascal's triangle. Some algebra later, we arrive at the definition
P(xi,yi) = Σyi-1n=0(xin).

By the way, if we solve for P(xi,yi) from the other direction we arrive at P(xi,yi) = (xi-1yi-1) + 2Σyi-1n=1(xi-1n-1) indicating that the two combinatorial functions are equal for { xi,yi ∈ ℕ+ , xi > yi }

Đx = Uxxi=1Uxiyi=1{Σyi-1n=0(xin)}

The Heart of the Matter

We know that the smallest x for which Uxxi=1Uxiyi=1{Σyi-1n=0(xin)mod 26} is equal to the complete residue system of 26 is x = 14. Can we find the minimum number of rows required to contain the complete residue system of any natural number a?
In other words, what is x for each a where Uxxi=1Uxiyi=1{Σyi-1n=0(xin)mod a} = A,
A > Ux-1xi=1Uxiyi=1{Σyi-1n=0(xin)}, where A is {0,1,2,...,a-1}?

A Discovery

Let's begin by tackling an easier question, for which values x for each a is
Uxxi=1Uxiyi=1{Σyi-1n=0(1)mod a} = A > Ux-1xi=1Uxiyi=1{Σyi-1n=0(1)mod a} true? Well, Σyi-1n=0(1)mod a = yi mod a. Since this P(xi,yi) does not depend on xi and is thus simply a P(yi), the outer union bears no effect on the resultant x for each a and we can simplify Uxxi=1Uxiyi=1{yi mod a} to just Uxyi=1{yi mod a}. In English, our function generates 1 new value each successive column or row, and this value is equal to the index of the column or row. It gives {1, 2, 3,..., yi mod a} which is equal to {0, 1, 2, 3,..., a-1} where yi = a. In other words, the function that describes the output x for each input a, for this definition of P(xi,yi), gives just a.

To put it more obviously, f(P(yi)) : a -> a.

Return to Main Page

Back to top