Divide and conquer on a geometric sum

September 12, 2026 · algorithms

I wanted (1-r^{n+1})/(1-r). Mod does not keep that division. Cut the series in the middle: two copies of a shorter sum, O(log n).

I was summing a geometric series today:

s(n) = \sum_{k=0}^{n} r^{k} = 1 + r + r^{2} + \cdots + r^{n},

then taking that modulo $N$ .

Closed form

My first reaction was: isn’t there a formula? Just use it. If $r \neq 1$ ,

s(n) = \frac{1 - r^{n+1}}{1 - r}.

That formula divides by $1-r$ . Congruence does not preserve division, so this is not a method for $s(n) \bmod N$ .

Linear scan

The naive thing: start from $1$ , keep multiplying by $r$ , add into the running total. There are $n+1$ terms, so $O(n)$ .

int geometric_sum_naive(int ratio, int max_exponent) {
  int total = 0;
  int current_term = 1;
  for (int exponent = 0; exponent <= max_exponent; ++exponent) {
    total += current_term;
    current_term *= ratio;
  }
  return total;
}

Divide and conquer

There is a smarter way, and this is divide and conquer as I see it. Cut the series in the middle, into two equal pieces.

When $n$ is odd, $n+1$ is even. Set $m = (n+1)/2$ . Then $s(n)$ has $2m$ terms, so it splits into two blocks of length $m$ :

\begin{aligned} s(n) &= \sum_{k=0}^{m-1} r^{k} + \sum_{k=m}^{2m-1} r^{k} \\ &= \sum_{k=0}^{m-1} r^{k} + r^{m} \sum_{k=0}^{m-1} r^{k} \\ &= \bigl(1 + r^{m}\bigr)\, s(m-1). \end{aligned}

Since $m = (n+1)/2$ , this is

s(n) = \bigl(1 + r^{(n+1)/2}\bigr)\, s\bigl(\tfrac{n-1}{2}\bigr).

The problem $s(n)$ shrinks to $s((n-1)/2)$ . Half the input.

When $n$ is even, set $m = n/2$ . Now $s(n)$ has $2m+1$ terms, so the same two blocks of length $m$ leave a last term $r^{n}$ :

\begin{aligned} s(n) &= \sum_{k=0}^{m-1} r^{k} + r^{m} \sum_{k=0}^{m-1} r^{k} + r^{n} \\ &= \bigl(1 + r^{m}\bigr)\, s(m-1) + r^{n} \\ &= \bigl(1 + r^{n/2}\bigr)\, s\bigl(\tfrac{n}{2} - 1\bigr) + r^{n}. \end{aligned}

Half again.

So the recurrence is

s(n) = \begin{cases} \bigl(1 + r^{(n+1)/2}\bigr)\, s\bigl(\tfrac{n-1}{2}\bigr) & \text{if } n \text{ is odd,} \\[0.4em] \bigl(1 + r^{n/2}\bigr)\, s\bigl(\tfrac{n}{2} - 1\bigr) + r^{n} & \text{if } n \text{ is even,} \end{cases}

with base $s(1) = 1 + r$ , of course.

That brings the time down to $O(\log n)$ . Remember the $r^{k}$ pieces: binary exponentiation is also $O(\log n)$ , so it does not change the overall time.

const int kModulus = 10000;

int pow_mod(int base, int exponent) {
  int result = 1;
  int base_power = base;
  while (exponent > 0) {
    bool is_odd = (exponent & 1) == 1;
    exponent >>= 1;
    if (is_odd) {
      result = (result * base_power) % kModulus;
    }
    base_power = (base_power * base_power) % kModulus;
  }
  return result;
}

int geometric_sum(int ratio, int max_exponent) {
  if (max_exponent == 1) {
    return 1 + ratio;
  }

  if (max_exponent % 2 == 1) {
    return (1 + pow_mod(ratio, (max_exponent + 1) / 2)) *
           geometric_sum(ratio, (max_exponent - 1) / 2);
  }

  return ((1 + pow_mod(ratio, max_exponent / 2)) *
          geometric_sum(ratio, (max_exponent / 2) - 1)) +
         pow_mod(ratio, max_exponent);
}