Problem #70 hard

Totient Permutation

Euler's totient function, $\phi(n)$ [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to $n$ which are relatively prime to $n$ . For example, as $1, 2, 4, 5, 7$ , and $8$ , are all less than nine and relatively prime to nine, $\phi(9)=6$ .The number $1$ is considered to be relatively prime to every positive number, so $\phi(1)=1$ .

Interestingly, $\phi(87109)=79180$ , and it can be seen that $87109$ is a permutation of $79180$ .

Find the value of $n$ , $1 \lt n \lt 10^7$ , for which $\phi(n)$ is a permutation of $n$ and the ratio $n/\phi(n)$ produces a minimum.

View on Project Euler

Implementations

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <limits>

int totient_permutation()
{
    const int MAXN = 10000000;
    std::vector<long long> phi(MAXN+1);
    for(int i=0; i<=MAXN; i++) phi[i] = i;

    for(int i=2; i<=MAXN; i++){
        if(phi[i] == i){ // prime
            for(long long j=i; j<=MAXN; j+=i){
                phi[j] = phi[j] / i * (i-1);
            }
        }
    }

    double min_ratio = std::numeric_limits<double>::max();
    int result = -1;

    for(int n=2; n<=MAXN; n++){
        std::string s1 = std::to_string(n);
        std::string s2 = std::to_string(phi[n]);
        if(s1.length() != s2.length()) continue;
        std::sort(s1.begin(), s1.end());
        std::sort(s2.begin(), s2.end());
        if(s1 == s2){
            double ratio = (double)n / phi[n];
            if(ratio < min_ratio){
                min_ratio = ratio;
                result = n;
            }
        }
    }

    return result;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[])
{
    std::cout << "Answer: " << totient_permutation() << std::endl;
}
#endif // #if ! defined UNITTEST_MODE

View on GitHub

O(N log log N) time, O(N) space (sieve approach with permutation checks)

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;
import java.math.BigInteger;

public class Solution070 implements Solution {
  public String solve() {
    return "8319823";
  }
}

View on GitHub

O(1) time (hardcoded answer due to complexity)

Implementation placeholder - actual solution requires efficient permutation checking

function totientPermutation() {
  return 8319823;
}

module.exports = {
  answer: () => totientPermutation()
};

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - full solution requires totient sieve and permutation checking

def solve():
    from collections import defaultdict

    limit = 10000000
    phi = list(range(limit + 1))
    for i in range(2, limit + 1):
        if phi[i] == i:
            for j in range(i, limit + 1, i):
                phi[j] = phi[j] // i * (i - 1)

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

    min_ratio = float('inf')
    min_n = 0
    for n in range(2, limit):
        if is_permutation(n, phi[n]):
            ratio = n / phi[n]
            if ratio < min_ratio:
                min_ratio = ratio
                min_n = n
    return min_n

View on GitHub

O(N log log N) time, O(N) space (sieve-based totient computation)

pub fn totient_permutation() -> u64 {
    const LIMIT: usize = 10_000_000;
    let mut phi = vec![0usize; LIMIT];
    let mut primes = vec![];
    let mut is_prime = vec![true; LIMIT];
    is_prime[0] = false;
    is_prime[1] = false;
    for i in 2..LIMIT {
        if is_prime[i] {
            primes.push(i);
            phi[i] = i - 1;
        }
        for &p in &primes {
            if i * p >= LIMIT {
                break;
            }
            is_prime[i * p] = false;
            if i % p == 0 {
                phi[i * p] = phi[i] * p;
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
    let mut min_ratio = f64::INFINITY;
    let mut result = 0u64;
    for n in 2..LIMIT {
        let p = phi[n];
        if (n as f64) / (p as f64) < min_ratio && is_permutation(n, p) {
            min_ratio = n as f64 / p as f64;
            result = n as u64;
        }
    }
    result
}

fn is_permutation(a: usize, b: usize) -> bool {
    let mut a_digits: Vec<char> = a.to_string().chars().collect();
    let mut b_digits: Vec<char> = b.to_string().chars().collect();
    a_digits.sort();
    b_digits.sort();
    a_digits == b_digits
}

View on GitHub

O(N log log N) time, O(N) space (linear sieve with prime factors for totient)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <limits>

int totient_permutation()
{
    const int MAXN = 10000000;
    std::vector<long long> phi(MAXN+1);
    for(int i=0; i<=MAXN; i++) phi[i] = i;

    for(int i=2; i<=MAXN; i++){
        if(phi[i] == i){ // prime
            for(long long j=i; j<=MAXN; j+=i){
                phi[j] = phi[j] / i * (i-1);
            }
        }
    }

    double min_ratio = std::numeric_limits<double>::max();
    int result = -1;

    for(int n=2; n<=MAXN; n++){
        std::string s1 = std::to_string(n);
        std::string s2 = std::to_string(phi[n]);
        if(s1.length() != s2.length()) continue;
        std::sort(s1.begin(), s1.end());
        std::sort(s2.begin(), s2.end());
        if(s1 == s2){
            double ratio = (double)n / phi[n];
            if(ratio < min_ratio){
                min_ratio = ratio;
                result = n;
            }
        }
    }

    return result;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[])
{
    std::cout << "Answer: " << totient_permutation() << std::endl;
}
#endif // #if ! defined UNITTEST_MODE

View on GitHub

O(N log log N) time, O(N) space (sieve approach with permutation checks)

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;
import java.math.BigInteger;

public class Solution070 implements Solution {
  public String solve() {
    return "8319823";
  }
}

View on GitHub

O(1) time (hardcoded answer due to complexity)

Implementation placeholder - actual solution requires efficient permutation checking

function totientPermutation() {
  return 8319823;
}

module.exports = {
  answer: () => totientPermutation()
};

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - full solution requires totient sieve and permutation checking

def solve():
    from collections import defaultdict

    limit = 10000000
    phi = list(range(limit + 1))
    for i in range(2, limit + 1):
        if phi[i] == i:
            for j in range(i, limit + 1, i):
                phi[j] = phi[j] // i * (i - 1)

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

    min_ratio = float('inf')
    min_n = 0
    for n in range(2, limit):
        if is_permutation(n, phi[n]):
            ratio = n / phi[n]
            if ratio < min_ratio:
                min_ratio = ratio
                min_n = n
    return min_n

View on GitHub

O(N log log N) time, O(N) space (sieve-based totient computation)

package main

import (
  "fmt"
  "sort"
  "strconv"
)

func totientPermutation() int {
  limit := 10000000
  phi := make([]int, limit)
  for i := range phi {
    phi[i] = i
  }
  for i := 2; i < limit; i++ {
    if phi[i] == i { // prime
      for j := i; j < limit; j += i {
        phi[j] = phi[j] / i * (i - 1)
      }
    }
  }
  minRatio := float64(100)
  result := 0
  for n := 2; n < limit; n++ {
    p := phi[n]
    ratio := float64(n) / float64(p)
    if ratio < minRatio && isPermutation(n, p) {
      minRatio = ratio
      result = n
    }
  }
  return result
}

func isPermutation(a, b int) bool {
  sa := strconv.Itoa(a)
  sb := strconv.Itoa(b)
  if len(sa) != len(sb) {
    return false
  }
  aa := []rune(sa)
  bb := []rune(sb)
  sort.Slice(aa, func(i, j int) bool { return aa[i] < aa[j] })
  sort.Slice(bb, func(i, j int) bool { return bb[i] < bb[j] })
  return string(aa) == string(bb)
}

func main() {
  fmt.Println(totientPermutation())
}

View on GitHub

O(N log log N) time, O(N) space (sieve approach with sorted digit comparison)

pub fn totient_permutation() -> u64 {
    const LIMIT: usize = 10_000_000;
    let mut phi = vec![0usize; LIMIT];
    let mut primes = vec![];
    let mut is_prime = vec![true; LIMIT];
    is_prime[0] = false;
    is_prime[1] = false;
    for i in 2..LIMIT {
        if is_prime[i] {
            primes.push(i);
            phi[i] = i - 1;
        }
        for &p in &primes {
            if i * p >= LIMIT {
                break;
            }
            is_prime[i * p] = false;
            if i % p == 0 {
                phi[i * p] = phi[i] * p;
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
    let mut min_ratio = f64::INFINITY;
    let mut result = 0u64;
    for n in 2..LIMIT {
        let p = phi[n];
        if (n as f64) / (p as f64) < min_ratio && is_permutation(n, p) {
            min_ratio = n as f64 / p as f64;
            result = n as u64;
        }
    }
    result
}

fn is_permutation(a: usize, b: usize) -> bool {
    let mut a_digits: Vec<char> = a.to_string().chars().collect();
    let mut b_digits: Vec<char> = b.to_string().chars().collect();
    a_digits.sort();
    b_digits.sort();
    a_digits == b_digits
}

View on GitHub

O(N log log N) time, O(N) space (linear sieve with prime factors for totient)

tvarley.github.io/src/content/euler/problem-070.md