CODEWITHSUNDEEP
algorithmsequence
PengOne
PengOne

Reputation: 48398

General method to fit a number into a sequence

The general problem is as follows. Given an increasing sequence of positive integers 0 < s_1 < s_2 < s_3 < ... and a positive integer n, is there an efficient algorithm to find the (unique) index k such that s_k <= n < s_(k+1)?

A concrete example of this problem with a particular nice solution is to find the largest nonzero digit of a binary expansion, i.e. take s_i = 2^(i-1), and then k = log_2(n).

A slightly harder example is to find the largest nonzero digit in the factorial expansion, i.e. take s_i = i!.

The example that I have in mind that brings up this question is the following:

s_i = ith triangular number = 1 + 2 + ... + i = i(i+1)/2

I'd like a nice solution to this, meaning something better than the following

for(int i=1; ; ++i) {
  if (triangle[i] > n)
    break;
}
return i;

NOTE: One cannot use a binary search here since the sequence is infinite. Of course, there is the obvious constraint that k <= n, but this is a horrible bound in general. For example, if s_i = i!, then using a binary search on n=20 requires computing 20! when the answer is k=3, so one shouldn't need to compute beyond 4!.

Upvotes: 0

Views: 88

Answers (1)

Eyal Schneider
Eyal Schneider

Reputation: 22446

A general approach: Try solving the equation n = s(x) and the set k = floor(x).

For s_i=2^(i-1) you get x=log2(n)+1. For s_i=i*(i+1)/2 you get x=(sqrt(1+8n)-1)/2.

In case that the equation is not solvable analytically, try an approximation (e.g. Newton's method), or simply use a binary search on the sequence.

Upvotes: 1

Related Questions