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?
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.
Print exactly q lines, each containing a single integer, which is the answer to the corresponding query.
**Sample Input **
2 3 1000000 20 1000000
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?
PS: output is n modulo m for each entry