Help me with this equations please!

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Amorydai
Posts: 3
Joined: Fri Nov 14, 2014 2:43 am UTC

Help me with this equations please!

Postby Amorydai » Fri Nov 14, 2014 3:00 am UTC

Hello all, I've been working on this equation off and on for 3 years now and am now not any closer to solving it than I was 3 years ago. It is as follows:

(a^2 + b) / (a + b^2) = n

a > b > 1 and a and b are both integers. Find the smallest pair of a and b for n = 202.

I tired solving it algebraically with no luck. I wrote a simple program to increment b starting at 2 and going up and then checking if a is an integer for any given value of b, but the program just runs forever and never quits. I tested the program out for other values of n and was able to come up with answers for almost all of them from n = 2 to 300, but try as I might I can't come up with an answer for n =202. Obviously the integers are going to be pretty large and there has to be a way to limit the search so I don't have to check each integer incrementally but I can't come up with one... Maybe someone can give me some ideas?

User avatar
somehow
Posts: 99
Joined: Wed Aug 14, 2013 8:31 pm UTC

Re: Help me with this equations please!

Postby somehow » Fri Nov 14, 2014 1:22 pm UTC

This narrows things down a little:

If a and b satisfy the given equation, then (rearranging) we have a^2 + b = 202(a + b^2). Let's think about the remainder on each side on division by 4.

The remainder of a^2 + b divided by 4 depends on the remainder of a divided by 4 and the remainder of b divided by 4. Let r by the remainder of a divided by 4 and let s be the remainder of b divided by 4. We can now compute the following table:

Code: Select all

   r: 0 1 2 3

s: 0  0 1 0 1
   1  1 2 1 2
   2  2 3 2 3
   3  3 0 3 0

For example, if r = 1 and s = 3, that means a = 4j + 1 and b = 4k + 3 (for some integers j and k), so a^2 + b = (4j + 1)^2 + 4k + 3 = 16j^2 + 8j + 1 + 4k + 3 = 4*(4j^2 + 2j + k + 1), so a^2 + b is divisible by 4 and the remainder is 0. This gives the second entry in the last row of the table. The rest are computed similarly.

The remainder of 202(a^2 + b) divided by 4 (the right side of the equation) depends only on whether a and b are even or odd.
If a and b are odd, then a^2 and b are odd, so (a^2 + b) is even, so 202(a^2 + b) is divisible by 4, and we get remainder 0.
If a and b are even, then a^2 and b are even, so (a^2 + b) is even, so again, we get remainder 0.
If a is odd and b is even, then a^2 is odd and b is even, so (a^2 + b) is odd, so 202(a^2 + b) has remainder 2 (when divided by 4).
If a is even and b is odd, then a^2 is even and b is odd, so (a^2 + b) is odd, so again, we get remainder 2.

Now we need the right and left sides of the equation to be equal, so in particular they must have the same remainder when divided by 4. If you compare the table for the left side of the equation with the information about the right side, you see that there are only two possibilites:
(1) b is divisible by 4, and a is even
(2) b has remainder 3 when divided by 4, and a is odd




Perhaps the solution space could be further reduced by thinking about other moduli besides 4. I'll think about it later if I get a chance. This essentially reduces the number of pairs to check by a factor of 4, though.
Xenomortis wrote:O(n2) takes on new meaning when trying to find pairs of socks in the morning.

curiosityspoon
Posts: 36
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Help me with this equations please!

Postby curiosityspoon » Fri Nov 14, 2014 2:26 pm UTC

This problem space reduces to "find B where sqrt(202B^2 - B + 10201) is an integer" (then A is simply the resulting integer plus 101), and from there the last digits of perfect squares allow us to rule out any B that ends in 1, 2, 6, or 7. Additionally, ending digits of 0, 3, 4, and 8 must be accompanied by an even tens digit, while 5 and 9 must have an odd tens digit in front of them.

There are definitely no such B <= 20000, which rules out A values up to about 284,000.

cphite
Posts: 1370
Joined: Wed Mar 30, 2011 5:27 pm UTC

Re: Help me with this equations please!

Postby cphite » Fri Nov 14, 2014 6:33 pm UTC

Have you tried putting (a^2 + b) / (a + b^2) = 202 into Wolfram Alpha?

User avatar
Xenomortis
Not actually a special flower.
Posts: 1456
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Help me with this equations please!

Postby Xenomortis » Fri Nov 14, 2014 6:55 pm UTC

It tries, bless it.
Image

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Help me with this equations please!

Postby jestingrabbit » Fri Nov 14, 2014 7:09 pm UTC

I thought I might let gcd(a, b) = d and a = Ad, and b = Bd. We then get Ad+B = 202Bd + 202A. Now, A, B and d are all relatively prime, so we have

202 A = B (mod d)
202 d = 1 (mod A)
d = 202 (mod B)
Ad + B = 0 (mod 202)

So, this seems at least a little profitable... but still hard to see the way forward.
Last edited by jestingrabbit on Fri Nov 14, 2014 9:06 pm UTC, edited 1 time in total.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Help me with this equations please!

Postby jaap » Fri Nov 14, 2014 8:30 pm UTC

The smallest solution is:
a=1993602325, b=140269363
This is followed by:
a=2293775132, b=161389448
There are no other solutions with b<213682610. At that point my computer program suffered from integer overflow.

I haven't found a good algebraic solution method, but have found a parameterization for all rational solutions:
a = (k + 202^2) / (202 - k^2)
b = (202k + 1) / (202 - k^2)
where k is any rational number.

If you write k=r/s, with r and s coprime, then you get:
a = s(r + s*202^2) / (202s^2 - r^2)
b = s(202r + s) / (202s^2 - r^2)

I don't see how you can determine for which values of r and s you get integer values for a and b.

Amorydai
Posts: 3
Joined: Fri Nov 14, 2014 2:43 am UTC

Re: Help me with this equations please!

Postby Amorydai » Fri Nov 14, 2014 10:37 pm UTC

Thank you for all the input guys. I knew the numbers would be big and if I let my program run for a day or two it would eventually come up with the answer, but I wasn't willing to wait that long, that's why I was looking for some constraints. At least now that I know the answer I won't be losing sleep at night! Jaap must have access to a supercomputer... Thanks again.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Help me with this equations please!

Postby jaap » Fri Nov 14, 2014 10:51 pm UTC

Amorydai wrote:Jaap must have access to a supercomputer...

No, just an ordinary laptop with an i5 processor. The Java program I used takes only 7.7 seconds to test all values of b up to 213682610. Here is my code:

Code: Select all

//(a-101)^2 = 202 b^2 - b + 101^2
public class Test {
   public static void main(String[] args) {
      long time = System.currentTimeMillis();
      long b = 1;
      while(true){
         long q = (202*b-1)*b+10201;
         if( q<0) break;
         long sq = (long)(Math.sqrt(q+0.5));
         if( sq*sq==q ){
            System.out.println("b="+b+" a="+(sq+101));
         }
         b++;
      }
      System.out.println(b);
      time = System.currentTimeMillis() - time;
      System.out.println((time/1000.)+" seconds elapsed.");
   }
}

User avatar
eta oin shrdlu
Posts: 451
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Help me with this equations please!

Postby eta oin shrdlu » Sat Nov 15, 2014 9:34 pm UTC

jaap wrote:I don't see how you can determine for which values of r and s you get integer values for a and b.

One way to parametrize the integer solutions is to convert the equation to Pell-like form,
R2 - n S2 = (2nb-1)2 - n (2a-n)2 = 1 - n3 = -8242407 .


Given a solution (R0,S0) in integers to the above equation, along with a solution (u,v) to the corresponding Pell equation
u2 - n v2 = 1 ,

you can generate an infinite family of solutions (Rk,Sk) to the above equation, by expanding
Rk + Sk*sqrt(n) = (R0+S0*sqrt(n)) (u + v*sqrt(n))k .

(This can be written as a linear first-order recursion for (Rk,Sk).) If (u,v) are chosen correctly then all integer solutions (R,S) are found as a union of some number of these infinite families; u/v is always a convergent in the continued-fraction expansion for sqrt(n). For n=202, we can take (u,v)=(19731763,1388322).

Of course not all of these (Rk,Sk) will give integer (ak,bk)=( (Sk+n)/2, (Rk+1)/(2n) ). But the transformation from (Rk,Sk) to (a,b) is linear, so if there is a solution then there are infinitely many, occurring periodically in the (Rk,Sk) sequence.

One obvious solution (R0,S0) is just (1,n). This doesn't give integer b, but the next few elements in this family are
(R1,S1) = (56668822651,3987204448)
(R2,S2) = (2236351556077127425,157349146400963446)
(R3,S3) = (88254317778390119472977899),6209552130072223389066148
The k=1 case gives the minimal solution
(a,b) = (1993602325,140269363) .
k=2 again gives a nonintegral b; k=3 gives a larger solution
(a,b) = (3104776065036111694533175,218451281629678513546975) .

We can get another family of solutions by noticing that 1-n3=-8242407=9(-915823). We can factor the square 32 into R and S and then look for a solution (R',S') to (R')2 - n (S')2 = -915823. Finding (R',S')=(135,68) we then multiply these by 3 to get another family based on (R,S)=(405,204). The first two solutions (a,b) from this family are
(a,b) = (2293775132,161389448)
(a,b) = (3572256154759519487778374,251343065963647140060824) .

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Help me with this equations please!

Postby skullturf » Sun Nov 16, 2014 5:52 pm UTC

This is really interesting. Does the equation (a^2+b)/(a+b^2) = n have a name that anyone's aware of? Does the equation have infinitely many solutions for all n? Did the OP get the question from a textbook or paper or anything, or just from playing around?

Amorydai
Posts: 3
Joined: Fri Nov 14, 2014 2:43 am UTC

Re: Help me with this equations please!

Postby Amorydai » Mon Nov 17, 2014 1:12 am UTC

skullturf wrote:Did the OP get the question from a textbook or paper or anything, or just from playing around?

Found it on Project Eureka, problem 815. Don't really know anything else about it. Problem states that there are integer solutions for all n>1.

Thanks for your breakdown eta oin shrdlu, that's a lot more math than I'm used to.

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Help me with this equations please!

Postby skullturf » Tue Nov 18, 2014 6:33 pm UTC

I was playing around with this a bit more, and I think I see how to prove that there are solutions for all n. Furthermore, using ideas suggested by eta oin shrdlu, I think it's possible to prove that there are infinitely many solutions when n is a nonsquare (this relies on knowing certain things about Pell's equation) but only finitely many solutions when n is a square.

I didn't write out all my steps in detail so it's possible I made a slip-up, but I think that's right.

EDITED TO ADD MORE:

If n is an even square, say n=(2m)^2, then a nontrivial solution is given by

a = 8m^5 + 2m^2
b = 4m^4

Verification: a^2 = 64m^10 + 32m^7 + 4m^4
a^2 + b = 64m^10 + 32m^7 + 8m^4
a + b^2 = 16m^8 + 8m^5 + 2m^2
(a^2+b)/(a+b^2) = 4m^2

However, I'm not quite sure how to prove there is always at least one nontrivial solution when n is an odd square.

When n=9, a nontrivial solution is (a,b)=(20,5).
Verification: 20^2+5 = 400 + 5 = 405
20+5^2 = 20 + 25 = 45
405/45 = 9

When n=25, a nontrivial solution is (a,b)=(143,26).
Verification: 143^2+26 = 20475, 143+26^2 = 819, 20475/819 = 25

When n=49, a nontrivial solution is (a,b)=(550,75).
Verification: 550^2+75 = 302575, 550+75^2 = 6175, 302575/6175 = 49

This might be all the nontrivial solutions, or close to all the nontrivial solutions, for the above three values of n. But I don't see how the pairs (20,5), (143,26), (550,75) fit into any obvious general pattern.

EDITED YET AGAIN to point out that (a,b)=(36,4) is another nontrivial solution when n=25.

Also, (a,b)=(101,5) and (a,b)=(1517,164) are two nontrivial solutions when n=81.

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Help me with this equations please!

Postby Nitrodon » Tue Nov 18, 2014 10:20 pm UTC

For n=m2, there are at most n/2 different solutions, each with a different value of a-mb between n/2 and n. If n is an odd square, the largest such solution has a-mb=(n+1)/2, and is given by:

a=(m2+1)(m2-m+2)/4
b=(m2+1)(m-1)/4


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 22 guests