My father and I were writing programs to find numbers that are equal to the sum of the factorial of the digits. For example, 145 = 1! + 4! + 5!. We wrote three programs one in Python, one in Java and one in C++. The ones in Java and C++ ran in about 7.3 seconds while the one in Python ran in about 7 minutes. I was wondering why this is. I've posted the Python and C++ code, I will post the Java code if you desire.

("... " = tab)

Code:
```# build a table of factorials 0! through 9! lastfact = 1 fact = [1] for k in range(1,10): ... lastfact *= k ... fact.append(lastfact) # function to calculate the sum of the factorials of the digits def factsum(n): ... if n==0: ... ... return 1 ... ans = 0 ... while n>0: ... ... u = n % 10 ... ... ans += fact[u] ... ... n -= u ... ... n /= 10 ... return ans # check the numbers up to 100 million for k in xrange(100*1000*1000): ... if k == factsum(k): ... ... print k```

Code:
```#include <iostream> using namespace std; /// Stopping point of our search const long LAST = 100*1000*1000 /// Table of factorials void init_ftable() { ... ftable = new long[10] ... ftable[0] = 1 ... for(int k=1; k<=9; ++k) { ... ... ftable[k] = ftable[k-1] * k; ... } } /// Compute sum of factorials of the digits long fsum(long n) { ... if (n==0) return 1; ... long ans = 0; ... while (n>0) { ... ... int u = n % 10; ... ... ans += ftable[u]; ... ... n -= u; ... ... n /= 10; ... } ... return ans; } int main() { ... init_ftable(); ... for(int n=1; n<=LAST; ++n) { ... ... if (fsum(n) == n) { ... ... ... cout << n << endl; ... ... } ... } }```

So far the numbers we have come up with are: 1, 2, 145, and 40585.
This is how the code looks on my calculator, it might not be optimal but it is 1:30 in the night.
It goes up to 1000 in 8 minutes, so I only found 1,2 and 145

For(X,1,E10
If X=sum(seq(int(10fPart(X10^(Z)))!,Z,-int(log(X))-1,-1
Pause X
End
Igrek wrote:
This is how the code looks on my calculator, it might not be optimal but it is 1:30 in the night.
It goes up to 1000 in 8 minutes, so I only found 1,2 and 145

For(X,1,E10
If X=sum(seq(int(10fPart(X10^(Z)))!,Z,-int(log(X))-1,-1
Pause X
End

I honestly have no idea how that helps the question at all >.>

There is no way that your C++ program ran in 7.3 seconds. My testing shows your C++ code taking about 40-60 seconds on an Athlon64 X2 @ 3ghz.

This just isn't a problem for python. What this problem needs is raw speed with no overhead, which C/C++ does beautifully.

That said, this is what I came up with in python, and is likely to be about as fast as it'll go:

Code:
```import operator try:     import psyco     psyco.full() except:     pass def fact(x):     return reduce(operator.mul, xrange(2, x+1), 1) def findFSums(count):     flist = []     for i in xrange(10):         flist += [fact(i),]     for i in xrange(count):         if i == reduce(lambda x,y: x+flist[int(y)], str(i), 0):             print 'Found:', i     return fsums findFSums(100*1000*1000) ```
We ran the C++ with optimizations, did you do that? Otherwise I'm not sure because it definitely ran that fast. Unless of course I have a really distorted sense of time and my terminal lied to me.

Anyhoo, thanks for the python code! Although we'll probably just stick to C++/Java seeing as they are generally faster (at least in this case). Although I'm gonna ask my brother (a math major) see if he can prove that those are the only four. (My dad's a mathematician but doesn't feel like doing it. ).
Isn't there a math.factorial operator or something, too..?

At any rate, this was awesome, in that it turned me on to psyco. *bookmarks*
Zaphod Beeblebrox wrote:
We ran the C++ with optimizations, did you do that? Otherwise I'm not sure because it definitely ran that fast. Unless of course I have a really distorted sense of time and my terminal lied to me.

It was compiled with Visual C++ 2008 with debugging symbols, but not in debugging mode. I highly doubt that optimizations would drop it to 7.3 seconds, but perhaps.

Quote:
Anyhoo, thanks for the python code! Although we'll probably just stick to C++/Java seeing as they are generally faster (at least in this case).

My pleasure, it was a fun problem to try and optimize. Stick to C/C++ for things like this, its much faster (hell, the JVM/JIT can take up to 15 seconds to start :/ ). Personally I think Java is terrible - try C# (either .NET or Mono, both are very solid)

The Tari wrote:
Isn't there a math.factorial operator or something, too..?

There might be, but it doesn't matter since the factorial's are cached and looked up in an array. I also considered doing a dict lookup (which eliminates the int() conversion), but I didn't feel like doing a speed test of list+int vs. dict
I honestly have nothing better to do right now, and I am interested in parallized python, so I paralized Kllr's code because I can =P

It basically scales linearly. It uses Parallel Python (which I discovered basically runs multiple instances and just communicates between them, so you could run this on a beowulf cluster if you wanted to ) I just chop the work into however many cpu you have (so for 100 million, cpu 1 gets the first 50 and cpu 2 gets the second)
I took out Psyco because it does not really yield any speed improvements at all for this.

Change TTILL = ----- to whatever you want, I just have it at a lower number so I can test it

Code:
```import time import operator import pp print js.get_ncpus(), "cpus" ncpu = input("Number to use:") stime = time.time() js = pp.Server() TTILL = 1000000 #def fact(x): #    return reduce(operator.mul, xrange(2, x+1), 1) def findFSums(low,high):     flist = []     retlist = []     for i in xrange(10):         flist += [reduce(operator.mul, xrange(2, i+1), 1) ,]     for i in xrange(low,high):         if i == reduce(lambda x,y: x+flist[int(y)], str(i), 0):             retlist.append(i)             print 'Found:', i     return retlist x =  TTILL / ncpu cur = 0 jobs = [] for temp in xrange(ncpu):     jobs.append(js.submit(findFSums, (cur+1,cur + x),(),("operator",)))     cur += x for temp in xrange(ncpu):     result = jobs[temp]()     print result #findFSums(100*1000*1000) print "Time: ", time.time() - stime ```

results in:

Code:
```>>> 2 cpus Number to use:1 Found: 1 Found: 2 Found: 145 Found: 40585 [1, 2, 145, 40585] Time:  7.9470000267 >>> 2 cpus Number to use:2 Found: 1 Found: 2 Found: 145 Found: 40585 [1, 2, 145, 40585] [] Time:  4.67499995232 ... 2 cpus Number to use:2 Found: 1 Found: 2 Found: 145 Found: 40585 [1, 2, 145, 40585] [] Time:  45.9029998779 >>> 2 cpus Number to use:1 Found: 1 Found: 2 Found: 145 Found: 40585 [1, 2, 145, 40585] Time:  86.0750000477 >>> ```

Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

»
» All times are UTC - 5 Hours

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum