Problem 066

[thundre]

Yes, the value exceeds 64-bit range, it's a 38-digit number.

Can somebody confirm this, please? I was so sure my code was correct, but the max value it's finding is 30 digits long, and the value for D is not being accepted. Thanks!

The largest minimal x has 39 digits.

[Francky]

Yes, the value exceeds 64-bit range, it's a 38-digit number.

Can somebody confirm this, please? I was so sure my code was correct, but the max value it's finding is 30 digits long, and the value for D is not being accepted. Thanks!

The largest minimal x has 39 digits.

I agree with daniel.is.fisher : 38 digits : 16421... <end snipped>

Edit :
and for other limits:
10³ → 38 digits : 16421... in 7ms
10⁴ → 212 digits : 23551... in 176ms
10⁵ → 724 digits : 91386... in 5s
10⁶ → 2475 digits : 13811... in 163s
(Python3 single thread, on i5-2400)

[thundre]

The largest minimal x has 39 digits.

I agree with daniel.is.fisher : 38 digits : (snip)

That's what I get for y.

I thought the number of digits in x would be more apropos to the problem, since the answer is supposed to be the D for which minimal x is largest, regardless of y.

BTW I think posting the last 10 digits of either x or y is kind of spoiler-ish.

[Francky]

I didn't check x/y, I use P and Q, sorry, but even in this case, I don't get 39 digits.
Here is first ones, and I'll delete them in a few times, not to spoil if it is.
10³ → 36 digits : 63872...
10⁴ → 210 digits : 23611...
10⁵ → 722 digits : 29995...
10⁶ → 2472 digits : 14152...
Edit : last digits snipped.

[Alanbly]

Ok, so I don't want to spoil this problem for anyone, but I also think that the problem is absolutely set up such that you really will have a hard time solving it if you aren't a number theory person and don't research an existing solution. If you research the problem, the solution becomes trivial (well given you've already solved all previous problems). So either bang your head against it for a few hours or read the Wikipedia page on this specific equation and use the methods specified therein and the code you already have and move on.

[brandish]

Don't know where else to write this, but the answer box only accepts 30 digits at the moment. Can this be changed so my hopefully correct answer can get accepted?

[euler]

Quoting from the problem:

Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.

You shouldn't need more than four digits.

[mpiotte]

Don't know where else to write this, but the answer box only accepts 30 digits at the moment. Can this be changed so my hopefully correct answer can get accepted?

... Find the value of D &le; 1000" ...

4 digits should be enough to represent a number not exceeding 1000.

[Montago]

... So ... Why is x=1 and y=0 not a solution for ALL D>0 ??

[mpiotte]

... So ... Why is x=1 and y=0 not a solution for ALL D>0 ??

It is implied from the statement about square D and the examples that we are looking for x and y positive integers.

[vivekchaudhary]

I'm getting different results using Pell’s Equation and brute force!
Pell's equation results in <snip>, but for <snip>, so <snip> should be the answer.

Can someone please cross-verify my results?
Problem 66 [https://projecteuler.net/problem=66]
EDIT by moderator: merged topic and removed spoilers.

[mpiotte]

I'm getting different results using Pell’s Equation and brute force!
Pell's equation results in <snip>, but for <snip>, so <snip> should be the answer.

Can someone please cross-verify my results?
Problem 66 [https://projecteuler.net/problem=66]
EDIT by moderator: merged topic and removed spoilers.

Please don't post results in this forum, and use the existing topic if one already exists.

[Alex-82w4]

Well, if you look up http://en.wikipedia.org/wiki/Diophantine_equation and look at "Examples of Diophantine Equations" it's there, isn't it? (third example).
What it boils down to is that people are supposed to do this bit of research by themselves and find out what it is about.
The meta goal is to get proficient in this kind of web based self learning, based on the information given to you by the problem statement. That's why I still think that people should abstain from giving such extra information in this forum.

For me you don't need to remove your information as this discussion in itself is very instructive imho, telling people what they are supposed to do.

hk, I read your post on Diophantine Equations. The problem 66 is a special case, i.e. Pell's equation.
I can't learn how to find fundamental (first) solution by using

convergents to the regular continued fraction

I created my brute force algorithm in Python. It works for $D\leq7$. When I run it for $D\leq1000$ it calculates only $727$ solutions ($x^2-D*y^2=1$) out of $1000$. What is a good resource to learn about Pell's equations fundamental solutions?

Thanks.

[sjhillier]

hk, I read your post on Diophantine Equations. The problem 66 is a special case, i.e. Pell's equation.

Well that link is already a good start. Some of the links onwards from that page should also help. As a general point, I always find the Wolfram MathWorld pages very useful too. For the Pell Equation in particular, there are plenty of resources around the web, at various levels. It's worth spending a bit of time getting to grips with the Pell Equation and Continued Fractions, as they are often very useful in these types of problems.

[Alex-82w4]

Thank you, sjhillier, for encouraging me to learn.
The problem solved !!