An efficient way to find perfect squares?

[foo_daemon]

Hi,

I have a problem that I'm a bit stuck on, and need some direction:

I need to find \forall_n within a certain domain that can satisfy this equation:

\left( 3n-1 \right) \left( n+1 \right) = m^{2} where m,n \in \mathbb{Z}

Or, to put it in a different context, I'm looking for discrete values of n (within a certain domain) such that \sqrt{ \left( 3n - 1 \right) \left( n + 1 \right) } is an integer.

I know I can just do an iterative search over \forall_n in the domain, but shouldn't there be a faster, easier way using some number theory?
If 3n - 1 and n + 1 are both perfect squares, then it is true, but it is also true if their product is a perfect square (e.g. n=17 ). I'm just not sure how to piece all the conditions together into a coherent algorithm.

 

[Hurkyl]

You might get better answers if you explained what your certain domain is.

If you consider iterating over the domain I don't see why you're having difficulty coming up with a coherent algorithm...


Are you sure you actually need an "efficient" way? People have a tendency to "prematurely optimize" -- i.e. to spend effort trying to speed up a part of the calculation without ever bothering to check that it needs to be sped up.

I'm mildly skeptical that the most stupidly obvious method isn't good enough for your purposes.



Anyways, applying some algebraic geometry:

Your equation defines a conic section in the plane. (a hyperbola)

Suppose (m0, n0) and (m1, n1) are two rational points lying on the hyperbola. Then the slope of the line passing through them is rational (or infinite).

Conversely, if L is any line passing through (m0, n0) whose slope is rational, then either L is tangent to the hyperbola, or L intersects the hyperbola in two rational points.


This gives us an easy way to enumerate the rational solutions to your equation. Take (m_0, n_0) = (2, 1). Now, consider the line

m = 2 + t (n -1)​

Plugging this into the equation of the hyperbola, we find the two solutions for n are:

n=1
n = \frac{t^2 - 4t + 5}{t^2 - 3} = 1 + \frac{8 - 4t}{t^2 - 3}​

Remember that t can be a rational number -- so the possible rational values for n are
n = 1 + \frac{v(8v - 4u)}{u^2 - 3v^2}
where I've set t = u/v, with u and v relatively prime.

Ah, but we want n to be an integer! If u is nonzero, then v and u^2 - 3v^2 are relatively prime, so we must have that

\frac{8v - 4u}{u^2 - 3v^2}​

is an integer.


It's unfortunate that's a minus sign in the denominator. If it were a plus sign, we could easily list all possible values of (u,v) that give an integer. However, at least we can see that u needs to be unusually close to u^2 - 3v^2. What if we set u = \sqrt{3} v + \epsilon?

I'm getting exhausted by the details at this point, so I'll sketch what I'm thinking for here. I want to solve the system of inequalities that says "the denominator of that fraction is smaller than the numerator" and whatever inequalities say "n is in your certain domain". I'm hoping there will be very few v that satisfy the system.

 

[dodo]

Oops... Hurkyl stepped in first. :) I did another (unfinished) attempt, which goes like this:

3n-1 is never a perfect square because it is congruent to 2 (mod 3), while squares are congruent to either 0 or 1 (mod 3). So the solutions have to be of the kind of your n=17.

Again, I don't have anything concrete, but this is one lead. Consider the recurrence sequence
a_n = 4a_{n-1} - a_{n-2}
When kickstarted with a_0=1, a_1=3 it produces 1, 3, 11, 41, 153..., and when started with a_0=1, a_1=5, it gives 1, 5, 19, 71, 265, ...

Take corresponding pairs from these two sequences, (1,1), (3,5), (11,19), (41,71), (153,265), ..., and denote one of these pairs as (a,b). The number \frac {a^2+b^2} 2 is an integer (because both a and b are odd). The first two such numbers happen to be 1 and 17, both making (3n-1)(n+1) a square. In fact, computer evidence suggests that all solutions have this form.

I was looking for a proof by induction that says, if the pair (a,c) works and the pair (b,d) works, then the pair (4b-a,4d-c) will work as well. It gets messy and I've not finished (not that I'm certain to finish, of course!).

And, of course, such a proof would only show that numbers of this form are solutions, not that all solutions must have this form. More work is needed here! I'l try to write again during the week, if I arrive somewhere.

As an additional observation, note that, if (3n-1)(n+1) is a square, then (3n-1)(n+1) + (n-1)^2 = (2n)^2 is a Pythagorean triple, which is part of the reason why I came up with the above; this may play a part in the induction proof. Maybe.

Hope this helps--

 

[RamaWolf]

The first five values satisfying your equation are n_{i} = 1, 17, 241, 3361, 46817,...
(the corresponding values of the right side are m_{i} = 2, 30, 418, 5822, 81090, ...)
and the general recursion formula for n_{k} is
n_{k} := 15*n_{k-1} - 15*n_{k-2} + n_{k-3}

 

[RamaWolf]

Consider the isosceles triangle with side length (n, n, n-1), then for the length
of the height upon the smalller side we have:

h = \frac{1}{2} * \sqrt{(3*n-1)*(n+1)}

and for n from {17,241,331, etc} since h and b = \frac{1}{2}+(n-1) are integers, we
have a Pythagorean triangle with sides (b, h, n) (see post of Dodo above)

 

[foo_daemon]

RamaWolf: Haha, nice! Yep, you identified where this problem stems from (I was sort of partitioning it up): http://projecteuler.net/index.php?section=problems&id=94

To find integer areas of the isosceles triangle \left( n, n, n-1 \right) one must solve (expanded from Heron's formula):Area = \frac{\left(n-1\right)} {4}\sqrt{\left( 3n - 1 \right) \left( n + 1 \right) }

Now the other part left to solve:

For the isosceles triangle \left( n, n, n+1 \right), the formula is incredibly similar:Area = \frac{\left(n+1\right)}{4}\sqrt{\left( 3n + 1 \right) \left( n - 1 \right) }

That recursive formula is great, but could you give me some pointers/links on how you got to it? I'd like to try to reach a similar formula for the second part of the problem on my own..

Thanks all!

 

[foo_daemon]

Wow, was just testing around and it appears the exact same recursive formula satisfies the second part of the equation as well (the 'conjugate' square, I guess you could call it?). You just need to use the different set of initial values: n_i = 1, 5, 65, 901, 12545...
m_i = 0, 8, 112, 1560, 21728...Awesome, now I just need to figure out how to derive that answer..

 

[RamaWolf]

Consider the isosceles triangle with side length (n, n, n-1), then for the length
of the height upon the smalller side we have:

h = \frac{1}{2} * \sqrt{(3*n-1)*(n+1)}

and for n from {17,241,331, etc} since h and b = \frac{1}{2}+(n-1) are integers, we
have a Pythagorean triangle with sides (b, h, n) (see post of Dodo above)

Typo: the formula for b is: b = \frac{1}{2}*(n-1)

 

[RamaWolf]

RamaWolf: Haha, nice! Yep, you identified where this problem stems from (I was sort of partitioning it up): http://projecteuler.net/index.php?section=problems&id=94

To find integer areas of the isosceles triangle \left( n, n, n-1 \right) one must solve (expanded from Heron's formula):


Area = \frac{\left(n-1\right)} {4}\sqrt{\left( 3n - 1 \right) \left( n + 1 \right) }

Now the other part left to solve:

For the isosceles triangle \left( n, n, n+1 \right), the formula is incredibly similar:


Area = \frac{\left(n+1\right)}{4}\sqrt{\left( 3n + 1 \right) \left( n - 1 \right) }

That recursive formula is great, but could you give me some pointers/links on how you got to it? I'd like to try to reach a similar formula for the second part of the problem on my own..

Thanks all!

If the sequence is {a_{k}) then get a linear system of equations like this:

a_{k} = x_{1}*a_{k-1}+ x_{2}*a_{k-2}+ x_{3}*a_{k-3}

Mathematica commands:

eqs = {3361 == 241 x1 + 17 x2 + x3,46817 == 3361 x1 + 241 x2 + 17 x3,652081 == 46817 x1 + 3361 x2 + 241 x3};
vars = {x1, x2, x3};
sol = Solve[eqs, vars]

 

[RamaWolf]

Btw:

if a_{k} := (3*a_{k} - 1)*(a_{k} + 1) = b_{k}^{2} with a_{k} and b_{k} \in \mathbb{Z},

(initial values as above), then we have to recursions:

a_{k} = 15*a_{k-1} - 15*a_{k-2} + a_{k-3} for k > 3

and

b_{j} = 14*b_{j-1} - b_{j-2} for j > 2

 

[dodo]

Well, certainly the rule
n_k = 15n_{k-1} - 15n_{k-2} + n_{k-3}
is much easier to use in practice than what I wrote in post#3.

However, personally I need the musings in post#3 in order to prove that the values of n produced by this recurrence sequence indeed make (3n-1)(n+1) a square.

I think I completed a proof (to be posted soon), but I'm yet trying to finish the case for the converse, that is, a proof that the only values of n that make (3n-1)(n+1) a square are those coming from the recurrence sequence.

More details soon, hopefully. In the meantime, realize that, if a, ~ b, ~ 4b-a and 4(4b-a)-b = 15b-4a are four consecutive values of a sequence with recurrence rule
a_k = 4a_{k-1} - a_{k-2}
and if c, ~ d, ~ 4d-c and 15d-4c are four consecutive values of another sequence with the same recurrence rule (but possibly different starting values), and if the function
n(x,y) = \frac {x^2 + y^2} 2
is used to combine corresponding values of the two sequences, then applying RamaWolf's rule to three consecutive values of n(x,y) we obtain
\begin{align*}<br /> 15 \cdot n(4b - a,4d - c) - 15 \cdot n(b,d) + n(a,c)<br /> \\<br /> &amp;= 15 \cdot \frac {16b^2 - 8ab + a^2 + 16d^2 - 8cd + c^2} 2 - 15 \cdot \frac {b^2 + d^2} 2 + \frac {a^2 + c^2} 2 \\<br /> &amp;= \frac {240b^2 - 120ab + 15a^2 + 240d^2 - 120cd + 15c^2 - 15b^2 -15d^2 + a^2 + c^2} 2 \\<br /> &amp;= \frac {225b^2 - 120ab + 16a^2 + 225d^2 - 120cd + 16c^2} 2 \\<br /> &amp;= \frac {(15b - 4a)^2 + (15d - 4c)^2} 2 \\<br /> &amp;= n(15b - 4a, 15d - 4c)<br /> \end{align*}
so the two approaches are the same.

 

[RamaWolf]

Our initial problem converned a isosceles triangle (t, t, t - 1);
now let t = 2 s + 1 and h by the height on the smaller side (i.e. t - 1),
the question was wether the triagle (s, h, t) is a
Pythagorean triangle (or the numbers (s, h, t ) by a Pythagorean tripel PT).

Numerical evidence has delivered the first examples of that PT be:

(s, h, t) = (0, 1, 1), (8, 15, 17), (120, 209, 241), (1680, 2911, 3361), (23408, 40545, 46817)

Recursion formulas are:

s_{k} := 8 + 14 s_{k-1} - s_{k-2 } ( NEW!)

h_{k} := 14 h_{k-1} - h_{k-2 }

t_{k} := 15 t_{k-1} - 15 t_{k-2 } + t_{k-3}

 

[ramsey2879]

Our initial problem converned a isosceles triangle (t, t, t - 1);
now let t = 2 s + 1 and h by the height on the smaller side (i.e. t - 1),
the question was wether the triagle (s, h, t) is a
Pythagorean triangle (or the numbers (s, h, t ) by a Pythagorean tripel PT).

Numerical evidence has delivered the first examples of that PT be:

(s, h, t) = (0, 1, 1), (8, 15, 17), (120, 209, 241), (1680, 2911, 3361), (23408, 40545, 46817)

Recursion formulas are:

s_{k} := 8 + 14 s_{k-1} - s_{k-2 } ( NEW!)

h_{k} := 14 h_{k-1} - h_{k-2 }

t_{k} := 15 t_{k-1} - 15 t_{k-2 } + t_{k-3}

The following also appear to work
t_{k} := 4 + 14 t_{k-1} - t_{k-2 }
s_{k} := 15 s_{k-1} - 15 s_{k-2 } + s_{k-3}
h_{k} := 15 h_{k-1} - 15 h_{k-2 } + h_{k-3}

 

[dodo]

This is the enchilada I have so far. There is a proof that the sequence 15 blah - 15 blah + blah produces numbers n such that (3n-1)(n+1) is a square. There is also a bare sketch of the converse, which is proving too hard for me; maybe someone can fill in the holes or suggest an alternative.

 

[RamaWolf]

I now want to link our initial problem

(isosceles triangle with sides (t, t, t-1) and integer valued area)

to the theory of Pythagorean triangles.

I start with

Lemma: Let b_{0} and b_{1} be co-prime natural numbers and

b_{k}:=4 b_{k-1} - b_{k-2}

then the pairs (b_{k},b_{k+1}) are all co-prime

Euclidean Rule for Pythagorean Numbers:
Let (m,n) be co-prime natural numbers (m<n), then

h := n^{2} + m^{2}
e := 2 m n
d := n^{2} - m^{2}

form the hypothenuse, the even and the odd leg
of a primitive Pythagorean triangle (PPT)


Now we have from b = {0, 1, 4, 15, 56, 209, 241, ...}

(m.n) -h- -e- -d-
---------------------------------
(1,4) -17- -8- -15-
(4,15) -241- -120- -209-
(15,56) -3361- -2911- -1680-
(56,209) -46827- -23408- -40545-
(...,...)

Without any difficulty, we identify the list of the h's with the side t of the
isosceles triangle, the e's as half of the side (t-1) and the d's as the
heights of the isosceles triangle over the smaller side, returning an integer
valued are of the isosceles triangle as h * e * d.

Remark: From this point of view it is clear and needs no further proof,
that h^{2} - e^{2} is a perfect square

 

[RamaWolf]

I opened a new thread called

Pythagorean Triangles with one side equal s and hypothenuse equal 2 s+1