Author 
Message 

Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360

Posted: 17 Jun 2010 05:51:47 pm Post subject: 


Given a^{2}, and the formula A^{2}+B^{2}=c^{2}, is it possible to find b and c, such that they are integers.
I know one B value is 2b+1=a^{2}, and the corresponding c value is b+1, but there is another solution, with both b and c being less then this easy to find one.
Take 221 for example. There is the solution b=110 and c=111, but there is also b=2 and c=15.
Take 27 for example. There is the solution b=13 and c=14, but there is also b=3 and c=6.
The number of solutions does not matter. With a semiprime, like 221, there are always two. A prime only leaves one solution. Is there a way to find these values?
Last edited by Guest on 17 Jun 2010 06:01:22 pm; edited 1 time in total 

Back to top 


Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 17 Jun 2010 07:05:33 pm Post subject: 


You're saying that [font=times new roman][size="3"]a[/size] doesn't even need to be an integer?
Find a [font=times new roman][size="3"]b[/size] for which [font=times new roman][size="3"]√(a+b²) = c[/size] is an integer.
For(B,0,Ans
If fPart(√(Ans+B[font=verdana]²
End
If B<Ans
{B,√(Ans+B[font=verdana]²
Last edited by Guest on 17 Jun 2010 07:18:24 pm; edited 1 time in total 

Back to top 


Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360

Posted: 17 Jun 2010 07:52:24 pm Post subject: 


Ok, that works, but it's slow for big numbers. Is there any other way? 

Back to top 


Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 17 Jun 2010 08:44:43 pm Post subject: 


Not if you want the smallest solution; I think the primality of integers has some involvement here.
Obeying (A139544), this version will detect ahead of time whether an answer can be found:
If not(fPart(Ans/4.5
Stop
For(B,0,Ans
If fPart(√(Ans+B[font=verdana]²
End
{B,√(Ans+B[font=verdana]²
How big a number are we talking about?
[EDIT]
On second thought, I wonder if the extended Euclidean algorithm might find a use here.
Last edited by Guest on 17 Jun 2010 08:50:56 pm; edited 1 time in total 

Back to top 


Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360

Posted: 17 Jun 2010 08:56:06 pm Post subject: 


How would the extended Euclidean algorithm work here? That's just ax+by=gcd(a,B) right?
Last edited by Guest on 19 Jun 2010 08:03:27 am; edited 1 time in total 

Back to top 


Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 18 Jun 2010 11:38:36 pm Post subject: 


Without the smiley, yes. It's good for finding a number such that [font=times new roman][size="3"]a+b×n[/size] is an integer (or, given a linear plot on a grid, which points reside on intersections).
One of my failed projects was this: upon wishing to restore the integer part of [font=times new roman][size="3"]m = fpart(√(x))[/size] (and by extension find an integer whose square root approximates any fraction), and then noticing that the successive differences of [font=times new roman][size="3"](m+n)²[/size] have a constant fractional part [font=times new roman][size="3"]r[/size], I wanted to set it up so that [font=times new roman][size="3"]m²+r×n[/size] came to an integer. It never worked out, sadly.
I remembered all that while reading this thread yesterday, and decided to give it another shot. Again, nothing came to fruition.
As for PMs not working as you told me in your email, I've verified the problem. When I fix it, I'll shoot you a PM.
[EDIT] – There is a onepost prerequisite for sending PMs. I sent you instructions on how to send them.
Last edited by Guest on 19 Jun 2010 12:01:58 am; edited 1 time in total 

Back to top 


Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360

Posted: 19 Jun 2010 08:02:54 am Post subject: 


Can you give an example of the (m+n)^{2} thing? It sounds very interesting and possibly worth studying further. 

Back to top 


Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 19 Jun 2010 09:15:56 am Post subject: 


If you're given just the fractional part of the square root of an integer, there's no immediate way of telling what the integer part was. One could add the fraction to each of the natural numbers and then square it to see which one removes the fractional part altogether. But, my goal was to do better than that.
After invoking a little algebra to simplify the problem—which I should've done beforehand—[font=times new roman][size="3"](m+n)²[/size] became [font=times new roman][size="3"]m²+2mn = m(m+2n)[/size]. I've discarded the [font=times new roman][size="3"]n²[/size] term because, as it's an integer, it contributes nothing to the removal of the fractional part. This is already similar to my [font=times new roman][size="3"]m²+r×n[/size] approach from earlier, with the exception of the convenient factor of two, which now halves the search time (although it is the same number of steps as the method from the last paragraph, but the operations may be easier to perform).
For your example, let's say I have [font=times new roman][size="3"]m = .124355652982[/size]. Start iterating...
[font=times new roman][size="3"]m²+2m×1[/size]
[font=times new roman][size="3"]m²+2m×2[/size]
[font=times new roman][size="3"]m²+2m×3[/size]
...
[font=times new roman][size="3"]m²+2m×12[/size]
I stopped here because the result left no fractional part.
Adding [font=times new roman][size="3"]12[/size] to [font=times new roman][size="3"]m[/size] and squaring it gives you [font=times new roman][size="3"]147[/size] – this is the smallest integer whose square root is a number with [font=times new roman][size="3"]m[/size] as its fraction.
So [font=times new roman][size="3"]m²+2mn[/size] becomes [font=times new roman][size="3"]a+bx[/size] with [font=times new roman][size="3"]a = m²[/size], [font=times new roman][size="3"]b = 2m[/size], and [font=times new roman][size="3"]x = n[/size], and I'm trying to find an integer [font=times new roman][size="3"]x[/size] where the whole thing is close to an integer.
Last edited by Guest on 19 Jun 2010 01:17:01 pm; edited 1 time in total 

Back to top 


Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360

Posted: 19 Jun 2010 08:03:40 pm Post subject: 


Interesting. what about the problem that I showed? Any ideas for that? 

Back to top 


Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 20 Jun 2010 02:27:14 am Post subject: 


Show me something that you have tried, first of all. 

Back to top 


bwang
Member
Joined: 15 Mar 2009 Posts: 128

Posted: 21 Jun 2010 04:28:12 pm Post subject: 


It is a wellknown fact that all Pythagorean triples are of the form (m^{2}n^{2}, 2mn, m^{2}n^{2}).
Case 1: a is of the form 2mn. Let a = 2 a_{1}. Then we see that m divides a_{1}. Hence, in this case, all solutions are given by b = m^{2}  (a / 2m)^{2}, c = m^{2} + (a / 2m)^{2}, with m a factor of a / 2. Note in this case, a must be even.
Case 2: a is of the form m^{2}  n^{2}. Then we see that (mn)(m+n) = a. Note that mn and m+n are of the same parity, so if a is even but not divisible by 4 there are no solutions. Otherwise, Let p>q be two divisors of a with the same parity (i.e. if 4a they are both even, else they are both odd). Then m+n = p and mn = q, so m = (p+q)/2 and n = (pq)/2. This lets us compute the values of b and c. 

Back to top 


Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360

Posted: 21 Jun 2010 04:47:41 pm Post subject: 


bwang wrote:
It is a wellknown fact that all Pythagorean triples are of the form (m^{2}n^{2}, 2mn, m^{2}n^{2}).
Case 1: a is of the form 2mn. Let a = 2 a_{1}. Then we see that m divides a_{1}. Hence, in this case, all solutions are given by b = m^{2}  (a / 2m)^{2}, c = m^{2} + (a / 2m)^{2}, with m a factor of a / 2. Note in this case, a must be even.
Case 2: a is of the form m^{2}  n^{2}. Then we see that (mn)(m+n) = a. Note that mn and m+n are of the same parity, so if a is even but not divisible by 4 there are no solutions. Otherwise, Let p>q be two divisors of a with the same parity (i.e. if 4a they are both even, else they are both odd). Then m+n = p and mn = q, so m = (p+q)/2 and n = (pq)/2. This lets us compute the values of b and c.
The only problem with that is that a is not an integer. a^{2} is. Thanks for that, though. 

Back to top 


bwang
Member
Joined: 15 Mar 2009 Posts: 128

Posted: 21 Jun 2010 05:31:41 pm Post subject: 


Wait, that post of mine was overly complicated. Since b^{2}  c^{2} = a^{2}, then we see (b  c)(b + c) = a^{2}. We may then use the same techniques as in case 2 of my previous post to solve the problem.
Sadly, this problem is equivalent to factoring a^{2}, which is hard.
Last edited by Guest on 21 Jun 2010 10:59:41 pm; edited 1 time in total 

Back to top 


Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360

Posted: 21 Jun 2010 05:33:33 pm Post subject: 


Oh. Great. It seems that problem blocks a lot of math. I wish factoring was easier. Oh well. Thanks anyway. 

Back to top 


Xeda112358
Active Member
Joined: 19 May 2009 Posts: 520

Posted: 27 Jan 2011 10:39:04 am Post subject: 


I know how to find pythagorean triples... does that help?
If you have a, then:
8b=(3a^{2}6)(1)^{a}(a^{2}+2)
8c=(3a^{2}+6)(1)^{a}(a^{2}2)
I was bored and I couldn't answer any more questions on the Putnam, so I did that I had to prove first that all integers above 2 were part of a Pythagorean Triple and I did that the same way I came up with the equation :P
I don't think it helps much if you want non integer inputs, though.
EDIT:I noticed that I put (1)^{2} instead of (1)^{a}
Last edited by Guest on 13 Feb 2011 12:34:22 pm; edited 1 time in total 

Back to top 


