0
$\begingroup$

I hope I can ask this question with enough clarity. It is not exactly clear in my head., but here goes

I have a number series, it starts at a random number and then increments by 8(always by 8) plus the last number.

for example in the series:

36,80,132,192,260,336,420,512,612,720,836,960

We start at 36 (randomly chosen)

We then add 8 to 36 to make 44

We then add 44 to 36 to make the next number in the series 80

Then we add 8 to 44 to make 52 and add that to 80 to make the next number in the series 132

So we have two sets of numbers one which is incrementing by 8 the other which is the addition of the incrementing numbers.

 36, 44, 52, 60, 68, 76, 84, 92,100,108,116,124
 36, 80,132,192,260,336,420,512,612,720,836,960 <== target series

Now I want to test whether another number exists in that series for example we can see that 612 is valid for that series but 680 is not.

Is the number 6992 a valid number for that series?

What about 500345264?

Is there a way I can test for validity without having to calculate every number in the series up until the one I want?

Is there a way I can count how many iterations I'd need to go through to get to the number. For example 612 is the 8th iteration.

This is part of a programming task (not school work but special interest) I will have tens of millions of these to calculate and I want the program to run as fast and as efficiently as possible.

So any help will be appreciated. If it can't be done then so be it, but not being a mathematician I thought I better ask before I gave up.

DC

$\endgroup$
1
  • 1
    $\begingroup$ Your sequence is determined by the recurrence relation $a_{n+1} = a_n + a_0 + 8(n+1)$. $\endgroup$ Nov 15 '13 at 13:11
2
$\begingroup$

As mentioned by Antonio, the recurrence relation that defines this sequence is: $$ a_n = a_{n-1} + a_0 + nb \,, $$ where in the example above $a_0 = 36$ and $b=8$. A little thought will show that, generally, $$ a_n = (n+1)a_0 + b\sum_{k=1}^n k = (n+1)a_0 + \frac{n(n+1)}{2}b \,. $$ This can be proved simply by induction but was deduced by considering the following: $$ a_0 = a_0 \\ a_1 = a_0 + a_0 + b = 2a_0 + b \\ a_2 = a_1 + a_0 + 2b = (2a_0 + b) + a_0 + 2b = 3a_0 + (1+2)b \\ a_3 = a_2 + a_0 + 3b = (3a_0 + (1+2)b) + a_0 + 3b = 4a_0 + (1+2+3)b \\ \ldots \\ a_n = (n+1)a_0 + b\sum_{k=1}^n k $$ Now that we have a formula to compute the $n$th number in the sequence without computing the previous numbers we can formulate a way to test any number to see if it is in the sequence by solving this for $n$, which results in the following quadratic equation: $$ \frac{b}{2}n^2 + \left(\frac{b}{2} + a_0\right)n + (a_0 - a_n) = 0\,, $$ where $a_n$ is the number you wish to test. If you solve for $n$ using the quadratic formula and one of the solutions is a non-negative integer then $a_n$ is in the sequence. Be careful implementing this to see if this is an integer because floating point arithmetic can be imprecise.

$\endgroup$
1
  • $\begingroup$ I can't thank you enough for this. It is exactly what I was hoping for. $\endgroup$ Nov 16 '13 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.