题目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

1. from time import clock
   
2. start = clock()
   
3. 
   
4. def getPrime(n):
   
5.     primes = [True]*n
   
6.     primes[0], primes[1] = False, False
   
7.     for (i, prime) in enumerate(primes):
   
8.         if prime:
   
9.             for j in range(i*i,n,i):
   
10.                 primes[j] = False
    
11.     primelist = []
    
12.     for (k, trueprime) in enumerate(primes):
    
13.         if trueprime:
    
14.             primelist.append(k)
    
15.     return primelist
    
16. 
    
17. def philist(n):
    
18.     primelist = getPrime(n)
    
19.     PHI = [0]*(n+1)
    
20.     PHI[0], PHI[1] = -1, 1
    
21.     for eachprime in primelist:
    
22.         PHI[eachprime] = eachprime - 1
    
23.     for i in range(len(primelist)):
    
24.         p = primelist[i]
    
25.         for k in range(p*p,n+1,p):
    
26.                 PHI[k] = PHI[int(k/p)]*(p-1)
    
27.         for j in range(p*p,n+1,p*p):
    
28.             PHI[j] = PHI[int(j/p)]*p
    
29.     return PHI
    
30. plist = philist(10000000)
    
31. 
    
32. minn, minnphi = 2, 2
    
33. for i in range(2,10000000):
    
34.     if sorted(list(str(i))) == sorted(list(str(plist[i]))):
    
35.         if i/plist[i] < minnphi:
    
36.             minnphi = i/plist[i]
    
37.             minn = i
    
38. print (minn, minnphi)
    
39. 
    
40. end = clock()
    
41. print ('Time:%.3f sec' % (end-start))

复制代码

jerryxjr1220

303963552391
Time:4.211 sec

1. from time import clock
   
2. start = clock()
   
3. 
   
4. def getPrime(n):
   
5.     primes = [True]*n
   
6.     primes[0], primes[1] = False, False
   
7.     for (i, prime) in enumerate(primes):
   
8.         if prime:
   
9.             for j in range(i*i,n,i):
   
10.                 primes[j] = False
    
11.     primelist = []
    
12.     for (k, trueprime) in enumerate(primes):
    
13.         if trueprime:
    
14.             primelist.append(k)
    
15.     return primelist
    
16. 
    
17. def philist(n):
    
18.     primelist = getPrime(n)
    
19.     PHI = [0]*(n+1)
    
20.     for eachprime in primelist:
    
21.         PHI[eachprime] = eachprime - 1
    
22.     for i in range(len(primelist)):
    
23.         p = primelist[i]
    
24.         for k in range(p*p,n+1,p):
    
25.                 PHI[k] = PHI[int(k/p)]*(p-1)
    
26.         for j in range(p*p,n+1,p*p):
    
27.             PHI[j] = PHI[int(j/p)]*p
    
28.     return PHI
    
29. plist = philist(1000000)
    
30. 
    
31. print(sum(plist))
    
32. 
    
33. end = clock()
    
34. print ('Time:%.3f sec' % (end-start))

复制代码

芒果加黄桃

1. # encoding:utf-8
   
2. # 寻找phi(n)为n的排列的数
   
3. from time import time
   
4. def getPrimes(n):
   
5.     primes = [True] * n
   
6.     primes[0], primes[1] = False, False
   
7.     for (i, prime) in enumerate(primes):
   
8.         if prime:
   
9.             for j in range(i * i, n, i):
   
10.                 primes[j] = False
    
11.     return [k for (k, v) in enumerate(primes) if v]
    
12. # 学习jerryxjr1220代码
    
13. def getPhis(N):
    
14.     l_primes = getPrimes(N)
    
15.     l_phis = [0] * (N + 1)
    
16.     for x in l_primes:
    
17.         l_phis[x] = x - 1
    
18.     for p in l_primes:
    
19.         for x in range(p * p, N + 1, p):
    
20.             l_phis[x] = l_phis[int(x / p)] * (p - 1)
    
21.         for y in range(p * p, N + 1, p * p):
    
22.             l_phis[y] = l_phis[int(y / p)] * p
    
23.     return l_phis
    
24. def euler070(N=10000000):
    
25.     l_phis = getPhis(N)
    
26.     minphi, num = 1.1, 0
    
27.     for i in range(2, N + 1):
    
28.         if sorted(list(str(i))) == sorted(list(str(l_phis[i]))):
    
29.             if i / l_phis[i] < minphi:
    
30.                 minphi, num = i / l_phis[i], i
    
31.     print(minphi, num)   
    
32. if __name__ == '__main__':
    
33.     start = time()
    
34.     euler070()
    
35.     print('cost %.6f sec' % (time() - start))

复制代码

1.0007090511248113 8319823
cost 58.685000 sec

fc1735

1. P = []
   
2. L = list(range(10000000))
   
3. for i in range(2, len(L)):
   
4.   if L[i] == i:
   
5.     P.append(i)
   
6.     L[i] = i - 1
   
7.   for p in P:
   
8.     if i * p >= len(L):
   
9.       break
   
10.     if i % p == 0:
    
11.       L[i*p] = L[i] * p
    
12.       break
    
13.     L[i*p] = L[i] * (p - 1)
    
14. 
    
15. 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++实现

1. #include<algorithm>
   
2. #include<iostream>
   
3. #include<vector>
   
4. #include<cmath>
   
5. using namespace std;
   
6. 
   
7. const int M = 1e7;
   
8. 
   
9. int ct = 0;
   
10. bool prime[M+10];
    
11. int factor[M+10];
    
12. int phi[M+10] = {0};
    
13. 
    
14. void euler_sieve(){
    
15.   prime[1] = false;
    
16.   for (int i = 2;i <= M;i++) prime[i] = true;
    
17. 
    
18.   for (int i = 2;i <= M;i++){
    
19.     if (prime[i]) {factor[++ct] = i;  phi[i] = i-1;}
    
20.     for (int j = 1;j <= ct && i*factor[j] < M;j++){
    
21.       prime[i*factor[j]] = false;
    
22.       if (i % factor[j] == 0) break;
    
23.     }
    
24.   }
    
25. }
    
26. 
    
27. void ini(){
    
28.   for (int i = 2;i <= sqrt(M);i++){
    
29.     if (prime[i]){
    
30.       for (int j = i;j*i <= M;j++)
    
31.         if (j % i == 0) phi[j*i] = phi[j] * i;
    
32.         else            phi[j*i] = phi[j] * (i-1);
    
33.     }
    
34.   }
    
35. }
    
36. 
    
37. void parse(vector<int> & v,int x){
    
38.   while(x){
    
39.     v.push_back(x % 10);
    
40.     x /= 10;
    
41.   }
    
42. }
    
43. 
    
44. int main(){
    
45.   euler_sieve();  ini();
    
46.   int ans;
    
47.   double minn = M;
    
48. 
    
49.   for (int n = 2;n < M;n++){
    
50.     vector<int> a,b;
    
51.     double t = n / (double)phi[n];  //cout << t << endl;
    
52. 
    
53.     parse(a,n);   parse(b,phi[n]);
    
54.     sort(a.begin(),a.end());
    
55.     sort(b.begin(),b.end());
    
56. 
    
57.     if (a == b){
    
58.       if (t < minn)  {minn = t; ans = n;}
    
59.     }
    
60.   }
    
61.   cout << ans << endl;
    
62.   return 0;
    
63. }
    

复制代码

永恒的蓝色梦想

C++ 133ms

1. #include<iostream>
   
2. #include<vector>
   
3. #include<limits>
   
4. #include<cstring>
   
5. using namespace std;
   
6. 
   
7. 
   
8. 
   
9. template<size_t size, typename T>
   
10. void euler_sieve(bool(&is_prime)[size], vector<T>& primes, T(&phi)[size]) {
    
11.     T i, k;
    
12.     memset(is_prime, -1, size);
    
13.     is_prime[0] = is_prime[1] = 0;
    
14. 
    
15.     for (i = 2; i < size; i++) {
    
16.         if (is_prime[i]) {
    
17.             primes.push_back(i);
    
18.             phi[i] = i - 1;
    
19.         }
    
20. 
    
21.         for (T j : primes) {
    
22.             k = i * j;
    
23. 
    
24.             if (k >= size) {
    
25.                 break;
    
26.             }
    
27. 
    
28.             is_prime[k] = false;
    
29. 
    
30.             if (!(i % j)) {
    
31.                 phi[k] = phi[i] * j;
    
32.                 break;
    
33.             }
    
34. 
    
35.             phi[k] = phi[i] * (j - 1);
    
36.         }
    
37.     }
    
38. }
    
39. 
    
40. 
    
41. 
    
42. bool is_permutation(unsigned int a, unsigned int b)noexcept {
    
43.     unsigned int t;
    
44.     unsigned char digits[10] = { 0 };
    
45. 
    
46.     while (a) {
    
47.         t = a;
    
48.         a /= 10;
    
49.         digits[t - a * 10]++;
    
50.     }
    
51. 
    
52.     while (b) {
    
53.         t = b;
    
54.         b /= 10;
    
55.         digits[t - b * 10]--;
    
56.     }
    
57. 
    
58.     return !((*(unsigned long long*)(&digits)) | (*(unsigned short*)(&digits[8])));
    
59. }
    
60. 
    
61. 
    
62. 
    
63. int main() {
    
64.     ios::sync_with_stdio(false);
    
65. 
    
66.     constexpr unsigned int UPPER_BOUND = 10000000;
    
67.     static bool is_prime[UPPER_BOUND];
    
68.     static unsigned int phi[UPPER_BOUND];
    
69.     vector<unsigned int> primes;
    
70.     double min_div = numeric_limits<double>::max(), div;
    
71.     unsigned int min_n = 0, n;
    
72. 
    
73.     euler_sieve(is_prime, primes, phi);
    
74. 
    
75. 
    
76.     for (n = 2; n < UPPER_BOUND; n++) {
    
77.         div = (double)n / phi[n];
    
78. 
    
79.         if (div < min_div && is_permutation(n, phi[n])) {
    
80.             min_div = div;
    
81.             min_n = n;
    
82.         }
    
83.     }
    
84. 
    
85. 
    
86.     cout << min_n << endl;
    
87.     return 0;
    
88. }

复制代码