[Exercise] Large sums

Joe · July 3 2012

The following question was asked today as part of a friendly coding competition at Europython.

Find the sum of the digits in the number 1000! (! -> factorial)

Bonus points were awarded for "the shortest one liner possible". Here at the conference, it is somewhat implied that we'd be using Python, but feel free to use your favorite language.

Here's my submission, can anyone do better?

sum([int(x) for x in iter(str(math.factorial(1000)))])

PS: If you don't know how to write one liners, you can still participate in the exercise; it's good practice!

yasamoka · July 3 2012

Again, in AutoIT:

$product = 1
Dim $a
For $a = 1 to 65 Step 1
   $product = $product * $a
Next
Dim $sum
$b = 1
For $b = 1 To StringLen(String($product)) Step 1
   $sum = $sum + Int(StringRight(StringLeft(String($product),$b),1))
Next
MsgBox(0,"SUM",$sum)

Can only get to 65 before address limitation kicks in...

NOTE: AutoIT is very BASIC-like. With a few modifications (or none), you could get this code running in BASIC.

Last edited by yasamoka (July 3 2012)

Zef · July 4 2012

Ruby doesn't have either a built-in methods for sum or factorial, but it's not too bad even without those:

(1..1000).inject(:*).to_s.chars.inject(0) { |sum, char| sum + char.to_i }

The variable names in the last block could be shorter, but kept them long for clarity.

Last edited by Zef (July 4 2012)

geek · July 4 2012

Total[IntegerDigits[1000!]]

xterm · July 4 2012

rahmu wrote:

Here's my submission, can anyone do better?
sum([int(x) for x in iter(str(math.factorial(1000)))])

you can drop the iter() and the [ ], works as a generator expression.

edit: Since you're importing math, you might as well do this

from math import factorial as f

The end result would be

sum(int(x) for x in str(f(1000)))

and an even shorter one

sum(map(int,str(f(1000))))

That's one character longer than geeks!

Last edited by xterm (July 4 2012)

mesa177 · July 4 2012

Matlab:

sum(char(num2str(factorial(1000),'%10.0f'))-48)

Last edited by mesa177 (July 4 2012)

geek · July 4 2012

@mesa177: good luck with fitting that into memory! by the way, it computes a different sum.

mesa177 · July 4 2012

geek wrote:

by the way, it computes a different sum.

you're right, I misread the problem, I'll edit it

NuclearVision · July 4 2012

@xterm
You're right:

from math import factorial 
print sum(map(int,list(str(factorial(1000)))))

I think there's similar problems back at Project Euler
By the way no one posted the solution sum, i think it is 10539.

Last edited by NuclearVision (July 4 2012)

arithma · July 4 2012

What makes a coding competition friendly or not?

NuclearVision · July 4 2012

arithma wrote:

What makes a coding competition friendly or not?

No prizes maybe?

Joe · July 4 2012

@arithma: No real prizes, no real rules, just a bunch of geeks hacking away.

(technically the winner got a Mac Book, but honestly no one really cared about "winning".
As a matter of facts, nobody managed to get all the answers right, and a few of us stayed up late way after the deadline looking for the solutions.

For the curious here's the original post. The page went online at 9pm, which left us with 2h to answer. Feel free to try it, I'd love to discuss the solutions you come up with.

The core of the problem was about computing some large prime numbers. It's prompting me to write a small article about it. I'll update this post once I've published it.

@geek: If you want to try the challenge, avoid using Mathematica.

@NuclearVision: 10539 is correct.

NuclearVision · July 4 2012

My solution for B ( the second problem):

def divlist(n):
    app = []
    for i in xrange(1,n+1):
        if n%i == 0:
            app.append(i)
    return app
def isPrime(n):
    if divlist(n) == [1,n]: #I did not consider 1 as a prime, otherwise i could have added in this line 'or divlist(n)==[1]'
        return True
    else: 
        return False
def find(n):
    app2 = []
    i=0
    while True:
        i+=1
        if isPrime(i)==True:
            app2.append(i)
        if len(app2)==n:
            break
    return app2[n-1]

@rahmu your F counted 54 char, the winner's F counter 55

Last edited by NuclearVision (July 4 2012)

Joe · July 4 2012

@NuclearVision: both my solution and the ones presented by xterm lack the proper imports first. They would not qualify. BTW, the shortest one-liner was found by somebody here after the deadline. It's similar to one of xterm's solution and is 51 character long:

import math;sum(map(int,'%s'%math.factorial(1e3)))

I answered correctly to A and C, made a stupid mistake in B that I corrected a few hours after the competition was over. I cannot believe anyone got the answer to E.

What's the result you get for B?

EDIT: I ran your code. It yields the correct result but took over 11mins on my laptop to compute. Read the article I link to below to see how you can improve your solution.

@everyone: I wrote this small article on what I learned yesterday about calculating primality. I'd love to get some feedback.

NuclearVision · July 6 2012

I was able to improve my code, finding the a-solution prime took like 8 minutes on my netbook(1gbram, 1.6Ghz cpu), if i am not mistaken this prime is 111043.

from time import time as t
def divlist(n):
	app = []
	for k in xrange(1,int((n/2)+1)):
		if n%k==0:
		    app.append(k)
	app.append(n)
	return app
def isPrime(n):
    if divlist(n) == [1,n]: #I did not consider 1 as a prime
        return True
    else: 
        return False
def find(n):
    t1 = t()
    app2 = [2]
    i=1
    while True:
        i+=2
        if isPrime(i)==True:
            app2.append(i)
        if len(app2)==n:
            break
    t2 = t()
    return str(app2[n-1]) +" "+ str(t2-t1)
print find(10539)

What have i done?:
I simplified half calculations in the divlist function, by limiting the divisors search domain between 1,and n/2.
Because a number n have no divisors that are >n/2.
Again I simplified the calculations in find function, by adding 2 instead of one for each loop, in fact there's no two consecutive primes, if we have a prime number n, k=n+1 is not prime it is, no doubt, divisble by 2,
(Between two consecutive numbers, one is even valued), thus it is not necessary to add 1 in each loop.

Last edited by NuclearVision (July 6 2012)

Adnan · April 25 2014

I did a very similar one in Project Euler a while ago.

import functools
import operator

i=1000
li=[]
lii=[]

for n in range(0, 1000):
    li.append(i-n)	

def product(li):
    return functools.reduce(operator.mul, li)
 
for n in str(product(li)):
    lii.append(int(n))
	
print sum(lii)

Feel free to point out my bad habits. Thanks !

Last edited by Adnan (April 25 2014)

NuclearVision · April 25 2014

Hello adnan, why did you use for loop lines 8-9, it is useless, you could do li=range(1,1001) to compute the factorial. Also python has a built in factorial function: math.factorial instead of product(li)
Also instead of importing operator you could use lambda x,y:x*y for mul, lambda comes handy often in python 2.
Also I don't think you need to import reduce (?) at least in python 2. Correct me if wrong.
Cordially.

Adnan · April 25 2014

Well I don't know why I got the beginner's habit of excessive usage of lists and loops, I will have to work that out.

Thanks for pointing out the other self-complications too, sadly I'm not aware of all the available tools in Python. I've came across people using lambda but I still don't understand how to use it, I'll read some docs / tutorials to learn it (and lots of "yield" here and there, not sure what that is yet, but the word is catchy).

Last edited by Adnan (April 25 2014)

NuclearVision · April 25 2014

Range(1,1001)=[1,...,1000] you don't wanna start with 0.
most of python tools are easy to define and use.
I had problems with lambda and yield too when I began with python but good lebgeeks helped me out.
Actually lambda is pretty easy tool in python yet so useful,
Let's say you want to reduce a list while summing its elements you would need to call reduce(function,list)
and you would need to define a function add(x,y): return x+y but this function is not so important. That's why we use lambda on the go to define less important functions inside the reduce function. ex: reduce(lambda x,y: x+y, list) instead of:
def add.... Reduce(add, list).
As for yield I also faced problems with it and got helped here :].
Let's say you want to write a function that detects even numbers from 1 to 20 and adds them to a list:

 def f():
    li=[]
    for i in xrange(1,21): #xrange is range equivalent but it is more compact because it calls its elements only
        if i%2==0:            # when needed and does not store them.
            li.append(i)
    return li

here is an equivalent example using yield function

def f2():
    for i in xrange(1,21):
        if i%2==0:
           yield i

Like you noticed, yield tells the function to initialize a generator object(like a list) and if the condition is fulfilled the yield var will add var to the generator and the function will return the generator after the loop ends, you don't need to tell the function to return the generator.
Generators are objects that can be transformed into lists easily to manipulate them and do things like summing, reducing... Doable to lists as follows : for this example listevennumbers=list(f2())
If you have any problem let me know i'd be more than happy to help :]

Johnaudi · April 27 2014

C#:

long a = 0, r = 0;
for (int i = 1; i < 1001; i++) r = r * i;
for (int i = 0; i < r.ToString().Length; i++) a += r.ToString()[i];

Last edited by Johnaudi (April 27 2014)

NuclearVision · April 27 2014

Johnaudi wrote:

C#:

long a = 0, r = 0;
for (int i = 1; i < 1001; i++) r = r * i;
for (int i = 0; i < r.ToString().Length; i++) a += r.ToString()[i];

r=0 and always will be.
And 1000! Is a big number log10(1000!)=2568 which means it contains over 2560 digits, while long can't handle more than 20bytes.

Joe · April 27 2014

Adnan wrote:

Feel free to point out my bad habits. Thanks !

The biggest issue I have with your code is that i, li and lii are terrible variable names. Unfortunately naming variables is particularly difficult when working on math problems. So try to include a description of what you're trying to do. Currently my favorite way of dealing with this problem is doctest.

As mentioned, your code duplicates existing internal functions available in the standard library. You should use them whenever possible. In your case check out range (or xrange if you're using python 2) and the factorial function of the math module.

However, just as you mention, you're using lists when you shouldn't. A list is expensive and should be avoided when possible. Can you think of a way to rewrite your code without creating these lists?

What's a lambda?

Adnan wrote:

I've came across people using lambda but I still don't understand how to use it, I'll read some docs / tutorials to learn it.

A lambda is a fancy name for a fairly simple concept called anonymous functions. Here's how Python deals with it.

First you have to understand that in Python, a function is an object just like int, str, list, tuple, dict or any other kind of object you came across. So just like any object, it can be assigned to a variable. Look at this:

# Let's define a simple function
def say_hello(name):
    return "Hello " + name

assert say_hello("Adnan") == "Hello Adnan"


# Now let's create a new variable pointing to this function
greet = say_hello

assert greet("Adnan") == "Hello Adnan"

lambda is just an operator that creates a new function without associating it to a variable name (hence the term "anonymous"). Here's how it can be used:

lambda <comma-separated list of arguments>: <value to be returned>

For instance, here's another way to define the say_hello function:

say_hello = lambda name: "Hello " + name
assert say_hello("Adnan") == "Hello Adnan"

Why is this useful and how to use it is a complicated topic; some programmers think that lambdas are themost powerful programming technique, while others believe they're evil and should never be used. On top of this, for better or worse, Python has added some restrictions by design to the lambdas that make them limited. If you're interested in the subject, open a new topic where we can discuss the use of lambdas specifically.

If you want to read more, I wrote a small article a while back that details a good use for lambdas.

What's yield?

Adnan wrote:

(and lots of "yield" here and there, not sure what that is yet, but the word is catchy).

The short answer is that yield is a keyword that allows the creation of generators. So before going further you should note this:

Python generators are an advanced topic. Even programmers with several years of experience might struggle with the concept upon discovering it. So it's normal if you find it a bit difficult to understand at first.

I'm not going to explain how they work, but I'm going to point you to relevant documentation: The most relevant one (just like anything in Python) is the PEP. In our case it's PEP 255: Simple Generators. However I find this PEP in particular a little difficult to read. So I found that this SO question and its answers do a good job at explaining it.

Again, if you have questions, open a new topic and we'll discuss it there :)

Johnaudi · April 27 2014

NuclearVision wrote:

Johnaudi wrote:
C#:
long a = 0, r = 0;
for (int i = 1; i < 1001; i++) r = r * i;
for (int i = 0; i < r.ToString().Length; i++) a += r.ToString()[i];
r=0 and always will be.
And 1000! Is a big number log10(1000!)=2568 which means it contains over 2560 digits, while long can't handle more than 20bytes.

Oh oops! Sorry typo...

I'll edit it.

There:

BigInteger a = 0, r = 1;
for (int i = 1; i < 1001; i++) r *= i;
for (int i = 0; i < r.ToString().Length; i++) a += r.ToString()[i];

Last edited by Johnaudi (April 27 2014)

NuclearVision · April 27 2014

Biginterger is not enough I think.
Still trying to come up with a more clever solution.

Johnaudi · April 27 2014

NuclearVision wrote:

Biginterger is not enough I think.
Still trying to come up with a more clever solution.

Is the answer 133803?

LebGeeks

#1 July 3 2012