What do 7, 77 and 168 have in Common?

by Jonathan Wellons

If you're a programmer, you may spend a lot of time figuring out how to make things faster. If you work with number-crunching, you've seen plenty of cases where you can greatly reduce a program's runtime by some huge factor. You're probably pretty good at it...

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
2007-04-13 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)


The same should work for the multiple of 7:
7 * sum(1..(10^12/7)) = 7 * ((10^12)/7+1)*((10^12)/7/2)
Of course you have to floor() all division-by-7 operations

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


I'm especially interested in any answers to the 3rd question.

Andrew J
2007-04-13 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.


The second question can be solved by dividing the whole problem by 7, which reduces it to the same as the first problem but with n=1e+12/7, giving approximately 1.02e+22 which we multiply by 7 to get the final answer: 7.143e+22.


The third one is in a totally different ballpark...


2007-04-13 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
2007-04-13 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
2007-04-13 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.


Wil - Thanks.


Markus - Thanks for clearing that up.

SDiZ
2007-04-15 03:17:58
The 3rd one, I have a dynamic programming answer written in perl:


sdiz@sp2:/tmp$ time perl seven.pl
DIGIT=0 N=1
DIGIT=1 N=2
DIGIT=2 N=4
DIGIT=3 N=22
DIGIT=4 N=206
DIGIT=5 N=2113
DIGIT=6 N=20728
DIGIT=7 N=205438
DIGIT=8 N=2043640
DIGIT=9 N=20411101
DIGIT=10 N=204084732
DIGIT=11 N=2040990205
DIGIT=12 N=20408959192


real 0m0.021s
user 0m0.016s
sys 0m0.000s

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


sdiz@sp2:~$ time perl seven.pl
DIGIT=0 N=1 SUM=0
DIGIT=1 N=2 SUM=7
DIGIT=2 N=4 SUM=154
DIGIT=3 N=22 SUM=10787
DIGIT=4 N=206 SUM=1029567
DIGIT=5 N=2113 SUM=105714126
DIGIT=6 N=20728 SUM=10363989636
DIGIT=7 N=205438 SUM=1027216680497
DIGIT=8 N=2043640 SUM=102184086890270
DIGIT=9 N=20411101 SUM=10205609904879424
DIGIT=10 N=204084732 SUM=1020424310227628614
DIGIT=11 N=2040990205 SUM=102049428685193293045
DIGIT=12 N=20408959192 SUM=10204479595989795520404


real 0m1.920s
user 0m1.864s
sys 0m0.012s

Jonathan Wellons
2007-04-15 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


118795$ time mzscheme -mf 7-by-7.ss 12
10204479595989795520404


real 0m0.302s
user 0m0.260s
sys 0m0.000s


Here is My Program and here's A Mathematical Description. Can we see your program, SDiZ?

George Jempty
2007-04-16 06:00:51
"What is the sum of the whole numbers between 1 and ...."


Please stop insulting our intelligence; any schoolboy who pays sufficient attention knows this one

Jonathan Wellons
2007-04-16 09:21:53
Dear George Jempty,


It's all relative. If it's too easy for you, you're welcome to try the third problem. You may find something faster than we did.


Best Wishes,
Jonathan

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


Sorry about the filter. It gives me trouble too -- O'Reilly used to have tons of trouble with spam so they must have turned it up.



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


Can you clarify what "7a(2)" means?


Thanks,
Jonathan

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


I give up. I guess 1369 = 37 * 37, but that could hardly be what you meant. What do they have in common?


Thanks!
Jonathan