9
$\begingroup$

Please fill in the entire summations for lines 4 through 9 and just the total for line 1,000,000.

        1.     1   =   1
        2.    14   =   2 + 12
        3.    41   =   2 + 3 + 13 + 23
        4.    ?   =   ? + ? + ? + . . .
        5.    ?   =   ? + ? + ? + . . .
        6.    ?   =   ? + ? + ? + . . .
        7.    ?   =   ? + ? + ? + . . .
        8.    ?   =   ? + ? + ? + . . .
        9.    ?   =   ? + ? + ? + . . .
     1,000,000.    ?   =   (no need for the series of terms if you’re not in the mood)

The right side of each summation produces the minimum possible total from a series of unique numbers whose digits include one 1, two 2s, three 3s, and so on up to the line’s number.   Here are two straightforward approaches that produce non-minimal totals, as less than 111 is possible for line 4.

       4.          111   =   1 + 2 + 3 + 4 + 23 + 34 + 44

       4.      223334445   =   1 + 223334444

Beyond line 9, digits equivalent to 10 and more are in play for the summed terms, but digit positions have powers- of-10 values as usual.   Nothing here requires actual depiction of digits greater than 9 but, to clarify, a non-minimal line 10 might use [10] to represent the digit 10 like this.

  1.   122333444455555666666777777788888900111111109   =
                122333444455555666666777777788888888999999999
               +   [10][10][10][10][10][10][10][10][10][10]

           =   122333444455555666666777777788888888999999999
             + 10×1000000000 + 10×100000000 + 10×10000000 + 10×1000000
             + 10×100000 + 10×10000 + 10×1000 + 10×100 + 10×10 + 10

           =   122333444455555666666777777788888888999999999 + 11111111110

solutions should receive more approval than computed solutions, which would have value nonetheless as cross checks.

This puzzle was motivated by Two missing numbers.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ "whose digits include one 1, two 2s, three 3s, and so on up to the row’s number" - what does this mean when the row's number is greater than 9? $\endgroup$
    – Rand al'Thor
    Feb 19, 2017 at 22:59
  • 1
    $\begingroup$ So couldn't you lower your "score" by choosing a different base? That doesn't really make sense... $\endgroup$
    – Deusovi ♦
    Feb 19, 2017 at 23:11
  • 1
    $\begingroup$ (eg if the second row were expressed in base 3, then the sum would only be $21_3$, or 7) $\endgroup$
    – Deusovi ♦
    Feb 19, 2017 at 23:12
  • $\begingroup$ Better now, hopes $\endgroup$
    – humn
    Feb 20, 2017 at 0:45

3 Answers 3

Reset to default
6
$\begingroup$

We proceed by induction.

In row $n$, all the digits $n$ should appear as units digits, not tens or hundreds digits. So we have $n+1n+2n+3n+\dots$ as part of the sum. This uses up all the digits $n$ and one of each of $1,2,3,\dots,n-1$, leaving still to be allotted a total of $k-1$ digits $k$ for every $k$ from $2$ up to $n-1$. These remaining digits should then be arranged in exactly the same way as in the $(n-2)$th row but with each digit incremented by $1$. Let's see how this works in practice:

  1. $4+14+24+34$ plus ($2+12$ incremented by one) gives $3+23+4+14+24+34$.

  2. $5+15+25+35+45$ plus ($2+3+13+23$ incremented by one) gives $3+4+24+34+5+15+25+35+45$.

So the $n$th row has one more one-digit number, and $n-1$ more two-digit numbers, than the $(n-1)$th. Thus, by induction:

  • for $n=2k$ the $n$th row has $k$ one-digit numbers and $k^2$ two-digit numbers;
  • for $n=2k-1$ the $n$th row has $k$ one-digit numbers and $k(k-1)$ two-digit numbers.

And by induction again, we can compute the sum $S_n$ of the $n$th row as follows:

  • if $n=2k$, then \begin{align} S_n&=n+1n+2n+\dots+(n-1)n+(S_{n-2}\text{ incremented by $1$}) \\&=n^2+10\frac{n(n-1)}{2}+S_{n-2}+(k-1)+11(k-1)^2 \\&=S_{n-2}+4k^2+10k(2k-1)+(k-1)(11k-10) \\&=S_{n-2}+35k^2-31k+10\end{align}
  • if $n=2k-1$, then \begin{align} S_n&=n+1n+2n+\dots+(n-1)n+(S_{n-2}\text{ incremented by $1$}) \\&=n^2+10\frac{n(n-1)}{2}+S_{n-2}+(k-1)+11(k-1)(k-2) \\&=S_{n-2}+(2k-1)^2+10(k-1)(2k-1)+(k-1)(11k-21) \\&=S_{n-2}+35k^2-66k+32\end{align}

Now we have inductive formulae for the solution, which will simplify in order to give reasonably straightforward formulae which are cubic in $k$, and possibly even a unified formula depending only on $n$. As shown in this CW answer from the OP, the sum for $n=1,000,000$ is

$S_{1,000,000}=1,458,333,833,333,500,000$

(I haven't checked the details of this derivation, but I trust humn to get it right).

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ For $n=3=2\cdot 2-1$, your formula gives $S_3=S_1+(2-1)(31\cdot 2-11)=52$, not $41$ as in the OP. Am I missing something? $\endgroup$
    – Ankoganit
    Feb 20, 2017 at 4:22
  • $\begingroup$ Rand, you made a mistake in your last equation. 10(k-1)(2k-1) + (k-1)(11k-21) = (k-1)(20k - 10 + 11k - 21) = (k-1)(31k - 31). Also, i think you lost your n^2 which would be why your equation doesn't work. $\endgroup$
    – Piotr Pytlik
    Feb 20, 2017 at 9:40
  • 1
    $\begingroup$ @Ankoganit Should be working now. $\endgroup$
    – Rand al'Thor
    Feb 20, 2017 at 10:58
  • $\begingroup$ I've been impressed from the start by how quickly you solved the pattern! The algebra is inevitably cluttered, admittedly, so in test-solving this I ran straight to the relatively lazy cubic form. Speaking of which, just what is that total for line 1,000,000? $\endgroup$
    – humn
    Feb 20, 2017 at 14:58
  • $\begingroup$ (Dear rand al'thor, this could be yet another $\color{#0c0}{\Large\raise-.1ex\checkmark} \!$ in your cap if you copy line 1,000,000's total from the presumably-correct wiki answer.) $\endgroup$
    – humn
    Apr 18, 2017 at 6:06
1
$\begingroup$

First, as pointed out by rand al'thor, the biggest digit $n$ should be always used as units digit. Then we add one of each smaller digit in front to create $n$ distinct numbers, so for $n=4$ we get

4 14 24 34

Then, we repeat the same procedure for $n-1$, but now only $n-2$ times, since one digit is already used. The procedure ends when we used all required digits. Putting it in a nice math formula:

$$S = \sum_{i=0}^{\lfloor n/2\rfloor}(n-i)(n-2i) + 10\sum_{i=1}^{\lfloor n/2\rfloor}(\sum_{j=i}^{n-i}j)$$

The first part of the equation accounts for counting all the units, the second for tens.

This gives:

4:

$4+14+24+34$ and $3+23 = 102$

5:

$5+15+25+35+45$ and $4 + 24+34$ plus $3 = 190$

6:

$6+16+26+36+46+56$ plus $5+25+35+45$ plus $4+34=334$

7:

518

8:

780

9:

1095

1000000:

1.4583e+018

Improve this answer
$\endgroup$
1
$\begingroup$

Wiki answer to illustrate and complete rand al'thor’s solution:   An example of how terms of an even line inductively build the terms of the next even line, and a way to get line 1,000,000’s total by hand.

         Terms of line 6                                      Terms of line 8
     -----------------------                              -----------------------
                                     all-new
                                       row          8   18   28   38   48   58   68   78
                                     ------->       '----'---:'---:'---:'----'----'----'
                                                             :    :    :    |    |    |
   6    16   26   36   46   56        +1 +1           7      27   37   47   57   67   |
   '-----'----'----'----'----'        ----->          '-------'---:'---:'----'----'---'
             :    :    |    |                                     :    :    |    |
     5       25   35   45   |         +1 +1             6         36   46   56   |
     '--------'----'----'---'         ----->            '----------'---:'----'---'
                  :    |                                               :    |
       4          34   |              +1 +1               5            45   |
       '-----------'---'              ----->              '-------------'---'

     (Smaller digits appear as columns only, larger digits follow rows as well)


Getting the total of line $\boldsymbol n$ = 1,000,000 (by hand)

Call $\, \sum_n$ the cubic polynomial for the total of line $n$, where $n$ is even, and use constants $\small A,B,C,D\,$ in a way that makes them easy to work by hand.

$$\require{begingroup}\begingroup \small \def \S #1{ \llap{\textstyle \sum_{#1}} } \def \f #1#2{ {\normalsize #1 \over \normalsize #2} } \def \F #1#2{ { \large #1 \over \normalsize #2} } \def \PF #1#2{ {\large\raise -.3ex(} \kern-.1em \F{#1}{#2} \kern-.1em { \large\raise-.3ex)} } \small \begin{array}{rl} & \normalsize \S{n} \small = \kern-.8em & \normalsize \rlap{ An(n{-}2)(n{-}4) + Bn(n{-}2) + Cn + D } \\[3ex] 0 ~ = ~~ & \S{0} = \kern-.8em & A(0)(-2)(-4) + B(0)(-2) + C(0) + D & \kern-0.5em = D & \Longrightarrow~~ D ~~~ = ~~~~ 0 \\[1.5ex] 14 ~ = ~~ & \S{2} = \kern-.8em & A(2)(0)(-2) \,~ + \,\: B(2)(0) \,~ + ~ C(2) & \kern-1.0em = 2C & \Longrightarrow~~ C ~~ = ~~~~ \f{14}{2} ~~~~ = ~~ 7 \\[1.5ex] 102 ~ = ~~ & \S{4} = \kern-.8em & A(4)(2)(0) \;~~ + ~~ B(4)(2) ~~ + ~ 7(4) & \kern-1.5em = 8B + 28 & \Longrightarrow~~ B ~ = ~~ \f{102{-}28}{8} ~~ = ~ \f{37}{4} \\[1.5ex] 334 ~ = ~~ & \S{6} = \kern-.8em & A(6)(4)(2) ~~ + ~~\, \f{37}{4}(6)(4) ~ + ~ 7(6) & \kern-2.0em = 48A + 222 + 42 \kern-.5em & \Longrightarrow~~ A = \f{334{-}222{-}42}{48} = \f{35}{24} \\[3ex] & \normalsize \llap{\Longrightarrow~~ \textstyle\sum_n} \small = \kern-.8em & \normalsize \rlap{ \f {35}{24}n(n{-}2)(n{-}4) + \f {37}{4} n(n{-}2) + 7n } \\[1ex] & \llap{} = \kern-.8em & \rlap{ \f {35}{24} n(n^2{-}6n{+}8) + \f{222}{24}n(n{-}2) + \f{168}{24}n } \\[1ex] & \llap{} = \kern-.8em & \F {n}{24} ( 35n^2 + 12n + 4 ) \\[1ex] & \llap{} = \kern-.8em & \F{n}{6} \big( 875 \PF{n}{10}^2 + 3n + 1 \big) \\[3ex] & \normalsize \S{1,000,000} \small = \kern-.8em & \f{10^6}{6} \big( 875(10^{10}) + 3(10^6) + 1 \big) \\[1.5ex] & \llap{} = \kern-.8em & \rlap{\large{8,750,003,000,001,000,000 \over 6}} \\[1ex] & \llap{} = \kern-.8em & 1,458,333,833,333,500,000 \end{array}\endgroup$$

This amounts to a line 1,000,000 with 250,000,500,000 terms.

1,000,000.   1,458,333,833,333,500,000   =
             [500,001] + [500,002] + [500,003] + · · · + [1,000,000]
            + 1[1,000,000]
            + 2[999,999] + 2[1,000,000]
            + 3[999,998] + 3[999,999] + 3[1,000,000]
            + · · ·
            + [500,000][500,001] + [500,000][500,002] + · · · + [500,000][1,000,000]
            + · · ·
            + [999,997][999,998] + [999,997][999,999] + [999,997][1,000,000]
            + [999,998][999,999] + [999,998][1,000,000]
            + [999,999][1,000,000]

Improve this answer
$\endgroup$
1
  • $\begingroup$ Note: The $\sum_n$ summation here should've been labeled $S_n$ to follow rand al'thor's solution. $\endgroup$
    – humn
    Apr 18, 2017 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.