Finding Common Numbers in Two Sequences

Date: 09/21/2006 at 15:29:18
From: James
Subject: Solving two ascending Series

Hi,

Given two sequences, is there a way to determine what numbers they 
will have in common?  For example,

Sequence 1: 22 (+21), 43 (+23), 66 (+25), 91
Sequence 2: 7 (+9), 16 (+11), 27, 40, 55, 72, 91

As you can see the sequences meet at the number 91.  In all the
problems I'm working with, each sequence has an initial number and an
initial amount to add to get the next number.  Then the amount added
increases by 2 in each step of the sequence.

I am currently writing both sequences out until I find a shared
number, so I'm wondering if there is a way to calculate where they
will meet based on the two initial values and initial amounts to add?

Thanks,

James

Date: 09/22/2006 at 14:26:38
From: Doctor Vogler
Subject: Re: Solving two ascending Series

Hi James,

Thanks for writing to Dr. Math.  It seems to me that a short-cut way
of finding when two sequences will have a common number would require
explicit formulas for each sequence.  A good method for doing this is
described at

  Method of Finite Differences
    http://mathforum.org/library/drmath/view/53223.html 

The bottom line is that if the first number is A, the first difference
is B, and each difference increases by C, then the n'th term is given by

  (C/2)(n^2 - 3n + 2) + B(n - 1) + A

In your case, the first sequence has

  A = 22, B = 21, C = 2.

The second sequence has

  A = 7, B = 9, C = 2.

You want to know if the n'th term of the first sequence could ever
equal the m'th term of the second sequence.  That means that you need
integer solutions to the equations

  (n^2 - 3n + 2) + 21(n - 1) + 22 = (m^2 - 3m + 2) + 9(m - 1) + 7

or

  n^2 + 18n + 3 = m^2 + 6m.

This is an example of a quadratic Diophantine equation.  In fact, it's
a special type that is rather easy to solve.  The method is described at

  Second-Degree Two-Variable Diophantine Equation
    http://mathforum.org/library/drmath/view/55988.html 

In your case, you proceed like this:  You complete the squares on both
sides:

  (n + 9)^2 - 78 = (m + 3)^2 - 9

and then rearrange the equation to make a difference of squares:

  (n + 9)^2 - (m + 3)^2 = 78 - 9 = 69.

Then you factor the difference of squares:

  (n + 9 + m + 3)(n + 9 - m - 3) = 69

or

  (n + m + 12)(n - m + 6) = 69.

This is a factored form of the original equation, and since n and m
have to be integers, solutions come from integer factors of 69.  In
particular, the factors of 69 are 1, 3, 23, 69, -1, -3, -23, and -69.
You can solve each for a solution.  For example, if

  n + m + 12 = 23
  n - m + 6 = 69/23 = 3,

then solving for n and m give n = 4, m = 7, and the 4th term in the
first sequence and the 7th term in the second sequence are both 91.

You can decide for yourself whether you consider solutions with either
n or m negative to be valid or not.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 08/05/2007 at 10:16:41
From: Bob
Subject: The nth term of two sequences

I have two sequences of which I am trying to calculate at what point 
each sequence will produce the same number.  The two sequences are:

29,653,2077,4301,.....
709,717,733,757,789,829,877,933,997,1069,1149,1237,1333,1437,1549,
1669,1797,1933,2077,....

As you can see, the 3rd number in the 1st sequence and the 19th 
number in the 2nd sequence are the same.

Can you please tell me where I'm going wrong on this?  I believe 
it's when I multiply the equations by 4 times the quadratic 
coefficient and then completing the square, but I can't seem to find 
it.

After reading your page I understand that the nth term is given by

  (C/2)(n^2-3n+2)+B(n-1)+A

and in the 1st sequence

  A=29, B=624, C=800

and in the 2nd sequence

  A=709, B=8, C=8

Now, plugging these values in the equation above I get

  (800/2)(m^2-3m+2)+624(m-1)+29 = (8/2)(n^2-3n+2)+8(n-1)+709

  400m^2 - 1200m + 800 + 624m - 624 + 29 = 4n^2 - 12n + 8 + 8n - 8 +
  709

which reduces down to

  400m^2 - 576m + 205 = 4n^2 - 4n + 709

Now, if all of the above is correct, completing the square for both 
sides I will get a fraction which I wish to avoid and after viewing 
http://mathforum.org/library/drmath/view/53107.html I can avoid 
fractions by multiplying the equation by 4 times the quadratic 
coefficient which gives me:

1st Sequence

  1600(400m^2 - 576m + 205)
  640000m^2 - 921600m + 328000
  640000m^2 - 921600m = -328000
  (800m - 576)^2 = -328000 + 331776 or 3776
  (800m - 576)^2 - 3776

2nd sequence:

  16(4n^2 - 4n + 709)
  64n^2 - 64n + 11344
  64n^2 - 64n = -11344
  (8n - 4)^2 = -11344 + 16 or -11328
  (8n - 4)^2 + 11328

so:

  (800m - 576)^2 - 3776 = (8n - 4)^2 + 11328

rearranging this to make a difference of squares I get:

  (800m - 576)^2 - (8n - 4)^2 = 15104

then factoring the difference of squares I get:

  (800m - 576 - 8n + 4)(800m - 576 + 8n - 4) = 15104

or

  (800m - 8n - 572)(800m + 8n - 580) = 15104

The factors of 15104 are
 
  1,2,4,8,16,32,59,64,118,128,236,256,472,944,1888,3776,7552, -1,....


  800m - 8n - 572 =
  800m + 8n - 580 =

Where m = 3 and n = 19 the two equations result in:

  2400 - 152 - 572 = 1676
  2400 + 152 - 580 = 1972

Neither of these results are factors of 15104.

Thanks for your help.

- Bob

Date: 08/05/2007 at 16:38:53
From: Doctor Vogler
Subject: Re: The nth term of two sequences

Hi Bob,

Thanks for writing to Dr Math.  I'm impressed by your effort!  You did
a good job working out this problem.  There was only one mistake, and
it was a subtle one that came up because of trying to apply the
completing the squares method to both sides of the equation.  The
problem was that you multiplied the left side and the right side by
different numbers.  You had

  400m^2 - 576m + 205 = 4n^2 - 4n + 709

and then you multiplied the left side by 1600 which turns it into

  (800m - 576)^2 - 3776

and then you multiplied the right side by 16 which turns it into

  (8n - 4)^2 + 11328.

But if you multiply two equal numbers by different amounts, then you
usually get unequal numbers.  You can still multiply in order to make
completing the square easier (i.e. not requiring fractions), but you
have to multiply both sides by the same number.  In fact, since
1600/16 is a square, you can just use 1600.

  1600(400m^2 - 576m + 205) = 1600(4n^2 - 4n + 709)

  1600(400m^2 - 576m + 205) = 10^2 * 16(4n^2 - 4n + 709)

  (800m - 576)^2 - 3776 = 10^2 * ( (8n - 4)^2 + 11328 ).

  (800m - 576)^2 - 3776 = (80n - 40)^2 + 1132800.

and then you can rewrite this as a difference of squares, just like
you did.  But, in fact, you don't need to multiply by as large a
number as 1600.  On the other hand, once you've completed the squares,
you don't have to start over again either.  You can just take the
equation you ended up with and start dividing out common factors. 
This will allow you to have fewer factors to check in the end (when
you factor the number on the right side).  For example, we can divide
both sides of the equation by 8^2

  (100m - 72)^2 - 59 = (10n - 5)^2 + 17700.

I'll let you finish up from there, as you seem quite capable of doing
so, but if you have any questions about this or need more help, please
write back and show me what you have been able to do, and I will try
to offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 08/12/2007 at 10:55:50
From: Bob
Subject: Thank you (The nth term of two sequences)

Doctor Vogler,

Thank you for straightening that out for me.  I guess I should have
realized that myself as far as if both sides of the equation are 
equal, to maintain equality you have to treat each side equally.

Thanks again for all of your help.

- Bob