Problem 066

[kvom]

My program finds a solution for each value of D from 1-1000 and reports the largest. However the value of D I get is not accepted as correct. Since the value of X my algorithm computes agrees with the sample values given in the problem description, I'm at a loss to proceed further.

FWIW, the maximum value of X that I computed was 2178548422

[ed_r]

> FWIW, the maximum value of X that I computed was 2178548422

Do all of your 'X' values look like they're less than 2³² (typical int size) or might there be a trend for them growing (as D increases) to something much, much bigger ...?

[kvom]

After thinking about this some more, I loaded my program's reported results into an Excel spreadsheet and tried validate that values of X. I found that my sqrt routine was off in cases of very large Dy^2 values. I have rewritten it somewhat, and am retrying on only the values of D where Excel showed a variation (about 60 cases). Unfortunately it seems to take over 30 minutes to retest each of these cases. I'm guessing it will be faster to try inputting each of the 60 values of D into the website

[elr]

i suspect i have some kind of overflow problem with this too

i'm able to produce the values which showed at the problem page

my program find that the maximal value of x from the minimal solutions is 17068346512338472993
but the matched D value does not accepted...

does the value of x or y goes above 2^64 ?
or better to ask does x^2/y^2 goes above 2^64...

[daniel.is.fischer]

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

[elr]

thanks i've solved it

[flk]

Hi, sorry if this post is out of line since the answer thread is locked, but I felt I had to vent my relief/frustration somewhere! This problem took me an insane amount of time - I feel like it should have a warning! (although yes, I have only solved 55 problems so far, I'm sure there are harder ones later?).

First I tried using normal methods without doing research, as I feel that is cheating. However, after it became clear these methods would not work, I began researching, and from what I can tell, there is no way to do this problem without knowing some in-depth number theory. Even after knowing the correct algorithm, I had numerical issues and ended up having to using a combination of languages to solve it :O

In short, this is a bastard of a problem - perhaps problems which require some level of knowledge such as this should be marked accordingly to prevent wasted time?

Anyway, it's quite enjoyable to have it behind me! Phew!

/rant off



(hopefully this post does not count as a spoiler)

[koolk]

Hi, sorry if this post is out of line since the answer thread is locked, but I felt I had to vent my relief/frustration somewhere! This problem took me an insane amount of time - I feel like it should have a warning! (although yes, I have only solved 55 problems so far, I'm sure there are harder ones later?).

I did a quick research on wikipedia, and there was enough information there. I solved it in a (kinda) simple way, with C++.

[flk]

Perhaps this just hinged on my misconception that the problems are solvable without additional research, and that such research is 'cheating'. I guess I will change my views accordingly!

[koolk]

I try to solve problems without any research first. But If I see that it requires knowledge that I lack, I do a research (And sometimes it is impossible to solve the problem without that knowledge). In this case it was easy to solve the problem with a quick research because you know what to search, but most of the time the research is just a small part in the process of solving the problem.

[djjeck]

I try to solve problems without any research first.

Be careful when you try to skip research: you might end up bruteforcing problems that might have a beautiful, elegant and faster solution, losing an opportunity to learn something!

(I do that too, btw)

[thedoctar]

FINALLY FINISHED THIS!!!!!! 0.5 seconds!!!!

Just a warning to anyone to attempt this question:
RESEARCH FIRST!

Wikipedia has good info and Wolfram Mathworld. Also, $x^2 - Dy^2=1$ are also known as:

Expand

Pell's equation

.

[Francky]

10ms in python (without pypy).
--
@thedoctar : Be carefull, it was a hint that you gave,
you could remove it.

[thedoctar]

10ms in python (without pypy).
--
@thedoctar : Be carefull, it was a hint that you gave,
you could remove it.

Nice on the score. Fast as usual.I also dind't use pypy, and under a second.

Might be a hit, but the big red box states dont' post spoilers and I don't believe it's a spoiler. I'll put it as hidden text. Another name for the equation does not explicitly give away the problem.

[hk]

@thedoctar:
The problem statement talks about "Diophantine equation".
If you start to investigate that subject using Google you will inevitably encounter the term you are mentioning and will see that it fits the problem.
So there is no need to mention it at all.

[thedoctar]

But it's a lot faster to research if you know the name of the type of Diophantine equation. Diophantine equations are more broader, aren't they? The only reason I knew they were called Pell's equation was because I remember them because of a maths enrichment book I had mentioned them.

[hk]

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.

[Slaunger]

I think posting the name of this class of equations is a spoiler, and that figuring that out is big part of the work involved in solving this particular problem. However, now that several users have mentioned the name explicitly, it is sort of out in the open, unfortunately

[hk]

Actually I'm not so sure about that figuring out the name of the class is the biggest part of the problem.
I think that figuring out how to solve this class of problem isn't something most people can do on their own.
While it is years ago that I solved this problem (and several other problems using the same class of equation) I can't say that I know by heart how to do it. I always have to look that up again.

[Perlkonig]

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!