Ma · Mathematics

Closed Forms for Sums Involving Floor Logarithms

Published By the 9to5Science editorial team

At a glance

  1. 1. Fix the variables

    Decide whether the logarithm’s base or its argument changes with the summation index.

  2. 2. Use a threshold count

    The floor counts how many positive integer powers of the base do not exceed the argument.

  3. 3. Sum the counts

    Count the indices meeting each power threshold, then simplify the finite sum.

  4. 4. Check endpoints

    Include equality at each power; it is what makes the floor increase at that index.

The notation “floor(logₙ)” is incomplete unless you know what the logarithm’s argument is and whether its base changes with the summation index. Two common sums are ∑k=1N⌊log⁡bk⌋\sum_{k=1}^N\lfloor\log_b k\rfloor, with a fixed base bb, and ∑k=2N⌊log⁡kN⌋\sum_{k=2}^N\lfloor\log_k N\rfloor, with a changing base. They have different formulas. The fixed-base sum has a simple geometric closed form; the changing-base sum is naturally written using integer roots.

Fixed base: sum of floor(log base b of k)

Let b≥2b\ge 2 and N≥1N\ge 1 be integers, and define

S(N)=∑k=1N⌊log⁡bk⌋.S(N)=\sum_{k=1}^{N}\left\lfloor\log_b k\right\rfloor.

Set m=⌊log⁡bN⌋m=\lfloor\log_b N\rfloor. For each kk, the value ⌊log⁡bk⌋\lfloor\log_b k\rfloor counts the positive integers jj for which bj≤kb^j\le k. Reversing the order of counting gives

S(N)=∑j=1m#{k:1≤k≤N, bj≤k}=∑j=1m(N−bj+1)=m(N+1)−∑j=1mbj.\begin{aligned} S(N) &=\sum_{j=1}^{m}\#\{k:1\le k\le N,\ b^j\le k\}\\ &=\sum_{j=1}^{m}(N-b^j+1)\\ &=m(N+1)-\sum_{j=1}^{m}b^j. \end{aligned}

Using the geometric-series identity ∑j=1mbj=(bm+1−b)/(b−1)\sum_{j=1}^{m}b^j=(b^{m+1}-b)/(b-1) gives

∑k=1N⌊log⁡bk⌋=m(N+1)−bm+1−bb−1,m=⌊log⁡bN⌋.\boxed{\displaystyle \sum_{k=1}^{N}\left\lfloor\log_b k\right\rfloor =m(N+1)-\frac{b^{m+1}-b}{b-1}, \qquad m=\left\lfloor\log_b N\right\rfloor.}

An equivalent form is mN−(bm+1−b)/(b−1)+mmN-(b^{m+1}-b)/(b-1)+m. If the base is not an integer, the threshold-counting identity still applies, but use ⌈bj⌉\lceil b^j\rceil as the first integer kk satisfying k≥bjk\ge b^j:

S(N)=∑j=1⌊log⁡bN⌋(N−⌈bj⌉+1).S(N)=\sum_{j=1}^{\lfloor\log_b N\rfloor}(N-\lceil b^j\rceil+1).

Worked example: base 2, upper limit 20

Here m=⌊log⁡220⌋=4m=\lfloor\log_2 20\rfloor=4. Therefore

∑k=120⌊log⁡2k⌋=4(20+1)−(2+4+8+16)=84−30=54.\begin{aligned} \sum_{k=1}^{20}\lfloor\log_2 k\rfloor &=4(20+1)-(2+4+8+16)\\ &=84-30\\ &=54. \end{aligned}

You can check this by grouping the terms by their floor value. The value is 1 for k=2,3k=2,3, 2 for k=4,…,7k=4,\ldots,7, 3 for k=8,…,15k=8,\ldots,15, and 4 for k=16,…,20k=16,\ldots,20. Thus the sum is 2⋅1+4⋅2+8⋅3+5⋅4=542\cdot1+4\cdot2+8\cdot3+5\cdot4=54; the k=1k=1 term is zero.

If the base changes with the index

If you meant

T(N)=∑k=2N⌊log⁡kN⌋,T(N)=\sum_{k=2}^{N}\left\lfloor\log_k N\right\rfloor,

then count pairs (k,j)(k,j) satisfying kj≤Nk^j\le N. For a fixed exponent jj, the possible integer bases are 2≤k≤⌊N1/j⌋2\le k\le\lfloor N^{1/j}\rfloor. There are ⌊N1/j⌋−1\lfloor N^{1/j}\rfloor-1 such bases. No exponent above ⌊log⁡2N⌋\lfloor\log_2 N\rfloor contributes, so

T(N)=∑j=1⌊log⁡2N⌋(⌊N1/j⌋−1).\boxed{\displaystyle T(N)=\sum_{j=1}^{\lfloor\log_2 N\rfloor}\left(\left\lfloor N^{1/j}\right\rfloor-1\right).}

For example, with N=20N=20, the contributions for j=1,2,3,4j=1,2,3,4 are 19,3,1,119,3,1,1, respectively. Hence T(20)=24T(20)=24. This is an exact finite formula, though it is not usually simplified to a single geometric expression.

Common mistakes

  • Mixing up the base and argument. In log⁡bk\log_b k, bb is fixed and kk varies. In log⁡kN\log_k N, the base varies instead.
  • Dropping the endpoint. The condition is bj≤kb^j\le k, not bj<kb^j<k. At an exact power, the floor has already increased. For integer bb, the number of qualifying indices is N−bj+1N-b^j+1.
  • Starting the exponent count at zero. The j=0j=0 threshold is b0=1b^0=1 and contributes nothing to the floor; only positive exponents need to be counted.
  • Calling the answer one formula without stating the sum. Write the summation limits and identify which symbol is the logarithm’s base before applying a closed form.

If your intended expression uses a different argument or summation range, substitute it into the threshold-counting method: identify when the floor reaches each integer level, then count the indices at or above that threshold.

References

  1. Concrete Mathematics: A Foundation for Computer Science, Ronald L. Graham, Donald E. Knuth, and Oren Patashnik

Spotted an error? Send a correction. Read how we write and check articles in our editorial policy.