The stupid question is the question not asked PerlMonks

### Finding sum of all digits from 1 to 1 million.

 on Jan 23, 2002 at 23:58 UTC Need Help??
vladb has asked for the wisdom of the Perl Monks concerning the following question:

Hi, There was a node on node on the Discussions page that mentioned an encryption contest held by a university. As it appeared, the contest was pretty basic (by far way tooo simple). Here's the code that is supposed to give the right answer to this question "FIND THE SUM OF ALL DECIMAL DIGITS APPEARING IN THE NATURAL NUMBERS FROM ONE TO ONE MILLION INCLUSIVE":
```my (\$s,\$x,\$i);
for (\$i=0; \$i<1e6; \$i++)
{
#        print "\$i:";
# get all digits in a number
for (\$i=~/./g) {
#                 print "\$_ ";
# sum all digits
\$s += \$_;
}
#        print " (\$s)\n";
};
I was positive the code had to produce the right answer, however, it didn't. Instead, it came up with this number: 27000000. Is this a problem with Perl or the code? Or should I use a Big integer module in order to yield the right number?

Thanks,

 "There is no system but GNU, and Linux is one of its kernels." -- Confession of Faith

Replies are listed 'Best First'.
(tye)Re: Finding sum of all digits from 1 to 1 million.
by tye (Sage) on Jan 24, 2002 at 00:36 UTC

Without getting formal about the proof:

```1..9 = 45
1..99 = SumOfTensDigits + SumOfOnesDigits
= 10*1..9 + 10*1..9 = 900
1..999 = SumOfHundredsDigits + SumOfTensAndOnesDigits
= 100*1..9 + 10*1..99 = 4500 + 9000 = 13500
1..9999 = 1000*1..9 + 10*1..999 = 45000 + 135000 = 180000
...
1..'9'x\$n
= 45, 450+450, 4500 + 4500+4500, 45000 + 3*45000, ...
= 4.5*\$n*10^\$n
1..1e6 = 1..'9'x6 + 1 = 4.5*6*10^6 + 1 = 27e6 + 1
= 27_000_001
so the code is actually only off by one because it uses < but they said "INCLUSIVE". (:

- tye (but my friends call me "Tye")
Re (tilly) 1: Finding sum of all digits from 1 to 1 million.
by tilly (Archbishop) on Jan 24, 2002 at 00:49 UTC
Fencepost error. The spec says inclusive, and your C-style for loop does not include 1e6. Use a Perl-style foreach loop and you would be unlikely to make the same mistake.

But still this one is faster to do with pen and paper. Convince yourself of the following:

1. The total contributions from the 7'th (and higher) digits is the 1 in 1_000_000.
2. For each given digit from the first through the sixth, there are 100_000 times that it is 0, 100_000 times it is 1, and so on up to 100_000 times it is 9.
3. The answer is therefore 1 + 6*(0+1+2+3+4+5+6+7+8+9)*100_000.
4. Therefore the answer is 27_000_001.
Now with this insight, a good exercise would be to write Perl code that efficiently calculates the sum of all of the digits in a range of integers. (Hint: Break things up by digit, and try to count how many you are going to have of each kind first.)
a good exercise would be to write Perl code that efficiently calculates the sum of all of the digits in a range of integers.
Assuming sum(n) is the sum of all digits from 1 to n, sum_range(m, n) is the sum of all digits from m to n, and m < n, isn't the following true?
```sum_range(m,n) = sum(n) - sum(m)
Or, did I totally get you wrong? /prakash
Off by one error again, your formula drops m from the answer. (And the obvious fix will need more cases if your range potentially includes negative integers.)

But still, you are essentially correct. After some wrapper logic, the problem really does boil down to being able to efficiently calculate the sum of the digits from 1 to n for any positive integer n.

Re: Finding sum of all digits from 1 to 1 million.
by bmcatt (Friar) on Jan 24, 2002 at 00:31 UTC
Ummm... You're actually close, although you're off by 1. Fencepost error - you're terminating the loop one too early, so you're not including 1e6 in the loop. When in doubt, let perl figure out the right way to do it for you:

A slightly modified version:

```#!/usr/bin/perl -w

use strict; # or die :-)

my \$LIMIT = 1000000;

my \$s;

foreach (1 .. \$LIMIT) {
foreach (/./g) {
\$s += \$_;
}
}

print "Sum: \$s\n";

Golfers invited to make this even nicer (not to mention make it run faster...)

Re: Finding sum of all digits from 1 to 1 million.
by runrig (Abbot) on Jan 24, 2002 at 00:38 UTC
..FROM ONE TO ONE MILLION INCLUSIVE

```for (\$i=0; \$i<1e6; \$i++) {
...
You're missing 1,000,000 and so are off by one.
Here's another way (which is still the long way, BTW):
```my \$total;
for (1..1_000_000) {
\$total += \$_ for split "";
}
print "\$total\n";
(Ovid) Re: Finding sum of all digits from 1 to 1 million.
by Ovid (Cardinal) on Jan 24, 2002 at 00:07 UTC
```\$ perl -e '\$sum += \$_ for ( 1..1000000 );print \$sum'
500000500000

Update: Whoops! :) Here's a brute force solution:

```\$ perl -e 'for(1..1_000_000){\$sum+=\$_ for(split//)};print \$sum'
27000001

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.

Re: Finding sum of all digits from 1 to 1 million.
by lhoward (Vicar) on Jan 24, 2002 at 00:17 UTC
With deference to jeffa and Ovid: you did not answer the right question. What vladb was asking for was "find the sum of all decimal digits appearing in the natural numbers from one to one million inclusive", not "find hte sum of all integers from 1 to one million inclusive".
mh, ok, repeat after me *grin*:
ALL INTEGERS BIGGER THAN 0 ARE NATURAL NUMBERS !

Have a nice day
All decision is left to your taste
Update:
Uhm ok, seems I got you wrong here.
so did you mean the solution would more look alike
```\$ perl -e '\$sum += length(\$_) for ( 1..1000000 );print \$sum'
But then I ask myself if that question is not much more tricky, cause there are only 10 decimal numbers we use to represent all numbers. So what is teh right answer though?
the result of the above, as it is 5888896 or simply 10?
(jeffa) Re: Finding sum of all digits from 1 to 1 million.
by jeffa (Bishop) on Jan 24, 2002 at 00:06 UTC
```perl -le "print 1_000_000 * 1_000_001 / 2"
Didn't need Math::BigInt, so i would say there is a problem in the code.

(that formula is one of Guass's, by the way)

UPDATE: details details! :D

seriously, sorry about that, does this help?

\$sum += split('',\$_) for (1..1_000_000);

You rule, tye! ;)

jeffa

```L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--

H---H---H---H---H---H---
```
That tells you the sum of all integers from 1 to 1 million. It doesn't give you the sum of all the digits in those numbers. To illustrate the difference: The sum of all numbers from 1 to 15 is 105 (1 + 2 + 3...+15) The sum of all digits in those numbers is 66 (1 + 2 + 3...+ (1 + 0)... + (1+ 5)) -Beth
Re: Finding sum of all digits from 1 to 1 million.
by mrbbking (Hermit) on Jan 24, 2002 at 02:11 UTC
FIND THE SUM OF ALL DECIMAL DIGITS APPEARING IN THE NATURAL NUMBERS FROM ONE TO ONE MILLION INCLUSIVE
sum = 1.
Add 2, 3, 4, 5, 6, 7, 8 and 9.
sum = 45.
In "10", there's a new digit. Namely zero.
45 + 0 = 45.
Next up is '11'... Hmm. Already included '1'. Skip it.
12. Did those too. Hey, I see a pattern!

The rest, all the way up to a million are just repetitions of the ones we've seen so far.

:-)
Re: Finding sum of all digits from 1 to 1 million.
by vagnerr (Prior) on Jan 24, 2002 at 00:17 UTC
I think you may be right. I don't think the answer you have is correct. There is actualy a formula to calculate the sum of the numbers from 1-n. It is (n^2)/2 + n/2 which in the case of n=1000000 the answer is 500000500000

---If it doesn't fit use a bigger hammer
The formula you need is:- 1/2n (n+1) N is the number. Eg (all numbers from one to ten), ten is number. So 1/2 * 10 =5 * (10+1) =55 Comes from sigma notation.....and i never got any gcses :)
Re: Finding sum of all digits from 1 to 1 million.
by rbc (Curate) on Jan 24, 2002 at 02:11 UTC
use the formul ...
<RB> (n+1)*n/2

Why does this work?
look at this ... 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 is the same as

1 + 10 +
2 + 9 +
3 + 8 +
4 + 7 +
5 + 6
which is the same as
11 + 11 + 11 + 11 + 11
which is 11*5 = (n+1)*n/2 where n = 10
Sorry, but 10 is not a gidit , its a number, composed of the digits 1 and 0.
so your solution should look alike:
0+9
1+8
2+7
3+6
4+5
which is 45
But anyway, I wouldn't be surprised if another one shows up presenting a "correct" solution of "42" grin

Have a nice day
All decision is left to your taste
Re: Finding sum of all digits from 1 to 1 million.
by Anonymous Monk on Jan 25, 2002 at 17:05 UTC
Hi there monks! I think that after mch study of the digits I have come to the conclusion that the sum of the code is...... 27000001. This you think this is incorrect please let me know......PEACE !AND LOVE FELLOW MONKS!!!
Re: Finding sum of all digits from 1 to 1 million.
by pvaldes (Chaplain) on Jan 30, 2013 at 18:55 UTC

find the sum of all decimal digits appearing in the natural numbers from one to one million inclusive

mhhh, I don't get it ... the answer is?:

print "0";

integers don't have decimals

Updated: Forget this, I was not understanding the question, obviously...
Re: Finding sum of all digits from 1 to 1 million.
by flexvault (Monsignor) on Jan 30, 2013 at 19:32 UTC

I confused by the term 'DECIMAL DIGITS'. In the following sequence, I would count the number of decimal digits as:

```   100                sum: 3
101                sum: 6
102                sum: 9
...
In those 3 numbers, we have a total of 9 digits.

So if I use this code:

```perl -E '\$sum=0;for(1..1e6){\$sum+=length(\$_);} say \$sum;'
The result printed as 5888896, which is not 27000001.

So how is the term 'DECIMAL DIGITS' defined? I think that is key to solving for the "real" answer.

Regards...Ed

"Well done is better than well said." - Benjamin Franklin

Create A New User
Node Status?
node history
Node Type: perlquestion [id://141005]
Approved by Corion
help
Chatterbox?
 [choroba]: I mean cheesy [LanX]: lol [ambrus]: no, the chess bishop itself is a joke on real bi-shops [ambrus]: or at least on the stereotype of bi-shops [choroba]: we call chess bishops "archers" [Eily]: choroba sorry, I had to get that off my chess [ambrus]: chess certainly hasn't started those stereotypes, like how kings aren't that powerful but has convinced their whole country to work for them, etc. it's just poured them to a nice clean form that would easily get propagated.

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (13)
As of 2017-09-26 12:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
During the recent solar eclipse, I:

Results (294 votes). Check out past polls.

Notices?