0

I have the following series, infinitely long.

1 2 4 7 11 16 22 29 37.....

and I need to find a given number (say, N) whether it exists in this series or, not. The number again can be input any number of times and can be not-surprisingly, a long long value. Considering the series is infinite, I thought it irrelevant to create a data structure to store the elements(am I too dumb here?)

Took a closer look in this series, and i found that the difference between consecutive terms form an Arithmetic progression.

1 2 3 4 5 6 7 8.....

So, one easiest way would be keep on adding them starting from 1 and if we reach ==N, output Yes, else if >N, No. But this will be the costliest algorithm of what I can think of. I must be missing some very acute logic, but not sure.

susenj
  • 342
  • 1
  • 4
  • 12
  • 7
    Hint: there's a simple formula for the terms of this sequence, which you can invert to find whether there's an integer index corresponding to `N` or not. – DSM Dec 29 '14 at 04:57
  • @iharob: Yes, the list is sorted. As I mentioned, I can't think of any data structure to store them because the list is infinite, and hence searching after storing them would not be feasible; Next thing I could do to have a linear search, but that doesn't seem to contribute here well w.r.t. time. – susenj Dec 29 '14 at 05:06
  • @susenj just give it some thought about the formula mentioned by DSM. – Iharob Al Asimi Dec 29 '14 at 05:10
  • Hint: compare the sequence with triangles. – icedwater Dec 29 '14 at 05:29
  • 1
    If this is a homework question, you could mess with your prof by picking a large degree and fitting a polynomial of that degree to this meagre set of size 9. – Pradhan Dec 29 '14 at 05:53

3 Answers3

3

according to this series, T(n) - n'th number in series.

T(1) = 1

T(2) - T(1) = 1

T(3) - T(2) = 2

T(4) - T(3) = 3

.

.

.

T(n) - T(n - 1) = n - 1

//sum of all above

T(n) - T(1) = 1 + 2 + 3 + 4 + 5 + ... + (n - 2) + (n - 1)

//T(1) = 1

T(n) - 1 = n(n - 1) / 2 

2 * (T(n) - 1) = n^2 - n

//T(n) is your input number and check whether n has an integer 
//solutions in following quadratic equation, if yes T(n) is in this series. 

n^2 - n - 2 * (number - 1) = 0;


simply check if the value of " (1 + sqrt((8.0 * number) - 7)) / 2.0 " is integer.

Checking if float is an integer

Community
  • 1
  • 1
snvrthn
  • 385
  • 1
  • 10
0

There is no need of storing the series in any Data structure. You can use formula :

(n * (n + 1) / 2) + 1 = x

where x is the no. you want to search. If any real root exist to this equation then "X" exits. example : 16 

(n * (n + 1) / 2) + 1 = 16
Manjunath N
  • 1,365
  • 11
  • 22
SeeTheC
  • 1,560
  • 12
  • 14
0

The sequence

1, 2, 4, 7, 11, 16, ...

is 1 removed from

0, 1, 3, 6, 10, 15, ...

which in turn is

0, 0+1, 0+1+2, 0+1+2+3, 0+1+2+3+4, 0+1+2+3+4+5, ...

To find if N is in the sequence, you just need to check if N-1 is the sum of a sequence of natural numbers, i.e. if there exists a p for which 1 + 2 + ... + p-1 + p == N-1.

icedwater
  • 4,701
  • 3
  • 35
  • 50