We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

# Project Euler #100: Arranged probability

# Project Euler #100: Arranged probability

#### Sort by

recency

#### |

#### 10 Discussions

#### |

Please Login in order to post a comment

Gotta say, it's been about two weeks working on this one, burning my brain. I took a lot of wrong turns and learned a lot about modular arithmetic and number theory.

To anyone stumped, Dario Alpern's site is

indispensable.The calculator page and the method page explain much of what you need to implement. Then, also brushing up and understanding how to solve quadratic congruences. And definitely build yourself some testing suites to make sure you are getting the right answers! Good luck!Understanding why this statement is

falseis crucial to solving some of the test cases: "Q as a perfect square should result in No solution." The same applies to PQ.I passed test cases 0, 3, 4, 6, 15, but failed to pass the other cases. I am not sure what else to do.

Would you be able to provide any other test cases or any clues?

Thank you very much in advance.

why this can't be solved using binary search

Does anyone knows whether Brahmagupta's composition is applicable here or not? I'm stuck with not being able to generate

`85 120`

from`3 4`

and`15 21`

.Even completing squares to arrive at Pell's equation with integer is troublesome with like

`3 8`

. No clue yet.EDIT: It gets frustrating. This time I follow the continued fraction approach. The trouble is still at the very beginning. While now I know that as a perfect square should result in`No solution`

, I could not get the Pell's Equation in its appropriate form. The one I've got is , where . So now it is . But when I plug in with and for the case and , those and are not integers. The fact is that, I couldn't even get the fundamental solutions for and right.Is it possible that there are multiple valid Pell's Equations for one input? But then there would be infinitely many such equations as I could just modify the corresponding . This idea sounds horrifying. And when

`sqrt`

is involved, answers like`181489708628619 296371453137673`

is found for`3 8 1000`

, which is obviously wrong.Also, there is the issue with

`OverflowError: long int too large to convert to float`

for Test Case #11, #16 and #17, when I tried to perform`y * sqrt(k) + 1`

.Trying to implement something like the Generic two integer variable equation solver is too overwhelming.

EDIT 2: Just found this, this, this, and this. That's a lot of reading ahead of me.