We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #70: Totient permutation
  4. Discussions

Project Euler #70: Totient permutation

Sort by

recency

|

16 Discussions

|

  • fran_mahon
     + 0 comments

    C++ Solution:

    #include <bits/stdc++.h>
using namespace std;

bool IsPermutation(int a, int b)
{    
    int digits[10] = {0};
    
    while(a)
    {
        unsigned int digit_a = a % 10;
        unsigned int digit_b = b % 10;

        digits[digit_a]++;
        digits[digit_b]--;

        a /= 10;
        b /= 10;
    }    
    return (count(digits, digits + 10, 0) == 10);
}

int main() 
{
    vector<int> totient(10000001);
    
    for(int i = 1; i <= 10000000; i++) 
    {
        totient[i] = i;
    }
    for(int i = 2; i <= 10000000; i++)
    {
        if(totient[i] == i)
        {
            for(int j = i*2; j <= 10000000; j += i)
            {
                totient[j] = (totient[j] / i) * (i-1);
            }
        }
    }
    int power = 10;
    double mn = 1e9;
    
    vector<int> nums;
    
    int N;
    cin >> N;
    
    for(int i = 1; i <= 10000000; i++)
    {
        if(i == N)
        {
            cout << nums.back() << "\n";
            return 0;
        }
        
        if(i == power) power *= 10;                
        if(totient[i] < power / 10 || totient[i] >= power) continue;
        if(i == totient[i]) continue;
        
        int num = i;
        int tot = totient[i];                
        
        double ratio = (double)i / (double)tot;                
        
        if(ratio < mn)
        {                              
            if(IsPermutation(num, tot))
            {
                mn = ratio;
                nums.push_back(num);
                
                cerr << i << ": " << tot << " (" << ratio << ")\n";
            }
        }
    }    
    return 0;
}

  • nkosi9976
     + 0 comments

    my code is failing due to optimization problems ,how can i further optimize this code or use a different approach

    def euler_totient(limit):
    phi = [i for i in range(limit + 1)]
    for i in range(2, limit + 1):
        if phi[i] == i:  # i is prime
            for j in range(i, limit + 1, i):
                phi[j] -= phi[j] // i
    return phi

def find_min_ratio(limit):
    phi = euler_totient(limit)
    min_ratio = float('inf')
    min_n = 0
    for n in range(2, limit + 1):
        if sorted(str(n)) == sorted(str(phi[n])):  # Check if n and phi(n) are permutations
            ratio = n / phi[n]
            if ratio < min_ratio:
                min_ratio = ratio
                min_n = n
    return min_n

# Sample input
limit = int(input())
result = find_min_ratio(limit)
print(result)

  • vashanthk662
     + 0 comments

    def sieve_of_eratosthenes(limit): primes = [True] * (limit + 1) primes[0], primes[1] = False, False

    p = 2
while p * p <= limit:
    if primes[p]:
        for i in range(p * p, limit + 1, p):
            primes[i] = False
    p += 1

return [i for i in range(2, limit + 1) if primes[i]]

    def phi(n, primes): result = n for p in primes: if p * p > n: break if n % p == 0: while n % p == 0: n //= p result -= result // p if n > 1: result -= result // n return result

    def is_permutation(a, b): return sorted(str(a)) == sorted(str(b))

    def find_min_ratio(limit): primes = sieve_of_eratosthenes(4000) # Considering primes up to a limit

    min_ratio = float('inf')
min_n = 0

for i in range(len(primes)):
    for j in range(i, len(primes)):
        n = primes[i] * primes[j]
        if n > limit:
            break
        totient = phi(n, primes)
        if is_permutation(n, totient):
            ratio = n / totient
            if ratio < min_ratio:
                min_ratio = ratio
                min_n = n

return min_n

    Taking input

    limit = int(input())

    Finding and printing the answer

    result = find_min_ratio(limit) print( result)

  • vizzy205
     + 0 comments

    This gives me a timeout error on 5 cases. Can anyone help?

    from math import gcd
from itertools import permutations

def totatives(n):
    phi = int(n > 1 and n)
    for p in range(2, int(n ** .5) + 1):
        if not n % p:
            phi -= phi // p
            while not n % p:
                n //= p
    #if n is > 1 it means it is prime
    if n > 1: phi -= phi // n 
    return phi

def permute(num,phi_num):
    temp="".join(sorted(str(num)))
    phi_num="".join(sorted(str(phi_num)))
    return temp==phi_num

N=int(input())
d={}
for n in range(12,N):
    if permute(n,totatives(n)):
        #print(permute,phi(n))
        d[n]=(n/totatives(n))
    
#print(d)
min_b=min(d.values())
for a,b in d.items():
    if b==min_b:
        print(a)
        break

  • kitchent
     + 1 comment

    I am one of those who approach the problem using the property that is minimum when it is prime. And because is never the permutation of prime , so we set our sight on being the product of two primes and . (Hint on counting: )

    For my implementation, I used a prime sieve to generate a list of primes, and feed them to a 2-level for loop afterwards. The point here is the find a balance between reducing the size of prime sieve (otherwise it would be TLE if we make a sieve of size ) and whether we have enough primes to get to the answer. For example, one of the answers is (product of and ), so we need to ensure is included in the prime sieve when is .

    Apart from that, we have one honourable candidate who is an answer, but is not the product of two prime numbers, but three! This is the frustrating Test Case #10. I don't have a strategy yet to handle this other than treating it as a special case.