13
$\begingroup$

Professor Erasmus has spent the last weekend by busily adding up all kinds of numbers. He told me today about his experiences: "On saturday evening, I added up twenty consecutive powers of $2$, and wrote their sum $S$ into my notebook. On sunday afternoon, I added up the first $n$ positive integers, and wrote their sum $T$ into my notebook. On monday morning, I suddenly realized that the sums $S$ and $T$ are equal. Mathematics is full of fascinating surprises!"

Has the professor once again made one of his well-known mathematical blunders, or do such twenty consecutive powers of $2$ indeed exist?

$\endgroup$
  • 1
    $\begingroup$ Professor Erasmus seems a bit like Fermat ("I have found a proof... but the margin is too small to contain it"-esque thing) $\endgroup$ – Conor O'Brien Sep 17 '15 at 2:28
19
$\begingroup$

The sum of twenty consecutive powers of $2$, starting at $2^k$ is:

$$S=2^k(1+2+4+\cdots+2^{19})=2^k(2^{20}-1)$$

and the sum of the first $n$ positive integers is:

$$T = 1+2+\cdots+n=\frac{n(n+1)}{2}$$

If these two quantities are equal

$$n(n+1)=2^{k+1}(2^{20}-1)$$

so it suffices to take $k=19,n=2^{20}-1=1048575$.

It is possible with lowest power of $2$ of $2^{19}$, and a sum of consecutive integers from $1$ to $1048575$.

$\endgroup$
6
$\begingroup$

If he claims to have done this without a computer, Erasmus has certainly made a mistake.

The first triangular number that is the sum of 20 consecutive powers of 2 is:

$1 + 2 + 3 + \ldots + 1048575 = 2^{19} + 2^{20} + \ldots + 2^{38} = 549755289600$

Erasmus might have computed the sum $S$ on Saturday afternoon. However, consider what he would have gone through on Sunday.

Suppose Erasmus can keep the current integer and the running sum in his head (so he's not slowed by having to write down the numbers). The world record for mental addition of 10-digit numbers is 2:51 to add 10 numbers. That comes out to 1.71 seconds per (random) digit. Now, Erasmus doesn't have quite as hard a job, because his digits aren't random -- but he will have to carry quite a lot more and he has many more digits to work with, 6.22 million. So let's suppose he can do a hundred times better than the world record holder at 17 milliseconds per digit. Unfortunately, it will still take him over a day to reach $T$ -- not a task that could be done in an afternoon.

(Yes, there's a simple shortcut, but Erasmus clearly states, "I added up the first $n$ positive integers," not "I calculated the sum of the first $n$ positive integers.")

Therefore, I think it's safe to say that the professor has bungled it up again.

Incidentally, if he was able to do it in his head in about 5 hours (as generous as I think I can get for "afternoon"), that would put him at 1 addition per 14 milliseconds, significantly faster than such early computers as the Harvard Mark I, Mark II, and Z3. If he had to use paper, he would have gone through several reams of the stuff.

$\endgroup$
  • $\begingroup$ Your formatting is a little weird... $\endgroup$ – Anthony Pham Sep 17 '15 at 11:14
  • $\begingroup$ @PythonMaster I had a hard time writing it up. If you have a constructive suggestion, feel free to make it. $\endgroup$ – trentcl Sep 17 '15 at 13:40
0
$\begingroup$

$$2^x + ... + 2^{x+19} = {n(n+1)\over 2} = 2^x(2^{20}-1)$$

$$n(n+1) = 2^{x+1} (2^{20}-1)$$

So it's definitely possible if $n = 2^{20}-1$ and $x = 19$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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