How to make this function process in constant time?

Question

I need to find the n-th term of this infinite series: 1,2,2,3,3,3,4,4,4,4...

Can you give me a constant time function for this task?

int i = 1;
while(true)
{
   if(i = n)
      //do things and exit the loop

   i++;
}

I think this isn`t going to be a constant time function...

Answer 1

Edit

After reading more comments, it appears I misunderstood the question.

If you want to find the item at nth position an array in constant time, then the answer is trivial: x[n], because array access is constant time. However, if for some reason you were using some container where access time is not constant (e.g. linked list), or did not want to look up value in the array, you'd have to use the arithmetic series formulas to find the answer.

Arithmetic series tells us that the position n of the ith unique item would be

n = i * (i - 1) / 2

So we just need to solve for i. Using quadratic formula, and discarding the nonsensical negative option, we get:

i = Math.Floor( (1 + Math.Sqrt(1 + 8 * n)) / 2)

Original Response

I'm assuming you're looking for the position of the nth unique term, because otherwise the problem is trivial.

Sounds like the first occurrence of the nth unique term should follow arithmetic series. I.e. the position of nth unique term would be:

n * (n - 1) / 2

Answer 2

Given my understanding of the problem, this is more of a math problem than a programming one.

If the problem is:

Given an infinite series that consists of 1 copy of 1, 2 copies of 2, 3 copies of 3... n copies of n, what is the kth value in this series?

Now the first clue when approaching this problem is that there are 1 + 2 + 3... + n values before the first occurance of n + 1. Specifically there are (sum of the first n numbers) values before n+1, or (n)(n-1)/2.

Now set (n)(n-1)/2 = k. Multiply out and rationalize to n^2 - n - 2k = 0. Solve using quadratic equation, you get n = (1 + sqrt(1+8k))/2. The floor of this gives you how many full copies of n there are before, and happily, given zero based indexing, the floor gives you the value at the kth point in the array.

That means your final answer in c# is

return (int) Math.Floor((1 + Math.Sqrt(1 + 8 * k)) / 2);

Given non zero based indexing,

return (int) Math.Floor((1 + Math.Sqrt(-7 + 8 * k)) / 2);