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:

Hence:

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 10⁴:

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 10¹¹ 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:

Since we know k:

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 10⁸ 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 <= 10^5.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.

Answer 1

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...

Answer 2

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

Answer 3

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.

Answer 4

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 10¹¹. Hence it is possible to find all numbers with two factors by iterating through all primes p below the square root of 10¹¹, 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).

Answer 5

Hi PythonPower,

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!