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
    Commented 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 ♦
    Commented 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 ♦
    Commented Feb 19, 2017 at 23:12
  • $\begingroup$ Better now, hopes $\endgroup$
    – humn
    Commented 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
    Commented 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
    Commented Feb 20, 2017 at 9:40
  • 1
    $\begingroup$ @Ankoganit Should be working now. $\endgroup$
    – Rand al'Thor
    Commented 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
    Commented 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
    Commented 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
    Commented Apr 18, 2017 at 19:34

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