I'm sorry if this is a newbie question but I'm not sure how to approach it.

I have a problem that I want to solve(by creating an algo) and I'm pretty sure its a Diophantine equation, but I'm not sure how to solve if there's more than a few variables. I created a script that solves for 3 variables(basically by brute force), I'm wondering if there's anything out there to learn better?

(fyi I'm very interested in math and am willing to learn but my math background is weak so sorry if I'm not asking correctly).

  • 1
    $\begingroup$ You probably need to be more specific. Since you don't state what the problem is, and that you only "think" it is a Diophantine equation, you might be wrong. As @user6312 says, solving general Diophantine equations cannot be done algorithmically, but you might be dealing with a particular sort of Diophantine equation that permits a method for finding solutions. $\endgroup$ – Thomas Andrews Jun 4 '11 at 21:33
  • $\begingroup$ thanks for the reply Thomas. I'm not 100% sure because my math background is very weak(since highschool no math and that was over 10 years ago..but its never too late to learn!). I posted this question a few months back math.stackexchange.com/questions/27732/… and now I'm ready to dedicate myself to this 100%. I looked around and many examples were only with 2 or 3 variables..I'm trying to figure out a way to do this with thousands of variables. $\endgroup$ – Lostsoul Jun 5 '11 at 1:45

One can also brute force with $n$ variables. But it is known that there is no general algorithm that will determine whether a Diophantine equation has a solution.

This beautiful and important result solves (in the negative) what is called Hilbert's 10th Problem.

In particular, there is no general algorithm that will determine, in advance, whether a brute force search will terminate.

Of course there are algorithms for particular classes of Diophantine equations, for example (easily) linear ones and (less easily) quadratic ones.

  • 1
    $\begingroup$ Thanks for the answer! I'll look at Hilbert's 10th problem and maybbe try to find a better way to brute force my problem. I can do it with 3 variables, problem is when I apply 3000, I didn't know if a different approach was required(I guess math is totally scalable :-) $\endgroup$ – Lostsoul Jun 5 '11 at 2:55
  • $\begingroup$ @Lostsoul: I looked at the stuff you added to your post, including the link. If things have not changed, you are looking at linear Diophantine equations, for which there is pretty complete theory and good algorithms. So the general undecidability result I replied with would be irrelevant. But interesting! $\endgroup$ – André Nicolas Jun 5 '11 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.