Author |
Message |
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 17 Jun 2010 05:51:47 pm Post subject: |
|
|
Given a2, and the formula A2+B2=c2, is it possible to find b and c, such that they are integers.
I know one B value is 2b+1=a2, 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 e-mail, I've verified the problem. When I fix it, I'll shoot you a PM.
[EDIT] – There is a one-post 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 well-known fact that all Pythagorean triples are of the form (m2-n2, 2mn, m2-n2).
Case 1: a is of the form 2mn. Let a = 2 a1. Then we see that m divides a1. Hence, in this case, all solutions are given by b = m2 - (a / 2m)2, c = m2 + (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 m2 - n2. Then we see that (m-n)(m+n) = a. Note that m-n 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 4|a they are both even, else they are both odd). Then m+n = p and m-n = q, so m = (p+q)/2 and n = (p-q)/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 well-known fact that all Pythagorean triples are of the form (m2-n2, 2mn, m2-n2).
Case 1: a is of the form 2mn. Let a = 2 a1. Then we see that m divides a1. Hence, in this case, all solutions are given by b = m2 - (a / 2m)2, c = m2 + (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 m2 - n2. Then we see that (m-n)(m+n) = a. Note that m-n 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 4|a they are both even, else they are both odd). Then m+n = p and m-n = q, so m = (p+q)/2 and n = (p-q)/2. This lets us compute the values of b and c.
The only problem with that is that a is not an integer. a2 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 b2 - c2 = a2, then we see (b - c)(b + c) = a2. 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 a2, 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=(3a2-6)-(-1)a(a2+2)
8c=(3a2+6)-(-1)a(a2-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 |
|
|
|