Loading ...
Problem Description
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 < 107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.
Analysis
We can reduce our search significantly by selecting prime pairs (p1, p2 ) and calculate n as n = p1 x p2. This allows the totient to be calculated as
The range of primes was selected by taking the square root of the upper bound, 10,000,000, which is about 3162 and taking ±30% for a range of primes from 2000 to 4000 (247 primes).
Solution
Runs < 1 second in Python.
from Euler import prime_sieve, is_perm, sqrt L = 10**7 primes = prime_sieve(int(1.30*sqrt(L))) del primes[:int(0.6*len(primes))] def pe70(limit): min_q, min_n, i = 2, 0, 0 for p1 in primes: i+=1 for p2 in primes[i:]: if (p1+p2)%9 != 1: continue n = p1 * p2 if n > limit: return min_n phi = (p1-1) * (p2-1) q = n / float(phi) if is_perm(phi, n) and min_q>q: min_q, min_n = q, n return "NFI!" print "Answer to PE70 = ",pe70(L) |
Comments
- The result for 109 was 990326167 < 1 second and 1010 was 9996217801 < 4 seconds.
- The line:
if(p1+p2)%9 != 1: continueis an optimization that observes for two integers to be permutations of one another their difference must be a multiple of 9. - The referenced functions are on the tools page.
I have a question, I am not a math guru, but why and how did you find it to be the square root +-25% for the range of primes, do you have somewhere I can read to see the proof for that. I am just curious, and was baffled with this problem until I found your solution.
Thanks!
Posted by Steven Carnes | May 22, 2009, 10:39 AMThis is a question for Christner to whom I have forwarded your enquiry.
Posted by Mike | May 22, 2009, 2:25 PMThis seems to work fine and we tested it against our (much slower) solution for 10^10 but having to feed it primes is a pain. I would also would like to know more about the 25% thing. It works but not sure why.
Thanks for the great solutions and help with the problems. This is by far the best site I’ve found.
Posted by Tarren | May 25, 2009, 10:14 AMI don’t understand how you know n is necessarily the product of two primes. Can you please explain that to me?
Thanks
Posted by Michael | April 27, 2010, 2:47 AMThis solution was written a long time ago using Perl which can be difficult to follow if you’re not familar with the language.
‘$n’ is the product of two primes because we are using primes read into an array ‘@p’. The list of primes is appended to the end of the program.
The statement:
@p = split /s/,;
reads all the prime numbers into the array at once.
Posted by Mike | April 27, 2010, 10:41 AMYes, I understood that part, but what I was asking was how you limited n to be the product of two primes. Why can’t n have three or more prime factors?
Posted by Michael | April 27, 2010, 10:50 AMThat is because the problem is asking for the minimal ratio:
We have prime pairs (p1, p2 ) and calculate n as n = p1 x p2. Let’s assume n’ is a product of prime tuple (p1, p2, p3). r is ratio of n/φ(n), r’ is ratio of n’/φ(n’). So r/r’ = (p3-1)/p3 which is smaller than 1. r < r', so a composite number n which is a product of two primes will produce the minimal ratio
Posted by Yang Yang | December 30, 2010, 5:25 AMI think Yang Yang explained it best. Thanks for your contribution.
Posted by Mike | December 31, 2010, 12:56 AMHi,
I was slightly confused about the algorithm used here and few questions about it.
1. You have only taken in num as p1*p2 . but the number could be (p1**k1) * (p2 ** k2).
How did you eliminate that they will only be product of two primes not product of higher powers.
2. Also how you came to conclusion about the number of primes to in +- 30% of square_root.
Thanks
Ayushman
P.s:- Thank a lot for posting the algorithm.
Posted by ayushman | June 18, 2012, 12:13 AM@Steven, thanks for your interest and QA for this algorithm. We re-ran it and it worked fine as is. I’m including the full list of primes we used.
Did you have different parameters?
Here’s the full list of primes:
2003 2011 2017 2027 2029 2039 2053 2063 2069 2081 2083 2087 2089 2099 2111 2113 2129 2131 2137 2141 2143 2153 2161 2179 2203 2207 2213 2221 2237 2239 2243 2251 2267 2269 2273 2281 2287 2293 2297 2309 2311 2333 2339 2341 2347 2351 2357 2371 2377 2381 2383 2389 2393 2399 2411 2417 2423 2437 2441 2447 2459 2467 2473 2477 2503 2521 2531 2539 2543 2549 2551 2557 2579 2591 2593 2609 2617 2621 2633 2647 2657 2659 2663 2671 2677 2683 2687 2689 2693 2699 2707 2711 2713 2719 2729 2731 2741 2749 2753 2767 2777 2789 2791 2797 2801 2803 2819 2833 2837 2843 2851 2857 2861 2879 2887 2897 2903 2909 2917 2927 2939 2953 2957 2963 2969 2971 2999 3001 3011 3019 3023 3037 3041 3049 3061 3067 3079 3083 3089 3109 3119 3121 3137 3163 3167 3169 3181 3187 3191 3203 3209 3217 3221 3229 3251 3253 3257 3259 3271 3299 3301 3307 3313 3319 3323 3329 3331 3343 3347 3359 3361 3371 3373 3389 3391 3407 3413 3433 3449 3457 3461 3463 3467 3469 3491 3499 3511 3517 3527 3529 3533 3539 3541 3547 3557 3559 3571 3581 3583 3593 3607 3613 3617 3623 3631 3637 3643 3659 3671 3673 3677 3691 3697 3701 3709 3719 3727 3733 3739 3761 3767 3769 3779 3793 3797 3803 3821 3823 3833 3847 3851 3853 3863 3877 3881 3889 3907 3911 3917 3919 3923 3929 3931 3943 3947 3967 3989
Posted by Mike | May 22, 2009, 2:22 PM