Databases
StackOverflow2013
Postsdbo
POFinding Integers With A Certain Property - Project Euler Problem 221
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFinding Integers With A Certain Property - Project Euler Problem 221
    primarykey
    data
    text
    <p>I've become very addicted to Project Euler recently and am trying to do <a href="http://projecteuler.net/index.php?section=problems&amp;id=221" rel="nofollow noreferrer">this</a> one next! I've started some analysis on it and have reduced the problem down substantially already. Here's my working:</p> <blockquote> <p>A = pqr and</p> <p>1/A = 1/p + 1/q + 1/r so pqr/A = pq + pr + qr</p> <p>And because of the first equation:</p> <p>pq+pr+qr = 1</p> <p>Since exactly two of p, q and r have to be negative, we can simplify the equation down to finding:</p> <p>abc for which ab = ac+bc+1</p> <p>Solving for c we get:</p> <p>ab-1 = (a+b)c</p> <p>c = (ab-1)/(a+b)</p> <hr> <p>This means we need to find a and b for which:</p> <p>ab = 1 (mod a+b)</p> <p>And then our A value with those a and b is:</p> <p>A = abc = ab(ab-1)/(a+b)</p> </blockquote> <p>Sorry if that's a lot of math! But now all we have to deal with is one condition and two equations. Now since I need to find the 150,000th smallest integer written as ab(ab-1)/(a+b) with ab = 1 (mod a+b), ideally I want to search (a, b) for which A is as small as possible.</p> <p>For ease I assumed a &lt; b and I have also noticed that gcd(a, b) = 1.</p> <p>My first implementation is straight forward and even finds 150,000 solutions fast enough. However, it takes far too long to find the 150,000 <em>smallest</em> solutions. Here's the code anyway:</p> <pre><code>n = 150000 seen = set() a = 3 while len(seen) &lt; n: for b in range(2, a): if (a*b)%(a+b) != 1: continue seen.add(a*b*(a*b-1)//(a+b)) print(len(seen), (a, b), a*b*(a*b-1)//(a+b)) a += 1 </code></pre> <p>My next thought was to use Stern-Brocot trees but that is just too slow to find solutions. My final algorithm was to use the Chinese remainder theorem to check if different values of a+b yield solutions. That code is complicated and although faster, it isn't fast enough...</p> <p>So I'm absolutely out of ideas! Anyone got any ideas?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USiCodez
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFinding Integers With A Certain Property - Project Euler Problem 221
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POFinding Integers With A Certain Property - Project Euler Problem 221
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POFinding Integers With A Certain Property - Project Euler Problem 221
      1. USJudge Maygarden
      1. VTFavorite
    1. CO@PythonPower: please see my answer below, which shows how to parameterise A via p and the the divisors of p^2 + 1
      singulars
      1. POFinding Integers With A Certain Property - Project Euler Problem 221
      1. USMitch Wheat
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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