Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Finding sum of all digits from 1 to 1 million.

by vladb (Vicar)
on Jan 23, 2002 at 23:58 UTC ( [id://141005]=perlquestion: print w/replies, xml ) 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"; }; print"\nAnswer: $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

    Your program has:

    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---
    (the triplet paradiddle with high-hat)
    
      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
    Okay... "all decimal digits." Let's be systematic about this...
    As instructed, start with 1.
    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.

    So the answer is 45.

    :-)
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

    vladb,

    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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://141005]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (3)
As of 2024-03-19 05:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found