Thanks Aaron for your reply. I am proposing this as a GSoC project. Sorry, I didn't mention it earlier. However, even if this is not accepted as a GSoC project, I would like to work on this.
The two n's are different. I should have used distinct letters instead of the n's. Sorry for the confusion. I have assumed that all ai's are nonzero and the above linear Diophantine equation (DE) satisfies the condition for the existence of solutions. If n>=3, then solutions to the above linear equation can always be given using n-1 parameters. If we define first n-2 xi's as parameters, then with another parameter m, we can express the solutions for the other two. For n=2, solutions can be determined using only one parameter, m. For n=1, If a solution exists, it can be computed by dividing b by a1. I guess I answered your question. If not please let me know. I checked the ODE module and indeed it can be used as a reference model for this project. I hope to implement a method DiophantineSolve(), which would take DE to be solved in the form f(x1*,* x2*,* x3*,* ...xn) = 0 or f(x, y, z) = 0 as an argument. All of the proposed equations can be expressed in such a way by a simple rearrangement. It will return the solutions/solution if they/one exist(s). For inner computations a classification function would be needed as in ODE module. That can be used to determine whether the DE is linear, quadratic, Pythogrean, .. etc. Algorithm used for the solution will depend on the result of this classification. I am still studying the ODE module. I am not familiar with pattern matcher either. I would take a look at that also. Comments and suggestions are appreciated. Thanks in advance. Regards, Thilina Rathnayake. On Mon, Apr 29, 2013 at 1:52 AM, Aaron Meurer <asmeu...@gmail.com> wrote: > Just to be clear, is this for GSoC, or is this just something that you > want to implement on your own? > > On Sun, Apr 28, 2013 at 2:07 PM, Thilina Rathnayake > <thilina.r...@gmail.com> wrote: > > Hi, I would like to implement a Diophantine equations module for Sympy. > > You can find my pull request here. It's still not merged. > > > > I hope to solve following classical Diophantine equations. All the > variables > > and constants > > used here are integers. > > > > > > 1) a1x1 + a2x2 + a3x3 + ...+ anxn = b (Linear diophantine equation) > > Here a1, a2, ... an and b are constants.If solvable (there is a > condition to > > determine this), > > solving this equation means expressing any two variables using other > > variables and an > > arbitrary integer n. i.e. solution is given by > > x1 = x1, x2 = x2, ... xn-2 = xn-2 , xn-1 = f( x1, x2, ... xn-2, n), xn-1 > = > > g( x1, x2, ... xn-2, n) > > f and g are functions to be determined. > > The n in the indices is different from the other n, right? > > Is the rank of the system always 2 in this case? > > > > > 2) x12 + x22 + x32 + ... xn2 = k > > Here k is a non-negative constant. There will be a number of solutions > > depending on > > n and k. Solving this means assigning constants a1, a2, ... an to xi's > > respectively. > > > > 3) x12 + x22 + x32 + ... xn2 = xn+12 (extension of Pythogorean equation) > > Solving this is pretty standard. There is a general primitive solution > set > > using n relatively > > prime integers. All other solutions can be obtained by multiplying those > > equations by > > an arbitrary integer. > > > > 4) x2 + axy + y2 = z2 > > Here a is a constant. If z is a variable, a general solution can be > given to > > this equation > > using a and three arbitrary integers. If z is a constant actual solutions > > can be given. > > > > 5) x2 - Dy2 = m2 (Pell's equation) > > Here D and m are constants. This has either no solution or infinitely > many > > solutions. > > ax2 - by2 = 1 and ax2 + bxy + cy2 + dx + ey + f = 0 can also be solved > with > > the light > > of Pell's equation. > > > > Lot of Diophantine equations can be converted to one of these forms. > > Addition of this kind > > a module will be a huge enhancement for Sympy. I would like to know how I > > can improve > > this. Thanks in advance. > > It sounds like a good start. If this is for GSoC, I'd like to see more > details. > > One thing to be aware of is that you will probably spend more time > worrying about how to pattern match these things than writing the > algorithms to solve them. SymPy has .match, but it can be limited. > For example, you can easily write a pattern to match > > x1**2 + x2**2 = k > > But if you can solve that, then you can also solve > > (x1 - 1)**2 + (x2 - 1)**2 = k > > or > > x1**2 - 2*x1 + x2**2 - 2*x2 = k > > by a simple shift. But the same simple pattern won't match either of > these. I ran into this kind of issue all the time when I wrote the ODE > module, which works very similarly (by the way, you should take a look > at the design there, as I think the design of this module can be very > similar). We should extend the pattern matcher's abilities to be able > to still succulently write patterns, but to allow them to match more > advanced things like shifts automatically. > > Of course, the worst case scenario is that it won't recognize a given > equation as being in a certain form, so it just won't be able to solve > as much as it could. So if you want, you could focus on this, or you > could leave it to someone else. > > Aaron Meurer > > > > > > > > > References > > [1] An Introduction to Diophantine Equations, Andreescu, Titu, Andrica, > > Dorin, Cucurezeanu, Ion > > [2] http://mathworld.wolfram.com/DiophantineEquation.html > > [3] http://en.wikipedia.org/wiki/Diophantine_equation > > > > Regards, > > Thilina Rathnayake. > > > > -- > > You received this message because you are subscribed to the Google Groups > > "sympy" group. > > To unsubscribe from this group and stop receiving emails from it, send an > > email to sympy+unsubscr...@googlegroups.com. > > To post to this group, send email to sympy@googlegroups.com. > > Visit this group at http://groups.google.com/group/sympy?hl=en-US. > > For more options, visit https://groups.google.com/groups/opt_out. > > > > > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sympy+unsubscr...@googlegroups.com. > To post to this group, send email to sympy@googlegroups.com. > Visit this group at http://groups.google.com/group/sympy?hl=en-US. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscr...@googlegroups.com. To post to this group, send email to sympy@googlegroups.com. Visit this group at http://groups.google.com/group/sympy?hl=en-US. For more options, visit https://groups.google.com/groups/opt_out.
