Optimizing Totient function

Question

I'm trying to maximize the Euler Totient function on Python given it can use large arbitrary numbers. The problem is that the program gets killed after some time so it doesn't reach the desired ratio. I have thought of increasing the starting number into a larger number, but I don't think it's prudent to do so. I'm trying to get a number when divided by the totient gets higher than 10. Essentially I'm trying to find a sparsely totient number that fits this criteria.

Here's my phi function:

def phi(n):
    amount = 0

    for k in range(1, n + 1):
        if fractions.gcd(n, k) == 1:
            amount += 1

    return amount

Answer 1

The most likely candidates for high ratios of N/phi(N) are products of prime numbers. If you're just looking for one number with a ratio > 10, then you can generate primes and only check the product of primes up to the point where you get the desired ratio

def totientRatio(maxN,ratio=10):
    primes    = []
    primeProd = 1
    isPrime   = [1]*(maxN+1)
    p         = 2
    while p*p<=maxN:
        if isPrime[p]:
            isPrime[p*p::p] = [0]*len(range(p*p,maxN+1,p))
            primes.append(p)
            primeProd *= p
            tot = primeProd
            for f in primes:
                tot -= tot//f
            if primeProd/tot >= ratio:
                return primeProd,primeProd/tot,len(primes)
        p += 1 + (p&1)

output:

totientRatio(10**6)
16516447045902521732188973253623425320896207954043566485360902980990824644545340710198976591011245999110, 
10.00371973209101, 
55

This gives you the smallest number with that ratio. Multiples of that number will have the same ratio.

n = 16516447045902521732188973253623425320896207954043566485360902980990824644545340710198976591011245999110

n*2/totient(n*2) = 10.00371973209101

n*11*13/totient(n*11*13) = 10.00371973209101

No number will have a higher ratio until you reach the next product of primes (i.e. that number multiplied by the next prime).

n*263/totient(n*263) = 10.041901868473037

Removing a prime from the product affects the ratio by a proportion of (1-1/P).
For example if m = n/109, then m/phi(m) = n/phi(n) * (1-1/109)

(n//109) / totient(n//109)    = 9.91194248684247

10.00371973209101 * (1-1/109) = 9.91194248684247

This should allow you to navigate the ratios efficiently and find the numbers that meed your need.

For example, to get a number with a ratio that is >= 10 but closer to 10, you can go to the next prime product(s) and remove one or more of the smaller primes to reduce the ratio. This can be done using combinations (from itertools) and will allow you to find very specific ratios:

m = n*263/241

m/totient(m) = 10.000234225865265

m = n*(263...839) / (7 * 61 * 109 * 137)  # 839 is 146th prime 

m/totient(m) = 10.000000079805726

Answer 2

I have a partial solution for you, but the results don't look good.. (this solution may not give you an answer with modern computer hardware (amount of ram is limiting currently)) I took an answer from this pcg challenge and modified it to spit out ratios of n/phi(n) up to a particular n

import numba as nb
import numpy as np
import time

n = int(2**31)

@nb.njit("i4[:](i4[:])", locals=dict(
    n=nb.int32, i=nb.int32, j=nb.int32, q=nb.int32, f=nb.int32))

def summarum(phi):
    #calculate phi(i) for i: 1 - n
    #taken from <a>https://codegolf.stackexchange.com/a/26753/42652</a>
    phi[1] = 1
    i = 2
    while i < n:
        if phi[i] == 0:
            phi[i] = i - 1
            j = 2
            while j * i < n:
                if phi[j] != 0:
                    q = j
                    f = i - 1
                    while q % i == 0:
                        f *= i
                        q //= i
                    phi[i * j] = f * phi[q]
                j += 1
        i += 1
    #divide each by n to get ratio n/phi(n)
    i = 1
    while i < n: #jit compiled while loop is faster than: for i in range(): blah blah blah
        phi[i] = i//phi[i]
        i += 1
    return phi

if __name__ == "__main__":
    s1 = time.time()
    a = summarum(np.zeros(n, np.int32))
    locations = np.where(a >= 10)
    print(len(locations))

I only have enough ram on my work comp. to test about 0 < n < 10^8 and the largest ratio was about 6. You may or may not have any luck going up to larger n, although 10^8 already took several seconds (not sure what the overhead was... spyder's been acting strange lately)

Answer 3

p₅₅# is a sparsely totient number satisfying the desired condition.

Furthermore, all subsequent primorial numbers are as well, because p_n# / phi(p_n#) is a strictly increasing sequence:

p₁# / phi(p₁#) is 2, which is positive. For n > 1, p_n# / phi(p_n#) is equal to p_n-1#p_n / phi(p_n-1#p_n), which, since p_n and p_n-1# are coprime, is equal to (p_n-1# / phi(p_n-1#)) * (p_n/phi(p_n)). We know p_n > phi(p_n) > 0 for all n, so p_n/phi(p_n) > 1. So we have that the sequence p_n# / phi(p_n#) is strictly increasing.

I do not believe these to be the only sparsely totient numbers satisfying your request, but I don't have an efficient way of generating the others coming to mind. Generating primorials, by comparison, amounts to generating the first n primes and multiplying the list together (whether by using functools.reduce(), math.prod() in 3.8+, or ye old for loop).

As for the general question of writing a phi(n) function, I would probably first find the prime factors of n, then use Euler's product formula for phi(n). As an aside, make sure to NOT use floating-point division. Even finding the prime factors of n by trial division should outperform computing gcd n times, but when working with large n, replacing this with an efficient prime factorization algorithm will pay dividends. Unless you want a good cross to die on, don't write your own. There's one in sympy that I'm aware of, and given the ubiquity of the problem, probably plenty of others around. Time as needed.

Speaking of timing, if this is still relevant enough to you (or a future reader) to want to time... definitely throw the previous answer in the mix as well.