Posts Tagged Puzzles

Divisible by 7, Both Ways

Author’s Update on 7/26/08: I submitted these numbers to the On-Line Encyclopedia of Integer Sequences. You can see a much longer list of the sums here.

I briefly wrote about this several years ago, but with my newfound powers of publishing LaTeX to the web, I feel that it can be made more accessible now.

Here’s the math problem, which sounds innocent enough:
Find the sum of all integers $i$ between 0 and $10^{6}$ (one million) such that both $i$ and the reverse of $i$ are divisible by 7. More generally, replace $10^{6}$ by $10^N$ and find an algorithm that works for any $N$.

Just to work up to this a bit, if those extra conditions did not exist, the problem would be easy. Ignoring 0, there are exactly $10^{6}$ integers between 1 and $10^{6}$, and they can be paired off into $\frac{10^{6}}{2}$ sets: $[1, 10^{6}], [2, 10^{6}-1],$ all the way up to the last set $[\frac{10^{6}}{2}-1,\frac{10^{6}}{2}]$. Each of these sets has the same sum: $10^{6}+1$. Therefore the sum of all the numbers is just $\frac{10^{6}}{2} \times (10^{6}+1) = 500,000,500,000$.

In addition, if the divisible-by-7 condition did exist, but not the condition on the reverse of $i$, it would also be relatively easy. The numbers to add would be the multiples of 7: $0, 7, 14, 21...$ up to $ ..., 999,999$. We can divide each of these numbers by 7, add them, then multiply the product by 7 at the end. That addition can be done the same way as in the above paragraph and we end up with $\frac{142857}{2} \times (142857 + 1) \times 7 = 71,428,928,571$.

It is the condition on $i$‘s reverse that makes this hard. Qualifying numbers start out 0, 7, 70, 77, 161, 168, 252, 259…, and end with …999838, 999922, 999929, 999992, 999999. There doesn’t seem to be anything obvious about the digits themselves, nor anything very regular about the spacing between the numbers (which was the key to the intermediate problem with only one condition).

However, we can solve this problem using Dynamic Programming with Modular Arithmetic. First, let’s look at the more general problem.

Breaking Down

Let $F(n, m, x, y)$ be the number of integers $i$ with $ n \le i < m$ and $i \equiv x$ (mod 7) and $Reverse(i) \equiv y$ (mod 7). Similarly, let $G(n, m, x, y)$ be the sum of those integers. $G(0, 10^N, 0, 0)$ is the answer to the our question, by definition, but first let’s look at $F(0, 10^N, 0, 0)$. It will turn out that we can use this to calculate $G(0, 10^N, 0, 0)$.

Observe that $F(0, 10^N, x, y)$ can be represented as the sum of 10 instances of $F$ over intervals of size $10^{N-1}$, one for each possible first digit (left padding with zeros to ensure N digits).


$\displaystyle F(0, 10^N, x, y) = \sum_{i=0}^9 F(10^{N-1}i, 10^{N-1}(i+1), x, y)$     (1)

As an example, what Equation (1) is saying is that


$\displaystyle F(0, 100, 0, 0) = F(0, 10, 0, 0) + F(10, 20, 0, 0) + ... + F(90, 100, 0, 0)$     (2)

This is because however many numbers there are between 0 and 100 with our divisibility properties, they are divided up among the ranges [0,9], [10,19], [20,29] up to [90,99]. If we count the numbers in those bins up separately and then add the totals for the bins, it will come at the same as if the numbers are counted up all at once.

We will characterize the numbers counted by each of the summands in Equation (2) in order to fold them together. The property we use to relate $F$ functions over different intervals comes from the digits of the numbers. Let $id_1d_2d_3 \dots d_N$ be an $N+1$-digit number, with first digit $i$. Then,


$\displaystyle id_1d_2d_3 \dots d_N$ $\textstyle =$ $\displaystyle i \times 10^{N} + d_1d_2d_3 \dots d_N$ (3)
$\displaystyle d_N \dots d_3d_2d_1i$ $\textstyle =$ $\displaystyle i + 10 \times d_N \dots d_3d_2d_1$ (4)

That is, every number in an interval $\left[10^{N}(i-1), 10^Ni\right]$ can be mapped to a number in $\left[0, 10^{N-1}\right]$ with quantifiable changes to its (and its reverse’s) residue modulo 7, simply by removing the first digit. In particular, by (3) and (4) this reduction is


$\displaystyle F(10^{N}(i-1), 10^Ni, x, y) = F(0, 10^N, x - 10^Ni, 10^{-1}(y - i))$     (5)

For example, each number in the interval [60, 69], can be mapped onto a one digit number by removing the tens digit, 6 (e.g, 62 becomes 2). If we were trying to calculate $F(60, 70, 6, 5)$, we could use this relation:


$\displaystyle F(60, 70, 6, 5)$ $\textstyle =$ $\displaystyle F(0, 10, 2, 2)$ (6)

Here’s why: The first 2 comes from the fact that when you subtract 60 from something with a remainder of 6 when divided by 7, the difference has a remainder of $6 - 60 \equiv 2$ (mod 7). The second 2 in Equation (6) is a little harder to see: Removing an initial 6 from a number whose reverse has a remainder of 5 has the effect of removing the last digit from its reverse. Subtracting 6 from a number that had a remainder of 5 changes the remainder to 6, then dividing by 10 changes the remainder to $6 \times 10^{-1} \equiv 6 \times 5 \equiv 2$ (mod 7).

Returning to Equation (2) and applying Equation (5), we have

\begin{eqnarray*}F(0, 100, 0, 0) & = & F(0, 10, 0, 0) + F(10, 20, 0, 0) + F(20,......) + F(0, 10, 0, 0) + F(0, 10, 4, 2) \\& & + F(0, 10, 1, 4) \\\end{eqnarray*}

Notice anything? Three of the terms, $F(0, 10, 0, 0)$, $F(0, 10, 4, 2)$ and $F(0, 10, 1, 4)$, appear twice. That means that rather than examine each number from 0 to 99 as it looked like we might need to do to find $F(0, 100, 0, 0)$, we need only examine the numbers from 0 to 9, 7 times each. We would then sum up the results of those 7 passes, taking care to count a certain three of them twice. That’s a 30% savings, but it doesn’t end there.

Suppose the original problem had been $F(0, 1000, 0, 0)$. We could divide it into 10 subproblems, each ranging from 0 to 100. Then, we could divide each of those up into 10 smaller problems from 0 to 10, then combining the ones that are copies. How many distinct problems would there be at this stage? They all have the form $F(0, 10, x, y)$ and $x$ and $y$ can only be integers in $[0,6]$. That’s only 49 subsubproblems, at the most. Now we have saved more than half the work. For any larger-sized ranges we could think of, the number of subproblems stays limited to 49.

We could find $F(0, 10^{1000}, 0, 0)$ by only looking at $F(0, 10, x, y)$ for 49 sets of $x$ and $y$, then doing a lot of adding!

There are two things left to do: Figure out how to add these subproblems back together and how to get the sum of those numbers, which was the original question.

Summing

Just to make things a little more compact, let $\alpha(N, x,i)$ be equal to $x - 10^Ni$ (mod 7) and $\beta(N, y,i)$ to $10^{-1}(y - i) \equiv 2(y - i) \equiv 2y + 5i$ (mod 7), we have

\begin{eqnarray*}F(0, 10^{N+1}, x, y) = \sum_{i=0}^9 F(0, 10^N, \alpha(N, x,i), \beta(N, y,i))\end{eqnarray*}

Remember the explanation for how we derived Equation (1)? We can carry out a similar reduction on $G$ to get


$\displaystyle G(0, 10^{N+1}, x, y)$ $\textstyle =$ $\displaystyle \sum_{i=0}^9 \Big{[}G(0, 10^N, \alpha(N, x,i), \beta(N, y,i)) +$  
    $\displaystyle \hspace{1em} 10^NiF(0, 10^N, \alpha(N, x,i), \beta(N, y,i))\Big{]}$ (7)

This is somewhat more complicated because when we map $i$-digit numbers to $i-1$-digit numbers, we aren’t changing $F$, which counts the numbers, but we are changing $G$, their sum. We have to add back in contributions made by the removed digits.

Building Back Up

We’ll maintain tables $\mathcal{F}_i$ and $\mathcal{G}_i$ at each level $i$ that hold the multiplicity of each of the $i$-digit subproblems.
To continue our mission to compute $G(0, 10^6, 0, 0)$, we begin by initializing the lowest order $\mathcal{F}$ table as follows below. The colors will be explained in a moment.

\begin{eqnarray*}\mathcal{F}_0 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......0 & 0 & \cellcolor[rgb]{.1,.4,0.4} 0 & 0 \\\hline\end{tabular}\end{eqnarray*}

Only $\mathcal{F}_0[0,0]$ has the value 1 because the only number with “0 digits” is 0, and it and its reverse have residue 0 modulo 7. We can apply Equation (1) to populate $\mathcal{F}_1$. Notice that each element in $\mathcal{F}_1$ is the sum of 7 elements in $\mathcal{F}_0$, 3 of them counted twice. E.g.,

\begin{eqnarray*}\mathcal{F}_1[2,2] & = & F(0, 10^1, 2, 2) \\& = & \sum_{i=0}...... 2) \\& = & \sum_{i=0}^9 F(0, 1, \alpha(0, 2,i), \beta(0, 2,i)\end{eqnarray*}

with $\alpha(0, 2, i) \equiv 2 - i \equiv 2 + 6i$ (mod 7), and $\beta(0, 2, i) = 4 + 5i$. When $i = 0$, this corresponds to the bluest cell (2,4) in $\mathcal{F}_0$. At $i = 1$, we’ve moved up and to the left to a slighter lighter blue cell. As $i$ ranges up to 9, we take a knight’s tour illustrated by the color fading from blue to green. The other cells visited are (1,2), (0,0), wrapping to (6,5), (5,3), (4,1), (3,6), and back to (2,4), (1,2) and (0,0). Notice that the 3 bluest cells are visited twice. In particular (0,0) is visited third and tenth, giving us two 1′s in the sum and $\mathcal{F}_1[2,2] = 2$.

Filling out the rest of $\mathcal{F}_1$,

\begin{eqnarray*}\mathcal{F}_1 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......& 0 \\& 6 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\hline\end{tabular}\end{eqnarray*}

And continuing with $\mathcal{F}_2$,

\begin{eqnarray*}\mathcal{F}_2 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......& 2 \\& 6 & 2 & 1 & 4 & 2 & 2 & 2 & 1 \\\hline\end{tabular}\end{eqnarray*}

To illustrate the interpretation of this, take $\mathcal{F}_2[5,0]$, in red. This means that are 4 numbers between 0 and 100 which have a remainder of 5 when divided by seven and when reversed, have a remainder of 0. Sure enough, there are four and they are 12, 19, 82 and 89. Continuing,

\begin{eqnarray*}\mathcal{F}_3 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......& 6 & 19 & 19 & 19 & 19 & 19 & 19 & 28 \\\hline\end{tabular}\end{eqnarray*}

and…

\begin{eqnarray*}\mathcal{F}_4 & = &\begin{tabular}{\vert cc\vert ccccccc\ve...... 195 & 203 & 216 & 186 & 235 & 187 & 206 \\\hline\end{tabular}\end{eqnarray*}

and…

\begin{eqnarray*}\mathcal{F}_5 & = &\begin{tabular}{\vert cc\vert ccccccc\ve...... 2021 & 1994 & 2123 & 2035 & 2100 & 2026 \\\hline\end{tabular}\end{eqnarray*}

At this point, we can extract all the needed values of the $F$-function to generate the $\mathcal{G}_i$ tables, via Equation (7). The $\mathcal{G}_i$ table is built in a similar fashion, except it draws from both $\mathcal{G}_{i-1}$ and $\mathcal{F}_{i-1}$. Unlike $\mathcal{F}_0$, $\mathcal{G}_0$ is entirely zeros. Within an asymptotically constant factor, the numbers in $\mathcal{G}_i$ are the squares of those in $\mathcal{F}_i$. As a result, the $\mathcal{G}_i$ tables must be omitted for space. However, ultimately, we do arrive at our answer $\mathcal{G}_6[0,0] = 10,363,989,636$.

Theoretical Analysis:

In general, for a base $b$ the computation of each subproblem is $\Theta(b)$. With forward and backward divisors $d_1$ and $d_2$, there are $d_1d_2$ subproblems on each of $N$ levels, thus this algorithm requires $\Theta(bd_1d_2N)$ operations. Practically speaking, $G(0, 10^{1000}, 0, 0)$, a number with 1,999 digits, can be calculated in only 14 seconds on my laptop.

More Numbers:

For completeness and for the curious, here are some extended results. The numbers in the range on the left that meet our divisibility conditions have their sum equal to the number on the right.

[0, 1] -$>$ 0

[0, 10] -$>$ 7

[0, 100] -$>$ 154

[0, 1000] -$>$ 10787

[0, 10000] -$>$ 1029567

[0, 100000] -$>$ 105714126

[0, 1000000] -$>$ 10363989636

[0, 10000000] -$>$ 1027216680497

[0, 100000000] -$>$ 102184086890270

[0, 1000000000] -$>$ 10205609904879424

[0, 10000000000] -$>$ 1020424310227628614

[0, 100000000000] -$>$ 102049428685193293045

[0, 1000000000000] -$>$ 10204479595989795520404

[0, 10000000000000] -$>$ 1020425244837350504933851

[0, 100000000000000] -$>$ 102041179796115463104759635

[0, 1000000000000000] -$>$ 10204085511291024760949778376

And the list continues….

Leave a Comment

Follow

Get every new post delivered to your Inbox.