Finding sum in less than O(N)

Question

Question: In less O(n) find a number K in sequence 1,2,3...N such that sum of 1,2,3...K is exactly half of sum of 1,2,3..N

Maths: I know that the sum of the sequence 1,2,3....N is N(N+1)/2.

Therefore our task is to find K such that: K(K+1) = 1/2 * (N)(N+1)/2 if such a K exists.

Pseudo-Code:

sum1 = n(n+1)/2
sum2 = 0

for(i=1;i<n;i++)
{
    sum2 += i;
    if(sum2 == sum1)
    {
        index = i
        break;
    }
}

Problem: The solution is O(n) but I need better such as O(n), O(log(n))...

Answer 1

You're close with your equation, but you dropped the divide by 2 from the K side. You actually want

K * (K + 1) / 2 = N * (N + 1) / (2 * 2)

Or

2 * K * (K + 1) = N * (N + 1)

Plugging that into wolfram alpha gives the real solutions:

K = 1/2 * (-sqrt(2N^2 + 2N + 1) - 1)
K = 1/2 * (sqrt(2N^2 + 2N + 1) - 1)

Since you probably don't want the negative value, the second equation is what you're looking for. That should be an O(1) solution.

Answer 2

The other answers show the analytical solutions of the equation

k * (k + 1) = n * (n + 1) / 2            Where n is given

The OP needs k to be a whole number, though, and such value may not exist for every chosen n.

We can adapt the Newton's method to solve this equation using only integer arithmetics.

sum_n =  n * (n + 1) / 2
k = n
repeat indefinitely         // It usually needs only a few iterations, it's O(log(n))
    f_k = k * (k + 1)
    if  f_k == sum_n
        k is the solution, exit
    if  f_k < sum_n
        there's no k, exit 
    k_n = (f_k - sum_n) / (2 * k + 1)   // Newton step: f(k)/f'(k) 
    if  k_n == 0
        k_n = 1   // Avoid inifinite loop
    k = k - k_n;

Here there is a C++ implementation.

---

We can find all the pairs (n, k) that satisfy the equation for 0 < k < n ≤ N adapting the algorithm posted in the question.

n = 1                        // This algorithm compares 2 * k * (k + 1) and n * (n + 1)
sum_n = 1                    // It finds all the pairs (n, k) where 0 < n ≤ N in O(N)
sum_2k = 1
for every n <= N             // Note that n / k → sqrt(2) when n → ∞
    while  sum_n < sum_2k
        n = n + 1            // This inner loop requires a couple of iterations,
        sum_n = sum_n + n    // at most.
   
    if ( sum_n == sum_2k )
        print n and k
   
    k = k + 1
    sum_2k = sum_2k + 2 * k

Here there is an implementation in C++ that can find the first pairs where N < 200,000,000:

           N           K           K * (K + 1)
----------------------------------------------
           3           2                     6
          20          14                   210
         119          84                  7140
         696         492                242556
        4059        2870               8239770
       23660       16730             279909630
      137903       97512            9508687656
      803760      568344          323015470680
     4684659     3312554        10973017315470
    27304196    19306982       372759573255306
   159140519   112529340     12662852473364940

Of course it becomes impractical for too large values and eventually overflows.

Besides, there's a far better way to find all those pairs (have you noticed the patterns in the sequences of the last digits?).

We can start by manipulating this Diophantine equation:

2k(k + 1) = n(n + 1)
                                   introducing   u = n + 1   →   n = u - 1
                                                 v = k + 1       k = v - 1
2(v - 1)v = (u - 1)u
2(v2 - v) = u2 + u
2(4v2 - 4v) = 4u2 + 4u
2(4v2 - 4v) + 2 = 4u2 - 4u + 2
2(4v2 - 4v + 1) = (4u2 - 4u + 1) + 1
2(2v - 1)2 = (2u - 1)2 + 1
                                 substituting   x = 2u - 1   →   u = (x + 1)/2
                                                y = 2v - 1       v = (y + 1)/2

2y2 = x2 + 1
x2 - 2y2 = -1

Which is the negative Pell's equation for 2.

It's easy to find its fundamental solutions by inspection, x₁ = 1 and y₁ = 1. Those would correspond to n = k = 0, a solution of the original Diophantine equation, but not of the original problem (I'm ignoring the sums of 0 terms).

Once those are known, we can calculate all the other ones with two simple recurrence relations

xi+1 = xi + 2yi
yi+1 = yi + xi

Note that we need to "skip" the even ys as they would lead to non integer solutions. So we can directly use theese

xi+2 = 3xi + 4yi   →   ui+1 = 3ui + 4vi - 3  →   ni+1 = 3ni + 4ki + 3
yi+2 = 2xi + 3yi       vi+1 = 2ui + 3vi - 2      ki+1 = 2ni + 3ki + 2

Summing up:

                    n                         k
-----------------------------------------------
3* 0 + 4* 0 + 3 =   3      2* 0 + 3* 0 + 2 =  2  
3* 3 + 4* 2 + 3 =  20      2* 3 + 3* 2 + 2 = 14  
3*20 + 4*14 + 3 = 119      2*20 + 3*14 + 2 = 84  
...

Answer 3

It seems that the problem is asking to solve the diophantine equation

2K(K+1) = N(N+1).

By inspection, K=2, N=3 is a solution !

---

Note that technically this is an O(1) problem, because N has a finite value and does not vary (and if no solution exists, the dependency on N is even meanignless).

Answer 4

The condition you have is that the sum of 1..N is twice the sum of 1..K

So you have N(N+1) = 2K(K+1) or K^2 + K - (N^2 + N) / 2 = 0

Which means K = (-1 +/- sqrt(1 + 2(N^2 + N)))/2

Which is O(1)