2

There is a debate about this Project Euler problem in the discussion thread for the problem.

The debate is whether you only have to add the first 12 digits of each number in order to get the answer.

For the particular question, it works fine if you only sum the first 12 digits of each number. But is this always the case?

ktm5124
  • 429
  • I'm not sure that suffices to solve the problem. The $11$th digit may depend on the $12$th digit. – Daniel Mar 27 '15 at 03:22
  • Thanks. I edited my post to say the first 12 digits. – ktm5124 Mar 27 '15 at 03:29
  • 1
    But again, the $12$th digit depends on the $13$th digit! – Daniel Mar 27 '15 at 03:30
  • Haha, touche. So the carry from the last 38 digits could affect the outcome of the first 10? In fact... the carry from the last N digits could affect the outcome of the first 10, for any N >= 1? – ktm5124 Mar 27 '15 at 03:30
  • Ross Millikan's comment talks about it: Every digit affect the previous one. – Daniel Mar 27 '15 at 03:32
  • I see. Is there any clever way to solve for the first 10 digits? I ended up solving it by writing my own BigInteger class (analogous to java.math.BigInteger). But I was looking for a clever solution! – ktm5124 Mar 27 '15 at 03:38
  • Maybe adding from right to left the digits in pairs whose sum is $10$, but you're right, there must be a better solution than brute force, but I can't see it. – Daniel Mar 27 '15 at 03:40

1 Answers1

1

It does not necessarily work. Consider the following fifteen $12$-digit numbers:

\begin{align} 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ 100000000019&\,\\ \underline{+ \,\,\,100000000019}&\,\\ 1500000000\color{red}{2}85&\,\\ \end{align}

But

\begin{align} 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ 10000000001&\,\\ \underline{+ \,\,\,10000000001}&\,\\ 1500000000\color{red}{1}5&\,\\ \end{align}

Also, are you sure the result is the same if you ignore the $12^\text{th}$ digits? There are $100$ numbers in the $12^\text{th}$ places, and there is a high chance that their sum affects the $10^\text{th}$ place (it suffices that their average is at least $1$, but as Ross Millikan points out, it is also possible for the $12^\text{th}$ place digits to carry over without a total of $100$).

Zubin Mukerjee
  • 17,832
  • But your example only has 15 numbers. Is it significant that there are 100 in the Project Euler problem? (As multiplying any number by 100 shifts its digits two places over.) – ktm5124 Mar 27 '15 at 03:27
  • Your last paragraph is wrong. One can construct an example where the carry goes forward as far as you want. The probability that it does (given "random" numbers to sum) goes down by a factor of $10$ for each extra digit that you keep, but it is still possible. – Ross Millikan Mar 27 '15 at 03:29
  • @RossMillikan You're right, I'll fix it. EDIT: should be better now? – Zubin Mukerjee Mar 27 '15 at 03:30