Tutorial :Project Euler Problem 245



Question:

I'm onto problem 245 now but have hit some problems. I've done some work on it already but don't feel I've made any real steps towards solving it. Here's what I've got so far:

We need to find n=ab with a and b positive integers. We can also assume gcd(a, b) = 1 without loss of generality and thus phi(n) = phi(ab) = phi(a)phi(b).

We are trying to solve:

\frac{n-\phi(n)}{n-1}=\frac1k

\frac{n-1}{n-\phi(n)}=k

Hence:

n\equiv1\ (\text{mod }n-\phi(n))

At this point I figured it would be a good idea to actually see how these numbers were distributed. I hacked together a brute-force program that I used to find all (composite) solutions up to 104:

15, 85, 255, 259, 391, 589, 1111, 3193, 4171, 4369, 12361, 17473, 21845, 25429, 28243, 47989, 52537, 65535, 65641, 68377, 83767, 91759  

Importantly it looks like there won't be too many less than the 1011 limit the problem asks. The most interesting/ useful bit I discovered was that k was quite small even for the large values of n. In fact the largest k was only 138. (Additionally, it seems k is always even.)

Considering this, I would guess it is possible to consider every value of k and find what value(s) n can be with that value of k.

Returning to the original equation, note that it can be rewritten as:

\frac{\phi(n)-1}{n-1}=\frac{k-1}k

Since we know k:

k\cdot\phi(n)\equiv k\ (\text{mod }n-1)

And that's about as far as I have got; I'm still pursuing some of my routes but I wonder if I'm missing the point! With a brute force approach I have found the sum up to 108 which is 5699973227 (only 237 solutions for n).

I'm pretty much out of ideas; can anyone give away some hints?


Update: A lot of work has been done by many people and together we've been able to prove several things. Here's a list:

n is always odd and k is always even. k <= 105.5. n must be squarefree.

I have found every solution for when n=pq (2 prime factors) with p>q. I used the fact that for 2 primes q = k+factor(k^2-k+1) and p = k+[k^2-k+1]/factor(k^2-k+1). We also know for 2 primes k < q < 2k.

For n with 2 of more prime factors, all of n's primes are greater than k.


Solution:1

Project Euler isn't fond of discussing problems on public forums like StackOverflow. All tasks are made to be done solo, if you encounter problems you may ask help for a specific mathematical or programming concept, but you can't just decide to ask how to solve the problem at hand - takes away the point of project Euler.

Point is to learn and come up with solutions yourself, and learn new concepts.


Solution:2

Let me continue what jug started, but try a somewhat different approach. The goal again is to just find the numbers that have two distinct factors n=pq. As you already pointed out we are looking for the numbers such that n-phi(n) divides n-1. I.e., if n=pq then that means we are looking for p,q such that

  p+q-1 divides pq-1  

Assume we fix p and are looking for all primes q satisfying the equation above. The equation above doesn't look very easy to solve, hence the next step is to eliminate q as much as possible. In particular, we use that if a divides b then a also divides b + ka for any integer k. Hence

  p+q-1 divides pq - 1 - p(p+q-1)  

and simplifying this leads to the condition

  p+q-1 divides p^2 - p + 1.  

We may assume that p is the smaller prime factor of n. Then p is smaller than the square root of 1011. Hence it is possible to find all numbers with two factors by iterating through all primes p below the square root of 1011, then find the divisors of p^2-p+1, solve for q and check if q is prime and pq is a solution of the problem.

This of course, still leaves the integers with more than two prime factors. A somewhat similar approach works here too, but is more involved and needs further optimizations.

One question I can't answer is why is this problem formulated so complicated. Couldn't the authors just have asked for the sum of composite integers where n-phi(n) divides n-1. So maybe I'm missing a big hint there.


Now, that the solutions with two prime factors are known, I'll try to find a potential algorithm for finding solutions with more than 2 prime factors. The goal is to find an algorithm that given a composite integer m finds all primes q such that mq is a solution. I.e., q must be such that

  mq - phi(mq) divides mq - 1.  

Let

  F = mq - phi(mq).  

Then of course

  F = (m-phi(m)) q + phi(m).  

As in the case of two prime factors it is possible to find a condition for F, by eliminating q from the left hand side of the equation above. Since F divides mq-1 it also divides

  (m-phi(m))(mq - 1)   

and hence also

  m F - (m-phi(m))(mq - 1)  = m phi(m) + m - phi(m).  

Thus by finding all the divisors F of m phi(m) + m - phi(m) and by checking if (F - phi(m))/ (m - phi(m)) is prime it is possible to find all solutions mq for a given m. Since only the divisors F that satisfy

 F == phi(m) (mod m - phi(m))  

can lead to new solutions, this fact can somtimes be used to optimze the factorization of m phi(m) + m - phi(m).


Solution:3

Multiply primes. What I did, is first check every 2-prime product; store the ones that are successes. Then using the stored products, check those with more primes (every 3-prime product shown in your brute force has a 2-prime subset that works). Use these stored products, and try again with 4 primes, 5 primes etc.

The only downside is that you need a good sieve or list of primes.

Here is a list of the ones for N<=(10^7):

2 primes 15,85,259,391,589,1111,3193,4171,4369,12361,17473,25429,28243,47989,52537,65641, 68377,83767,91759,100777,120019,144097,186367,268321,286357,291919,316171,327937 ,346063,353029,360301,404797,406867,524851,531721,558013,563767,633727,705667,73 8607,910489,970141,1013539,1080769,1093987,1184233,1185421,1223869,1233823,12618 07,1264693,1455889,1487371,1529641,1574383,1612381,1617379,1657531,1793689,20163 79,2095087,2130871,2214031,2299459,2500681,2553709,2609689,2617963,2763697,30475 21,3146677,3397651,3514603,3539017,3820909,3961219,4078927,4186993,4197901,44997 07,4552411,4935883,4975687,5103841,5299351,5729257,5829877,5864581,6017299,62364 01,6802531,6856609,8759011,9059233,9203377,9301603,9305311,9526747,9536899,95832 79,9782347,9900217 3 primes 255,21845,335923,3817309 4 primes 65535 5 primes 83623935


Solution:4

In order not to give too much away, I'd suggest two things:

  1. Analyze the sequence of numbers you've produced though brute-force: they all share a common characteristic. If you find what it is, you may then have a shot at brute forcing your way to a solution.

  2. Find a more sophisticated factoring algorithm. Or even better: rather than finding the factors from the numbers, build the numbers from the factors...


EDIT: The patterns you wll find will only add to your understading, and hopefully show you how you could have achieved the same amount of knowledge by an adequate manipulation of the analytical expression. Without knowing that pattern, I'm afraid that there is no path to a solution. Plus, this is probably among the hardest Project Euler problems, so you need not worry about finding the solution without a lot of sweat and toil...


Solution:5

no direct help for this problem, but maybe interesting for future math projects: instead of using WolframAlpha to analyze the sequence, I'd recommend "The On-Line Encyclopedia of Integer Sequences" on research.att.com.

Have fun solving all Euler problems!


Solution:6

I haven't found a full solution, but I would like to share my thoughts. Perhaps someone could help.

I believe that one should try to reduce the problem to

O(sqrt(n) http://www.texify.com/img/%5CLARGE%5C%21O%28%5Csqrt%7Bn%7D%29.gif

complexity.The following facts can be used to make the search more effective:

  • Any solution must be an odd number
  • Any solution must be a multiple of distinct primes (no square number factors are allowed)

Others have pointed out about these and it is easy to prove them using only the basic properties of the totient function.

I'll start by analyzing all prime and composite numbers up to sqrt(10^11). This is not a big task and the time required should be well below the 1 minute requirement. All solutions above the square root are of the form:

a*b, where at least one of a,b < sqrt(10^11)  

While iterating the range 0..sqrt(10^11), I will search for multiples of the number in iteration that are solutions. I will only cover the case of multiplying a number below the square root with a single prime. The solution set I will get this way will be a superset of the two-prime factors solution set. It will still not be the complete solution set, as solutions of the form p1*p2*p3, where p1p2,p2p3,p1p3>sqrt(10^11) will not be found.

Let b be the number below the square root and a the prime to multiply it.

b = kb*(b - phi(b)) + mb http://www.texify.com/img/%5CLARGE%5C%21b%20%3D%20k_%7Bb%7D%5Bb%20-%20%5Cphi%28b%29%5D%20%2B%20m_%7Bb%7D.gif

We have:

ab = kb(ab - aphi(b)) + amb http://www.texify.com/img/%5CLARGE%5C%21ab%20%3D%20k_%7Bb%7D%5Bab%20-%20a%5Cphi%28b%29%5D%20%2B%20am_%7Bb%7D.gif

Based on the facts that

phi(a) = a - 1 and phi(a)*phi(b) = phi(a*b) if a, b coprime  

we have

ab = kb(ab - phi(ab)) - kbphi(b) + amb http://www.texify.com/img/%5CLARGE%5C%21ab%20%3D%20k_%7Bb%7D%5Bab%20-%20%5Cphi%28ab%29%5D%20-%20k_%7Bb%7D%5Cphi%28b%29%20%2B%20am_%7Bb%7D.gif

The 'modulo' part on the right can be written as:

m = amb - kbphi(b) = (a-1)mb - (kb-1)b http://www.texify.com/img/%5CLARGE%5C%21m%20%3D%20am_%7Bb%7D%20-%20k_%7Bb%7D%5Cphi%28b%29%20%3D%20%28a-1%29m_%7Bb%7D%20-%20%28k_%7Bb%7D-1%29b.gif

Let me temporarily accept that

0 <= m <= ab - phi(ab) http://www.texify.com/img/%5CLARGE%5C%210%20%5Cleq%20m%20%5Cleq%20ab%20-%20%5Cphi%28ab%29.gif

Then I could solve the above equation for a (m=1), verify that the result is prime and then I will have the only solution that is a multiple of b. If the m is not within the limits to be the actual modulo, then I need to either solve the equation for different values of k:

(k-1)(ab - phi(ab)) <= m <= k(ab - phi(ab)) http://www.texify.com/img/%5CLARGE%5C%21%28k-1%29%28ab%20-%20%5Cphi%28ab%29%29%20%5Cleq%20m%20%5Cleq%20k%28ab%20-%20%5Cphi%28ab%29%29.gif

(k values must be somehow limited) or prove that in that case the will be a higher b < sqrt(10^11) to cover for this.

There is a special case for b prime or b composite and mb = 0. In that case:

m = -(kb - 1)b http://www.texify.com/img/%5CLARGE%5C%21m%20%3D%20-%28k_%7Bb%7D%20-%201%29b.gif

This can be calculated. For b a prime number:

m = -(b-1)b http://www.texify.com/img/%5CLARGE%5C%21m%20%3D%20-%28b%20-%201%29b.gif

I need to find a prime a that satisfies the equation:

k(ab - (a-1)phi(b)) + m = 1, k = 1,2,... http://www.texify.com/img/%5CLARGE%5C%21k%5Bab%20-%20%28a-1%29%5Cphi%28b%29%5D%20%2B%20m%20%20%3D%201%2C%20k%20%3D%201%2C2%2C....gif

For example, let b=3, phi(b)=2.

I need to solve:

k[3a-2(a-1)] - 6 = 1 => k(a + 2) = 5

For k=1, a=7, a prime (solution) For all other values of k, the above equation can't be satisfied.


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »