- All Contests
- ProjectEuler+
- Project Euler #248: Numbers for which Euler’s totient function equals 13!
- Discussions

# Project Euler #248: Numbers for which Euler’s totient function equals 13!

# Project Euler #248: Numbers for which Euler’s totient function equals 13!

+ 0 comments My program finds 13!'s divisors 66528 and 93600 (among others) because their successor is a prime and combines them. Sorting those roughly 180000 numbers finishes almost instantly but I went the crazy way and preferred ''std::nth_element'' because it is a little bit more efficient - but you can't measure the performance advantage

+ 0 comments can anyone explain the question?

+ 0 comments To check the cardinality ("checksum") of your sets ϕ

^{-1}(m), consider these resources I used:- Euler totient values up to n=500
- Online Encyclopedia of Integer Sequences (OEIS) for small m: m ≤ 93
- OEIS for large-growth m: m is a factorial up to 28!; note 14! < 10
^{12}is our Python's limit - Hansraj Gupta's Theorem 2 of his 1981 paper: the number v
_{o}of odd members of ϕ^{-1}(2^{k}) is 1 if 0 ≤ k < 32 and 0 for k ≥ 32. Furthermore, that paper includes an explicit list for m=576, as well as a useful table of even-odd checksums for ϕ^{-1}([1,...,m]).

In Python testcases, the limit for time is 20 seconds and memory is 512 megabytes. My

**Python3**code runs under 360 milliseconds; its own prime factorization uses memo-ization.

+ 0 comments from math import factorial

def gcd(p,q): while q != 0: p, q = q, p%q return p def is_coprime(x, y): return gcd(x, y) == 1

c=list(map(int,input().rstrip().split())) d=[] n= factorial(c[0]) b= 1 for i in range(n-1,2,-1): if (is_coprime(n,i)==1): b+=1 break d.append(i)

print(d[len(d)-1])

this code is working for smaller values but with the inputs of the problem it is showing time out please help

+ 0 comments very difficult

No more comments

Sort 5 Discussions, By:

Please Login in order to post a comment