Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's Technology & Calculator Open Topic subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

This forum is locked: you cannot post, reply to, or edit topics. Math and Science => Technology & Calculator Open Topic
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
Sven.Thomas0


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 Very Happy 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
Display posts from previous:   
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
    »
» View previous topic :: View next topic  
Page 1 of 1 » All times are GMT - 5 Hours

 

Advertisement