StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POProject Euler Problem 245
text
Body
copied!<p>I'm onto <a href="http://projecteuler.net/index.php?section=problems&id=245" rel="nofollow noreferrer">problem 245</a> 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:</p> <p>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).</p> <p>We are trying to solve:</p> <p><img src="https://chart.apis.google.com/chart?cht=tx&chl=%5Cfrac%7Bn-%5Cphi%28n%29%7D%7Bn-1%7D%3D%5Cfrac1k" alt="\frac{n-\phi(n)}{n-1}=\frac1k"></p> <p><img src="https://chart.apis.google.com/chart?cht=tx&chl=%5Cfrac%7Bn-1%7D%7Bn-%5Cphi%28n%29%7D%3Dk" alt="\frac{n-1}{n-\phi(n)}=k"></p> <p>Hence:</p> <p><img src="https://chart.apis.google.com/chart?cht=tx&chl=n%5Cequiv1%5C%20%28%5Ctext%7Bmod%20%7Dn-%5Cphi%28n%29%29" alt="n\equiv1\ (\text{mod }n-\phi(n))"></p> <p>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<sup>4</sup>:</p> <pre><code>15, 85, 255, 259, 391, 589, 1111, 3193, 4171, 4369, 12361, 17473, 21845, 25429, 28243, 47989, 52537, 65535, 65641, 68377, 83767, 91759 </code></pre> <p>Importantly it looks like there <a href="http://www08.wolframalpha.com/input/?i=15%2C+85%2C+255%2C+259%2C+391%2C+589%2C+1111%2C+3193%2C+4171%2C+4369%2C+12361%2C+17473%2C+21845%2C+25429%2C+28243%2C+47989%2C+52537%2C+65535%2C+65641%2C+68377%2C+83767%2C+91759" rel="nofollow noreferrer">won't be too many</a> less than the 10<sup>11</sup> 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.)</p> <p>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.</p> <p>Returning to the original equation, note that it can be rewritten as:</p> <p><img src="https://chart.apis.google.com/chart?cht=tx&chl=%5Cfrac%7B%5Cphi%28n%29-1%7D%7Bn-1%7D%3D%5Cfrac%7Bk-1%7Dk" alt="\frac{\phi(n)-1}{n-1}=\frac{k-1}k"></p> <p>Since we know k:</p> <p><img src="https://chart.apis.google.com/chart?cht=tx&chl=k%5Ccdot%5Cphi%28n%29%5Cequiv%20k%5C%20%28%5Ctext%7Bmod%20%7Dn-1%29" alt="k\cdot\phi(n)\equiv k\ (\text{mod }n-1)"></p> <p>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<sup>8</sup> which is 5699973227 (only 237 solutions for n).</p> <p>I'm pretty much out of ideas; can anyone give away some hints?</p> <hr> <p><strong>Update</strong>: A lot of work has been done by many people and together we've been able to prove several things. Here's a list:</p> <p>n is always odd and k is always even. k <= 10<sup>5.5</sup>. n must be squarefree.</p> <p>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.</p> <p>For n with 2 of more prime factors, all of n's primes are greater than k.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload