GSoC 2014 Diophantine equation

[Nguyen Tung]

Hi,
My name is Tung. I'm 19 and I'm from Vietnam. I have a question concerning Diophantine equation. In the very last line of your Ideas list, you say there is more work to do. So can you tell me more information about this topic and what exactly need to be done ?

[Thilina Rathnayake]

Hi Nguyen,

We need to improve the solutions for linear Diophantine equations

as the current implementation doesn't give you the complete set of

solutions. I made the following PR recently to correct this.

https://github.com/sympy/sympy/pull/7241

Also you can take a look at the two open issues  on the Diophantine module.

https://github.com/sympy/sympy/issues?labels=Diophantine&page=1&state=open

Another area you can work on is the exponential Diophantine equations. But

I don't have any good references to which I can point you.

Let me know if you have any further questions.

Regards,

Thilina

On Thu, Mar 13, 2014 at 7:11 PM, Nguyen Tung <iwon...@gmail.com> wrote:

Hi,
My name is Tung. I'm 19 and I'm from Vietnam. I have a question concerning Diophantine equation. In the very last line of your Ideas list, you say there is more work to do. So can you tell me more information about this topic and what exactly need to be done ?

--
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+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/c0a13160-ef9b-4206-8c4d-6a7f570f1492%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Nguyen Tung]

Hello,

Can you show me the link to factor_list ? I'm trying to read through diophantine.py. However, I'm new to GitHub.

[Thilina Rathnayake]

Hi,

Below is the link for `factor_list()` documentation.

http://docs.sympy.org/latest/modules/polys/reference.html?highlight=factor_list#sympy.polys.polytools.Poly.factor_list

You can find documentation on functions, classes and Modules in online sympy documentation.

http://docs.sympy.org/latest/index.html

Just do a search using the search box found in the left side. Also, you can build the
documentation locally if you have a clone of the SymPy repository. Just follow the
instructions at sympy/doc/README.rst

Additionally, You can type the following command in the git repository.

git grep -i "factor_list"

Regards,

Thilina

--

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+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/f4d8ceae-8d54-4a35-a147-5a9284c4068b%40googlegroups.com.

[Nguyen Tung]

I downloaded the whole source code by clicking "Download Zip" on this site:
 
https://github.com/sympy/sympy 

When I runned diophantine.py, it turned out a ImportError: No module named sympy
Can you explain why? Is it because the python version I'm using is 2.7? or do you know any other ways to run the code?

On Thursday, March 13, 2014 3:41:41 PM UTC+2, Nguyen Tung wrote:

[SAHIL SHEKHAWAT]

Its completely okay to download the source code as zip.

If i understand correctly The problem you are facing maybe that "sympy" is not on you env path and for that you firstly must run

$ python setup.py install 

from the sympy folder that you just have downloaded and if you want to develop on that very copy than just installing then you must run

$ python setupegg.py install

which is same as the former one but this time the env path will always point to this folder only and you can develop easily on it.

--

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+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/ff0dad0d-0ed8-4f2e-9382-0b1e4603685e%40googlegroups.com.

[Nguyen Tung]

Yes, I did nothing but tried to run the file diophantine.py. As you said, I haven't installed sympy, so can you show to how to install it step-by-step? I just right-click the the file setup.py, choose "edit with IDLE" then hit F5, then setupegg.py, hit F5, but i doesn't fix the problem.

Thanks in advance

[SAHIL SHEKHAWAT]

I have already given you the commands that you can run from your command line, presuming that you are on linux.

just 'cd' into the folder of sympy. there you will find setup.py and setupegg.py files into that folder. then just run

$ python setup.py install 

if you just want to install and

$ python setupegg.py install

if you also want to develop. 

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/08da6d10-e5b0-4257-b5a4-3eae2a1180fc%40googlegroups.com.

[SAHIL SHEKHAWAT]

Also, on windows you can run the same commands from the powershell.

[Nguyen Tung]

I'm using Windows, I type exactly what you said and I've cd to the folder containing setup.py and setupegg.py. But I got this:

'$' is not recognized as an internal or external command, operable program or batch file

[SAHIL SHEKHAWAT]

I am sorry for the '$' its actually is to show that this is the command which you should run from the command line..

run the command without '$' i.e

python setupegg.py install

and run only one of the above two commands.

 

Also, you will find command starting from '$' or '>>>' everywhere. well, dont just type these. these are just to show that it was a teminal or python shell etc.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/c7c62399-6064-417f-b16f-3cace1b26772%40googlegroups.com.

[Nguyen Tung]

Thanks, problem solved

[Nguyen Tung]

Hello,

In order to save time, can you tell me what kinds of Diophantine equation you have problems with? If possible, please give me an example.

Thank you

[Thilina Rathnayake]

Hi,

You mean the areas we need to improve? I noted some of the areas we need

to improve in my first reply to you. Please have a look at that. Let me know if

you have any problems with that.

Regards,

Thilina

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/8f31a303-6ef3-430e-968e-620e13437226%40googlegroups.com.

[Nguyen Tung]

First,
Yes, you said I can work on Diophantine equations. But I don't know what kind of equation you have problems with? (Is that binary quadratic or homogeneous ternary quadratic or general pythagorean)

Second,
I need some test cases that made you think your Diophantine solver needs to be improved. For example, 'x + y = 0' or 'x + 2*y = 3'. Something like that. So I can try to solve by hand to see why the code doesn't give the right answer (or incomplete solutions, as you said)

Third,
You were a little ambiguous in your first reply. I didn't really get what you said. What is PR? Is it a guide for me? In PR, you don't say anything about linear equations, and also the two issues you gave me were not about linear equations. (linear equations should be degree of one) I was so confusing. Please be more specific

Thank you

[Thilina Rathnayake]

Hi,

I am sorry If I was not clear to you early. I was just letting you know of the areas

you can work on. The PR refers to a "Pull Request". Are you familiar with github?

If not have a look at the following link.

https://help.github.com/articles/using-pull-requests

The link of the Pull request I gave to you is an attempt to make the solutions to
linear diophantine equation complete. Read the associated paper I have linked to

it on top of the Pull request. To solve linear equations completely We need to
implement the algorithm given in that paper. What we currently have now is a method

I came up during the last summer. Please note that this is not a bug fix, this is a

complete re-implemetation of the solutions for linear equations.

The two issues I pointed out are improvements suggested by Ondrej. Of course

they are not linear equations. You can work on them If you like. You will have to

find good references to work on those. There are a lot of references in my blog.

http://thilinaatsympy.wordpress.com/

Also search for diophantine equations in the following site. It will give you various

types of equations you can work on.

http://www.numbertheory.org/

Hope I have made myself clear to you. If not please do ask again.

Regards,

Thilina

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/39ad5ad3-1bba-4896-a787-4edff3ea729e%40googlegroups.com.

[Nguyen Tung]

Hi,

I've worked on the first issue you gave me:

diophantine(x**3-4*x*y**2+y**3-1)

I've found a bug in your classify_diop() that yields an error. In line 322, you put a '==' which should be '='. But even I fix that, the code gave me set([]) (which I assume no solution). Then, I tried to solve the equation by hand and I came up with (1, 0) (0, 1) (-2, 1) (2, 1) (in the order of (x, y)). Now I have two questions:

- Is my solution complete?
- Why did you add x**2*y : 0 to the 'coeff' dictionary after after conclude diop_type = 'cubib thue' ?

On Thursday, March 13, 2014 3:41:41 PM UTC+2, Nguyen Tung wrote:

[Nguyen Tung]

And another question, I've read the paper you gave me containing the algorithm that we want to implement. However, I think I don't really get the idea (notations, methods ...). Is there any chance I can still implement the module? 

[Thilina Rathnayake]

On Mon, Mar 17, 2014 at 1:09 AM, Nguyen Tung <iwon...@gmail.com> wrote:

Hi,

I've worked on the first issue you gave me:

diophantine(x**3-4*x*y**2+y**3-1)

I've found a bug in your classify_diop() that yields an error. In line 322, you put a '==' which should be '='. Bu

Yes that shoul be corrected. I guess it didn't come up as a bug because we currently
don't implement solutions for Thue equations.

t even I fix that, the code gave me set([]) (which I assume no solution).

 

That's because solutions for Thue equations have not been implemented.

I think it will be better to raise an exception rather than returning the empty

set.

 

Then, I tried to solve the equation by hand and I came up with (1, 0) (0, 1) (-2, 1) (2, 1) (in the order of (x, y)). Now I have two que

stions:

- Is my solution complete?

Well, I am not sure. We will have to confirm that by using an independent source.
PARI currently solves Thue equations. You can have a look at it.
http://pari.math.u-bordeaux.fr/

- Why did you add x**2*y : 0 to the 'coeff' dictionary after after conclude diop_type = 'cubib thue' ?

That's because the term doesn't appear in the equation. If the algorithms
(when they get implemented)  need to know the coefficient of x**2*y they can

find it in the coeff dictionary.

On Thursday, March 13, 2014 3:41:41 PM UTC+2, Nguyen Tung wrote:

Hi,
My name is Tung. I'm 19 and I'm from Vietnam. I have a question concerning Diophantine equation. In the very last line of your Ideas list, you say there is more work to do. So can you tell me more information about this topic and what exactly need to be done ?

--

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+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/aa4e359a-08a2-4c15-8fdd-d35faf65762a%40googlegroups.com.

[Thilina Rathnayake]

On Mon, Mar 17, 2014 at 8:37 PM, Nguyen Tung <iwon...@gmail.com> wrote:

And another question, I've read the paper you gave me containing the algorithm that we want to implement. However, I think I don't really get the idea (notations, methods ...). Is there any chance I can still implement the module? 

Well, try to implement something you understand very well. It doesn't need to be from

the paper I have linked in the Pull Request. Also, there is not enough work on that
paper for the summer.
 

On Sunday, March 16, 2014 9:39:20 PM UTC+2, Nguyen Tung wrote:

Hi,

I've worked on the first issue you gave me:

diophantine(x**3-4*x*y**2+y**3-1)

I've found a bug in your classify_diop() that yields an error. In line 322, you put a '==' which should be '='. But even I fix that, the code gave me set([]) (which I assume no solution). Then, I tried to solve the equation by hand and I came up with (1, 0) (0, 1) (-2, 1) (2, 1) (in the order of (x, y)). Now I have two questions:

- Is my solution complete?
- Why did you add x**2*y : 0 to the 'coeff' dictionary after after conclude diop_type = 'cubib thue' ?

On Thursday, March 13, 2014 3:41:41 PM UTC+2, Nguyen Tung wrote:

Hi,
My name is Tung. I'm 19 and I'm from Vietnam. I have a question concerning Diophantine equation. In the very last line of your Ideas list, you say there is more work to do. So can you tell me more information about this topic and what exactly need to be done ?

--

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+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/e4d9bd84-cc75-461d-9787-c96f87c57d3d%40googlegroups.com.

[Nguyen Tung]

Hi,

Do we really need a complete re-implementation? If some areas (like Thue equations) haven't been implemented, we'll work on those only.

On Thursday, March 13, 2014 3:41:41 PM UTC+2, Nguyen Tung wrote:

[Thilina Rathnayake]

On Tue, Mar 18, 2014 at 1:23 AM, Nguyen Tung <iwon...@gmail.com> wrote:

Hi,

Do we really need a complete re-implementation? If some areas (like Thue equations) haven't been implemented, we'll work on those only.

We only need to re-implement the solutions for linear diophantine equations.

Other implementations are okay. We can work on Thue equations if you

are interested

 

On Thursday, March 13, 2014 3:41:41 PM UTC+2, Nguyen Tung wrote:

Hi,
My name is Tung. I'm 19 and I'm from Vietnam. I have a question concerning Diophantine equation. In the very last line of your Ideas list, you say there is more work to do. So can you tell me more information about this topic and what exactly need to be done ?

--

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+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/ecc4a003-f25a-4b2e-bad9-399989b3749d%40googlegroups.com.

[Nguyen Tung]

Hi,

I've seen the way you solve Linear Diophantine equations. You break a large problem into smaller ones. Then you add solutions of all the smaller problems together, yield the solution of the large problem. I think it's very good. I don't find any bug or drawback. Why do you want to re-implement? You said incomplete solution. What makes you think that? Can you tell me more?

Thank you

On Thursday, March 13, 2014 3:41:41 PM UTC+2, Nguyen Tung wrote:

[Thilina Rathnayake]

Hi Nguyen,

Sorry I took a lot of time to get back to you.

Please go through this article.

http://thilinaatsympy.wordpress.com/2013/06/21/solving-linear-diophantine-equation/

I am not sure whether we can do the fallowing assumption when solving 2x + 3y + 4z = 5.

Lets set x = x and assume y = ax + bm + c and z = dx + em + f where a, b, c, d, e, f are constants to be found. m is the introduced parameter. Plug in these in original equation.

Regards,

Thilina

--

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+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/3c29f2cf-a405-4fab-9a2c-a513ada9f38e%40googlegroups.com.