题目70：考察φ(n)是n的一个排列的n值

欧拉计划

Totient permutation

Euler's Totient function, φ(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, φ(9)=6.

The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

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

Find the value of n, 1 < n < , for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

题目：

欧拉函数 φ(n)（有时也叫做phi函数）可以用来计算小于等于 n 的数字中与 n 互质的数字的个数。例如，因为 1,2,4,5,7,8 全部小于 9 并且与 9 互质，所以φ(9)=6。

数字1被认为与每个正整数互质，所以 φ(1)=1。

有趣的是，φ(87109)=79180，可以看出 87109 是 79180 的一个排列。

对于 1 < n < ，并且 φ(n) 是 n 的一个排列的那些 n 中，使得 n/φ(n) 取到最小的 n 是多少？

jerryxjr1220

有了第69题的算法程序，这题就是送分题了把

jerryxjr1220

这题唯一的问题是上限提升了10倍，到10的7次方，所以花的时间就多了好多，好在还能算……
8319823 1.0007090511248113
Time:133.215 sec

from time import clock
start = clock()

def getPrime(n):
    primes = [True]*n
    primes[0], primes[1] = False, False
    for (i, prime) in enumerate(primes):
        if prime:
            for j in range(i*i,n,i):
                primes[j] = False
    primelist = []
    for (k, trueprime) in enumerate(primes):
        if trueprime:
            primelist.append(k)
    return primelist

def philist(n):
    primelist = getPrime(n)
    PHI = [0]*(n+1)
    PHI[0], PHI[1] = -1, 1
    for eachprime in primelist:
        PHI[eachprime] = eachprime - 1
    for i in range(len(primelist)):
        p = primelist[i]
        for k in range(p*p,n+1,p):
                PHI[k] = PHI[int(k/p)]*(p-1)
        for j in range(p*p,n+1,p*p):
            PHI[j] = PHI[int(j/p)]*p
    return PHI
plist = philist(10000000)

minn, minnphi = 2, 2
for i in range(2,10000000):
    if sorted(list(str(i))) == sorted(list(str(plist[i]))):
        if i/plist[i] < minnphi:
            minnphi = i/plist[i]
            minn = i
print (minn, minnphi)

end = clock()
print ('Time:%.3f sec' % (end-start))

jerryxjr1220

303963552391
Time:4.211 sec

from time import clock
start = clock()

def getPrime(n):
    primes = [True]*n
    primes[0], primes[1] = False, False
    for (i, prime) in enumerate(primes):
        if prime:
            for j in range(i*i,n,i):
                primes[j] = False
    primelist = []
    for (k, trueprime) in enumerate(primes):
        if trueprime:
            primelist.append(k)
    return primelist

def philist(n):
    primelist = getPrime(n)
    PHI = [0]*(n+1)
    for eachprime in primelist:
        PHI[eachprime] = eachprime - 1
    for i in range(len(primelist)):
        p = primelist[i]
        for k in range(p*p,n+1,p):
                PHI[k] = PHI[int(k/p)]*(p-1)
        for j in range(p*p,n+1,p*p):
            PHI[j] = PHI[int(j/p)]*p
    return PHI
plist = philist(1000000)

print(sum(plist))

end = clock()
print ('Time:%.3f sec' % (end-start))

芒果加黄桃

# encoding:utf-8
# 寻找phi(n)为n的排列的数
from time import time
def getPrimes(n):
    primes = [True] * n
    primes[0], primes[1] = False, False
    for (i, prime) in enumerate(primes):
        if prime:
            for j in range(i * i, n, i): 
                primes[j] = False
    return [k for (k, v) in enumerate(primes) if v]
# 学习jerryxjr1220代码 
def getPhis(N):
    l_primes = getPrimes(N)
    l_phis = [0] * (N + 1)
    for x in l_primes:
        l_phis[x] = x - 1
    for p in l_primes:
        for x in range(p * p, N + 1, p):
            l_phis[x] = l_phis[int(x / p)] * (p - 1)
        for y in range(p * p, N + 1, p * p):
            l_phis[y] = l_phis[int(y / p)] * p
    return l_phis
def euler070(N=10000000):
    l_phis = getPhis(N)
    minphi, num = 1.1, 0
    for i in range(2, N + 1):
        if sorted(list(str(i))) == sorted(list(str(l_phis[i]))):
            if i / l_phis[i] < minphi:
                minphi, num = i / l_phis[i], i
    print(minphi, num)    
if __name__ == '__main__':
    start = time() 
    euler070()
    print('cost %.6f sec' % (time() - start))

1.0007090511248113 8319823
cost 58.685000 sec

fc1735

P = []
L = list(range(10000000))
for i in range(2, len(L)):
  if L[i] == i:
    P.append(i)
    L[i] = i - 1
  for p in P:
    if i * p >= len(L):
      break
    if i % p == 0:
      L[i*p] = L[i] * p
      break
    L[i*p] = L[i] * (p - 1)

print(min(map(lambda x: [x[0] / x[1], x[0]], filter(lambda x: sorted(str(x[0])) == sorted(str(x[1])), list(enumerate(L))[2:])))[1])

https://github.com/devinizz/project_euler/blob/master/page02/70.py

debuggerzh

8319823

Process returned 0 (0x0)   execution time : 32.889 s
Press any key to continue.
思路相同的c++实现

#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

const int M = 1e7;

int ct = 0;
bool prime[M+10];
int factor[M+10];
int phi[M+10] = {0};

void euler_sieve(){
  prime[1] = false;
  for (int i = 2;i <= M;i++) prime[i] = true;

  for (int i = 2;i <= M;i++){
    if (prime[i]) {factor[++ct] = i;  phi[i] = i-1;}
    for (int j = 1;j <= ct && i*factor[j] < M;j++){
      prime[i*factor[j]] = false;
      if (i % factor[j] == 0) break;
    }
  }
}

void ini(){
  for (int i = 2;i <= sqrt(M);i++){
    if (prime[i]){
      for (int j = i;j*i <= M;j++)
        if (j % i == 0) phi[j*i] = phi[j] * i;
        else            phi[j*i] = phi[j] * (i-1);
    }
  }
}

void parse(vector<int> & v,int x){
  while(x){
    v.push_back(x % 10);
    x /= 10;
  }
}

int main(){
  euler_sieve();  ini();
  int ans;
  double minn = M;

  for (int n = 2;n < M;n++){
    vector<int> a,b;
    double t = n / (double)phi[n];  //cout << t << endl;

    parse(a,n);   parse(b,phi[n]);
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());

    if (a == b){
      if (t < minn)  {minn = t; ans = n;}
    }
  }
  cout << ans << endl;
  return 0;
}

永恒的蓝色梦想

C++ 133ms

#include<iostream>
#include<vector>
#include<limits>
#include<cstring>
using namespace std;



template<size_t size, typename T>
void euler_sieve(bool(&is_prime)[size], vector<T>& primes, T(&phi)[size]) {
    T i, k;
    memset(is_prime, -1, size);
    is_prime[0] = is_prime[1] = 0;

    for (i = 2; i < size; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }

        for (T j : primes) {
            k = i * j;

            if (k >= size) {
                break;
            }

            is_prime[k] = false;

            if (!(i % j)) {
                phi[k] = phi[i] * j;
                break;
            }

            phi[k] = phi[i] * (j - 1);
        }
    }
}



bool is_permutation(unsigned int a, unsigned int b)noexcept {
    unsigned int t;
    unsigned char digits[10] = { 0 };

    while (a) {
        t = a;
        a /= 10;
        digits[t - a * 10]++;
    }

    while (b) {
        t = b;
        b /= 10;
        digits[t - b * 10]--;
    }

    return !((*(unsigned long long*)(&digits)) | (*(unsigned short*)(&digits[8])));
}



int main() {
    ios::sync_with_stdio(false);

    constexpr unsigned int UPPER_BOUND = 10000000;
    static bool is_prime[UPPER_BOUND];
    static unsigned int phi[UPPER_BOUND];
    vector<unsigned int> primes;
    double min_div = numeric_limits<double>::max(), div;
    unsigned int min_n = 0, n;

    euler_sieve(is_prime, primes, phi);


    for (n = 2; n < UPPER_BOUND; n++) {
        div = (double)n / phi[n];

        if (div < min_div && is_permutation(n, phi[n])) {
            min_div = div;
            min_n = n;
        }
    }


    cout << min_n << endl;
    return 0;
}