Concatenations, Part 2

In my last post, I talked about finding a string of 2,402 zeroes in the middle of the addition of the concatenation of 1, 2, 3, …, 960, 961, 962, plus the concatenation of 962, 961, 960, … , 3, 2, 1.  That is,

123456789 … 960961962 +
962961960 … 987654321 =
108641875 … [2402 zeroes] … 948616283.

With the wonderful help of Hans Havermann, I now understand how the string of zeroes came to appear there and seemingly nowhere else.

Let’s call x the maximum value in the concatenation (x = 962 here), A the ascending concatenation (A = 1123456789 … 960961962), and D the descending concatenation (D = 962961960 … 987654321).  When aligning A and D at the one’s place to add them (as we usually do), then the digits “960” from A pair up with “987” from D, as well as “961” with “654” and “962” with “321” at the very end on the right.  Working back to the left (down in A and up in D), the “900” from A lines up with “999” in D (from the number 99 and the first digit of 98).  From there (working left), both A and D have series of three-digit numbers, A going from 899 down to 100 and D going up from 100 to 899.  They all add up to a series of 10s, or a digit of 0 with a carry of 1.  Let’s look at a section:

A:       … ¹8 ¹9 ¹7 ¹8 ¹9 ¹8 ¹8 ¹9 ¹9 …
D:       …  1  0  2  1  0  1  1  0  0 …
sum:   …  0  0  0  0  0  0  0  0  0 …

(The superscript 1 indicates a carry from the previous column.)

From 100 to 899 is 800 numbers, each with three digits, for a total of 2,400 digits.  Then, when A goes from 100 down to 99, D goes up from 899 to 900.  Those last two digits (“99” from 99 in A and “00” from 900 in D) give two more zeroes, or a total of 2,402 zeroes in succession.

This could only happen because, working from right to left, both A and D have the same number of digits before the zeroes start.  A begins at 962 (the maximum value, x) and goes down to 900.  That trip involves 63 three-digit numbers, for a total of 189 digits.  In that same space, D starts at 1 and goes up to 99.  Here, there are nine digits used in the numbers 1 – 9.  Then, from 10 – 99, there are 90 two-digit numbers, or 180 more digits, to give the same total of 189.

In summary, A (the concatenation 123 … 962) + D (the concatenation 962 … 321) = a sum with 2,778 digits, 2,402 (86%) of which are in one string of zeroes.  That middle of zeroes comes from the digits for 100 – 899 from one addend lining up with the digits for 899 – 100 from the other, all giving digits of 0 with carries of 1.  Before that, however, the digits for 1 – 99 perfectly aligned with those from 962 – 900, allowing the middle magic to happen.

This happened for x = 962 (that is, concatenating 1 – 962 and 962 – 1).  Does it happen for other values of x?  Yes, but rarely.  962 is a three-digit number, and it is just far enough beyond 900 that the number of digits from 900 (three-digit number with a 9 and the rest 0) to 962 are exactly the same as the number of digits from 1 – 99 (two-digit number, all 9s).  That number of digits also has to be a multiple of three, since the numbers from 900 through 962 are all three-digit numbers.

So the key is how many digits there are in the concatenation of 1 – 999…999 where the number of 9s is one less than the number of digits in x (two 9s for the three-digit 962, in this case).  How many digits are there in 1 – 999…999?  For 1 – 9, there are nine single-digit numbers, so 9 digits in total.  1 – 99 is 1 – 9 and 10 – 99, nine single-digit and 90 two-digit numbers, or 189 in all.  More ranges are shown in this table:

Size of x	Range	1 digit	2 digits	3 digits	4 digits	5 digits	Total Digits
2 digits	1 - 9	9					9
3 digits	1 - 99	9	180				189
4 digits	1 - 999	9	180	2,700			2,889
5 digits	1 - 9,999	9	180	2,700	36,000		38,889
6 digits	1 - 99,999	9	180	2,700	36,000	450,000	488,889

The last column is series A033713 in the Online Encyclopedia of Integer Sequences.  (The sequence has a nice pattern:  the first digit gives the number of 8s after it, and the element ends with a 9.)  In the case of 962, the number of digits from 1 – 99 is 189.  And since 189 is a multiple of 3, then a whole number of three-digit numbers (63 of them, from 962 – 900) will align with the digits from 1 – 99.

What about for other cases?  For a two-digit largest number x, then the nine digits 1 – 9 would need to match the number of digits in 90 – x, for some x.  All the numbers from 90 – x are two-digit numbers, so the total number of digits would be even, never nine, so there’s no long string of zeroes.  Likewise with four- through 8-digit numbers—there’s never a match between the numbers of digits from 1 – 99…99 in D and 90…00 – x in A (for any x).

The next possible case is for a nine-digit number, and x = 987,654,320.  Instead of concatenating 1 – 962, we need to concatenate 1 – 987,654,320.  The resulting sum would have 8,777,777,778 digits, 7,200,000,008 of which would be in one string of zeroes in the middle.

Since this whole question revolves around representing numbers in decimal (base 10), it seems reasonable (to me, anyway), to ask, what happens with other bases?  Take, for example, base 5.  In base 5, the numerals are 0, 1, 2, 3, and 4.  Numbers larger than four use multiple digits; four in base 5 is 4, just like in decimal. Five is 10₅ (one times five plus zero times 1, and the subscript 5 means the number is to be read in base 5 instead of decimal), six is 11₅, ten is 20₅, etc. So, in base 5, D doesn’t have a string from 99 – 1 to balance the high end of A, it would have a string from 44₅ – 1 or 444₅ – 1, or whatever—4s in base 5 take the place of 9s in base 10—one less than the base. Here is the table for the number of digits in the range 1 – 444…444₅:

Size of x	Range	1 digit	2 digits	3 digits	4 digits	Total Digits	Total Digits5
2 digits	1 - 4	4				4	4
3 digits	1 - 445 (24)	4	40			44	1345
4 digits	1 - 4445 (124)	4	40	300		344	2,3345
5 digits	1 - 4,4445 (624)	4	40	300	2,000	2,344	33,3345

(Note the last column:  in base 5, the sequence for the total number of digits has a similar pattern to that for decimal numbers, but 3 and 4 take the place of 8 and 9, respectively.  The first digit is the number of 3s following it, and then a final 4.)

As with base 10, there will only be a long string of zeroes when the total digits is a multiple of the number of digits in x.  In base 5, that occurs fairly frequently, for x = 21, 585, 14,973, and 378,417, for starters (41₅, 4,320₅, 434,343₅, and 44,102,132₅, respectively).

In binary (base 2), there are no cases (up through x with 40 digits) where long strings of zeroes occur.  Here are some other results (in base 10):
•    base 2:  none, up through x with 40 digits
•    base 3:  6, 70, 6,150, etc.
•    base 4:  56, 252,434, etc.
•    base 5:  21, 585, 14,973, 378,417, etc.
•    base 6:  7,464, etc.
•    base 7:  44, 323, 2,300, 114,380, etc.
•    base 8:  2,054,353 is the smallest
•    base 9:  75, 6,355, etc.
•    base 10:  962, etc.
•    base 11:  114, 14,274, 157,829, etc.
•    base 12:  736,867,805,640 is the smallest
•    base 13:  161, 2,135, 27,965, etc.
•    base 14:  none, up to 12-digit x values
•    base 15:  216, 49,720, etc.
•    base 16:  4,004, etc.

Prime-valued bases (aside from 2) seem to have relatively more occurrences of long strings of zeroes.  Why?  Got me.

Concatenations

Take the numbers 1, 2, and 3 and concatenate them as 123, or one hundred twenty-three.  Then, reverse the order and concatenate them as 321, or three hundred twenty-one.  Add them and you get 444.  This is the third element of a sequence that begins:

• A(1) = 1 + 1 = 2
• A(2) = 12 + 21 = 33
• A(3) = 123 + 321 = 444
• A(4) = 1234 + 4321 = 5555, etc.

It seems pretty straightforward until the ninth element, when the carries start to complicate things.  The first 20 steps can be illustrated by using disks of color.  Here, each row represents a step in the sequence, with the first number (2) being represented by the bottom row (the single gray dot on the right).  The next row up shows 33 with two lighter gray dots.  In general, the shade of gray represents the digit, from black for 0 to white for 9.

The above image shows that a change from rows of constant color to other structures happens around the 10th step in the sequence.  Other interesting changes happen around the 100th step, as shown below.  The rows represent steps 91 (bottom) through 190 (top), and the first 200 digits (from right to left).

Around the 1000th step, things change again.  This image (below) shows steps 926 (bottom) through 1125 (top), and the first 400 digits of the sums.

Notice the black horizontal line across the left half of the image, about one-quarter of the way up from the bottom.  This happens at step 962.  Black means a digit of 0, so this shows the beginning of a line of a few thousand zeroes.  Or, 12345…960961962 + 962961960…54321 = a 2,779-digit number with a run of 2,402 zeroes in the middle of it.  I’m still looking for other long runs of zeroes, but haven’t found any yet.

Different, but similar images arise when subtracting the numbers rather than adding.  The image at the top of this page combines both ideas; the inner dots represent the digits of the differences between the concatenated numbers and the backgrounds of the square cells correspond the the digits of the sums.