-
-
Notifications
You must be signed in to change notification settings - Fork 1.8k
GH-1005: Pell's equation #1388
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
base: main
Are you sure you want to change the base?
GH-1005: Pell's equation #1388
Conversation
79f7120
to
a4c3729
Compare
src/others/pells_equation.md
Outdated
|
||
$$\sf=2+\cfrac{1}{1+\cfrac1{1+\cfrac1{1+\cfrac4{\vdots}}}}$$ | ||
|
||
we get the continued fraction of $\sf$ as $[2; 1, 1, 4, 1, 1, 4, \ldots]$. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Note this relies on floating point numbers. You can do it entirely with integer arithmetic.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Can you give me reference for doing it using integer arithmetic completely?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
"Quadratic irrationality" section of continued fraction article has it:
# compute the continued fraction of sqrt(n)
def sqrt(n):
n0 = math.floor(math.sqrt(n))
x, y, z = 1, 0, 1
a = []
def step(x, y, z):
a.append((x * n0 + y) // z)
t = y - a[-1]*z
x, y, z = -z*x, z*t, t**2 - n*x**2
g = math.gcd(x, math.gcd(y, z))
return x // g, y // g, z // g
used = dict()
for i in range(n):
used[x, y, z] = i
x, y, z = step(x, y, z)
if (x, y, z) in used:
return a
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
included with a link after non-integer example
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I would actually strongly suggest to replace the whole section to only show integer calculation, as floating-point calculation might be unstable.
@@ -8,5 +8,6 @@ converted.pdf | |||
/public | |||
.firebase/ | |||
firebase-debug.log | |||
.idea/ |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Do not include this
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
.gitgnore just ignores files to not include them when we do git add .
So, that won't affect anything
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
.idea/ |
I think we should remove this, unless it is something that is really needed for the project at large, rather than specific developer.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Why is it here again 🤔
Possibly useful: Codeforces - Pythagorean triples and Pell's equations. |
db59072
to
4732ab4
Compare
added in reference section |
123711e
to
bd4351c
Compare
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Hi, could you please add this article to README.md
and mavigation.md
into lists of new articles?
f88828b
to
c72a19c
Compare
added in |
Updates? |
Updated all suggestions. Have I missed any? |
ab10315
to
5ff3016
Compare
5ff3016
to
32e048b
Compare
Here we will consider the case when $d$ is not a perfect square and $d>1$. The case when $d$ is a perfect square is trivial. | ||
We can even assume that $d$ is square-free (i.e. it is not divisible by the square of any prime number) as we can absorb the factors of $d$ into $y$. | ||
|
||
$x^{2} - d \cdot y^{2} = ( x + \sqrt{d} \cdot y ) ( x - \sqrt{d} \cdot y ) = 1$ |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This equation looks like it just comes out of nowhere. As in, it isn't connected with the paragraphs that are immediately adjusted to it. I would add some explanation on what are we doing here exactly.
Also consider wrapping this in $$...$$
instead of $...$
.
Multiplying the above inequality by $( x_{0} - \sqrt{d} \cdot y_{0} )^{n}$,(which is > 0 and < 1) we get | ||
|
||
$ 1 < (u + v \cdot \sqrt{d})( x_{0} - \sqrt{d} \cdot y_{0} )^{n} < ( x_{0} + \sqrt{d} \cdot y_{0} ) $ | ||
Because both $(u + v \cdot \sqrt{d})$ and $( x_{0} - \sqrt{d} \cdot y_{0} )^{n}$ have norm 1, their product is also a solution. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
You use the term "norm" here, but it's not defined. We should add a definition + an explanation why we care about it (primarily because it is multiplicative).
|
||
$ 1 < (u + v \cdot \sqrt{d})( x_{0} - \sqrt{d} \cdot y_{0} )^{n} < ( x_{0} + \sqrt{d} \cdot y_{0} ) $ | ||
Because both $(u + v \cdot \sqrt{d})$ and $( x_{0} - \sqrt{d} \cdot y_{0} )^{n}$ have norm 1, their product is also a solution. | ||
But this contradicts our assumption that $( x_{0} + \sqrt{d} \cdot y_{0} )$ is the smallest solution. Therefore, there is no solution between $( x_{0} + \sqrt{d} \cdot y_{0} )^{n}$ and $( x_{0} + \sqrt{d} \cdot y_{0} )^{n+1}$. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
We defined the smallest solution by saying that it is the solution with the smallest positive
|
||
## To find the smallest positive solution | ||
### Expressing the solution in terms of continued fractions | ||
We can express the solution in terms of continued fractions. The continued fraction of $\sqrt{d}$ is periodic. Let's assume the continued fraction of $\sqrt{d}$ is $[a_{0}; \overline{a_{1}, a_{2}, \ldots, a_{r}}]$. The smallest positive solution is given by the convergent $[a_{0}; a_{1}, a_{2}, \ldots, a_{r}]$ where $r$ is the period of the continued fraction. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Let's add a link to continued fractions article. Ideally, I would also add explanation on why it is a solution at all, and why is it the smallest possible.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Also, the paragraph says that "the smallest solution is given by ...", but doesn't tell that, specifically, the solution is
|
||
It can also be calculated using only [integer based calculation](https://cp-algorithms.com/algebra/continued-fractions.html) | ||
|
||
### Finding the solution using Chakravala method |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This looks complicated. Are there specific reasons to do it over continued fractions variant? I find the exposition very hard to read (largely because of misrenders, though).
Unless it's in some way better than continued fractions method, I'd consider dropping the section altogether.
2771efd
to
271c26a
Compare
271c26a
to
3f2791e
Compare
Co-authored-by: Oleksandr Kulkov <adamant.pwn@gmail.com>
Proof and how to find using continued fractions.
Chakralava Method
Problems
References