What do 7, 77 and 168 have in Common?
by Jonathan Wellons
If you'd like to test your algorithmic wit, describe how to speed these calculations up (Ie., without actually adding up all the numbers):
What is the sum of the whole numbers between 1 and a trillion (10^12)?
What is the sum of the whole numbers between 1 and a trillion that have the additional property that they are divisible by 7? (7, 14, 21, ...)
What is the sum of the whole numbers between 1 and a trillion that are divisible by 7 and when reversed are still divisible by 7? Numbers like 7, 168, and 1169 do this.
19 Comments
Markus 20070413 15:07:55 
Sum for the whole number between 1 and 10^12: 2 * sum(1..10^11), and that is (according to my friend Gauss): 2 * (10^11+1)*(10^11/2)

Jonathan Wellons 20070413 15:18:29 
I love the Gauss reference! Can I assume you meant 12 instead of 11? Why is it multiplied by 2?

Andrew J 20070413 15:34:27 
It's well known (to mathematicians at least) that the sum of the integers from 1 to n is given by the formula n*(n+1)/2, thus putting by n=1e+12 the first question comes to 5.00000000001e+23.

20070413 15:50:26 
Andrew is right that sum(1..n) = n*(n+1)/2 I just read "even" instead of "whole" numbers, which result in sum(1..n : n is even) = 2*sum(1..n/2) 
Wil 20070413 19:52:24 
May I suggest that rather than saying something is obvious to a certain class of people, that you bother to make your reasoning clear? What's interesting about these problems is not that you have a quick, clever shortcut (likely produced by others), but rather that you know how to think through the issue at hand. 
Jonathan Wellons 20070413 23:38:01 
Andrew  You're also right about 1 and 2. The 3rd one may be in a slightly different ballpark, but it does have an answer. I'm very interested in if anyone has a simpler one than I do.

SDiZ 20070415 03:17:58 
The 3rd one, I have a dynamic programming answer written in perl:

SDiZ 20070415 03:37:19 
Just FYI, my program use around 300kB of memory (include perl, my program, data, etc..etc..). 
SDiZ 20070415 06:23:42 
Oops... I was doing the wrong problem... I count the number of them instead of summing them up. 
SDiZ 20070415 07:01:01 
okay, fixed. this require Math::BigInt::GMP.

Jonathan Wellons 20070415 12:35:48 
Nice work SDiZ! It sounds like you have the same algorithm as I do (Dynamic Programming). I also get the same answer

George Jempty 20070416 06:00:51 
"What is the sum of the whole numbers between 1 and ...."

Jonathan Wellons 20070416 09:21:53 
Dear George Jempty,

SDiZ 20070417 08:21:02 
Seems my comment can't get though the spam filter. Let's scramble the URL a bit: http:wwwsdiznet/temp/seven.txt (replace the '' with the correct character) 
Jonathan Wellons 20070417 17:58:14 
SDiZ,

20070511 15:00:29 
for the answer to the third question you simply use the equation 10^12/7a(2) 
Jonathan Wellons 20070511 15:18:56 
Dear Anonymous,

Jennifer 20071007 14:21:48 
What do the numbers 1, 3, 6, and 9 either have in common? 
Jonathan Wellons 20071008 08:08:34 
Dear Jennifer,
