Euler Project: Sums of Digit Factorials

Question

MY CODE:

import time
import math
import sys
def sums(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r
def f(n):
    r=0
    s1=0
    while n:
        r, n =  n % 10, n // 10
        s1=s1+math.factorial(int(r))
    return s1

def sf(n):
    return sums(f(n))

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        p=p+1

def sg(i):
    return sums(g(i))

def ssg(n):
    s=0
    for i in range(1,n+1):
        s=s+sg(i)
    return s

q=int(sys.stdin.readline())
out=[]
for i in range(q):
    n1,m1=(sys.stdin.readline()).split()
    n=int(n1)
    m=int(m1)
    v=ssg(n)
    out.append(v%m)
for i in out:
    print(i)

This code was made for Euler Project 254:

Define f(n) as the sum of the factorials of the digits of n. For example, f(342) = 3! + 4! + 2! = 32.

Define sf(n) as the sum of the digits of f(n). So sf(342) = 3 + 2 = 5.

Define g(i) to be the smallest positive integer n such that sf(n) = i. Though sf(342) is 5, sf(25) is also 5, and it can be verified that g(5) is 25.

Define sg(i) as the sum of the digits of g(i). So sg(5) = 2 + 5 = 7.

Further, it can be verified that g (20) is 267 and ∑ sg(i) for 1 ≤ i ≤ 20 is 156.

What is ∑ sg(i) for 1 ≤ i ≤ 150?

Input Format

The first line of each test file contains a single integer q, which is the number of queries per test file. lines follow, each containing two integers separated by a single space: n and m of the corresponding query.

Output Format

Print exactly q lines, each containing a single integer, which is the answer to the corresponding query.

**Sample Input **

2
3 1000000
20 1000000

Sample Output

8
156

MY PROBLEM

This code is not fast enough for all their test cases so, my code was rejected as answer. (They did not specify which test cases they are testing on it.)

So, how efficiency of this code could be increased?

Thanks

PS: output is n modulo m for each entry

Answer 1

First of all, why do you answer multi queries? The problem asks only to find the summation of sg from 1 to 150.

The real bottleneck in your solution is this function:

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        p=p+1

its growth rate is very big and the loop is unbounded. If you tried to bound it to 100 for example you will find it becomes too fast.

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        if p == 100:
            break
        p=p+1

This function will not give us the right answer for sure but it tells us that this function is the bottleneck and make the code too slow.

The real problem is how to calculate g(i) fast. I will give you some ideas and hints:

g(n) is the sum of digits that give us n and form the minimum possible number and at the same time can be represented in the form of $$A1!+A2!+..+Ax!$$ for example: (5 = 1 + 2 + 2) -> ( 122 = 120 + 2 ) -> ( 5! = 120 and 2! = 2 ) so ( 2! + 5! ) gives us 5 i.e. g(5) = 25

and as f(n) calculates the factorial of each digit so we have factorial of digits from 1 to 9 only.

If we calculated the different combinations of sums of factorial digits from 1 to 9 (I think we can make something faster but this is just a start and you can find some algorithm to follow instead of trying all the combinations which will also be too slow) and store the minimum of them (i.e. the minimum number they can form by adding them) in an array for each digit from 1 to 150. then we will loop throw the array from 1 to 150 and sum .. this will be too fast.

I think this is enough to start going and invest some effort in this path.

I already solved this problem 2 years before. But I will NEVER share the solution and I ask everyone not to share the solutions of projecteuler problems because this is against the conditions of the website. If you can't solve it. You should give it some time or learn some needed topics but never ask anyone for the solution. at most, you can take some hints to help you work on the problems.

This moment really worth and by taking other people solution you will lose this moment

Answer 2

The obvious change that would improve the performance would be to accumulate modulo m, rather than to accumulate at full precision and only then find the remainder.