Problem 179: Consecutive Positive Divisors

Mathematical Development

The Divisor Function

Definition. For $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, the divisor count function is:

Key properties:

1. $d$ is multiplicative: $d(mn) = d(m)d(n)$ when $\gcd(m,n) = 1$.
2. $d(p) = 2$ for any prime $p$.
3. $d(p^k) = k + 1$.
4. Highly composite numbers have many divisors: $d(720720) = 240$.

Computing $d(n)$ via Sieve

Method 1: Divisor sieve (O(N log N)). For each $k$ from 1 to $N$, increment $d[j]$ for all multiples $j = k, 2k, 3k, \ldots$. The harmonic series $\sum_{k=1}^{N} N/k = O(N \log N)$ gives the complexity.

Method 2: Smallest prime factor sieve (O(N)). Compute the smallest prime factor (SPF) for all $n \leq N$ using a linear sieve. Then for each $n$, factorize via repeated division by SPF and compute $d(n) = \prod(e_i + 1)$.

Density of Consecutive Equal Divisor Counts

Theorem (Erdos, 1936). The set of $n$ with $d(n) = d(n+1)$ has positive natural density. That is:

Empirically, this density is approximately $0.0986$, meaning about 9.86% of consecutive pairs have equal divisor counts.

Verification Table

Common Divisor Counts

The most common divisor counts for $n \leq 10^7$:

Editorial

The simplest workable approach is a divisor sieve. Instead of factorizing each number independently, the program lets every integer $k$ contribute one divisor count to each of its multiples. After this sweep, the array entry at position $n$ is exactly $d(n)$.

Once the divisor counts are available, the rest is just a linear scan through consecutive pairs. Every index $n$ with $2 \le n < 10^7$ is checked against $n+1$, and the answer is the number of times the two divisor counts match. The code also keeps a small brute-force verifier for tiny limits, but the main computation is entirely driven by the sieve.

Pseudocode

Create an array of divisor counts initialized to zero.

For each integer $k$ from 1 up to $10^7 + 1$:
    visit every multiple of $k$ within the array bounds
    and add 1 to that multiple's divisor count.

Initialize the answer to zero.
For each $n$ from 2 up to $10^7 - 1$:
    if the counts of $n$ and $n+1$ are equal,
    increase the answer.

Return the final count.

Complexity Analysis

• Divisor sieve: $O(N \log N)$ time, $O(N)$ space.
• SPF sieve: $O(N)$ time, $O(N)$ space.

For $N = 10^7$, the divisor sieve takes about 2 seconds in C++.

Answer

#include <bits/stdc++.h>
using namespace std;
int main() {
    const int N = 10000000;
    vector<int> d(N + 2, 0);
    for (int k = 1; k <= N + 1; k++)
        for (int j = k; j <= N + 1; j += k)
            d[j]++;
    int count = 0;
    for (int n = 2; n < N; n++)
        if (d[n] == d[n + 1]) count++;
    assert(count == 986262);
    cout << count << endl;
    return 0;
}

"""
Problem 179: Consecutive Positive Divisors
Count n in (1, 10^7) where d(n) = d(n+1).
"""

def solve_sieve(N: int = 10_000_000):
    d = [0] * (N + 2)
    for k in range(1, N + 2):
        for j in range(k, N + 2, k):
            d[j] += 1
    count = sum(1 for n in range(2, N) if d[n] == d[n + 1])
    return count, d

def solve_brute(N: int = 1000):
    def divisor_count(n):
        c = 0
        for d in range(1, n + 1):
            if n % d == 0: c += 1
        return c
    return sum(1 for n in range(2, N) if divisor_count(n) == divisor_count(n + 1))

# Verify small case
assert solve_brute(100) == sum(1 for n in range(2, 100)
    if sum(1 for d in range(1, n+1) if n%d==0) == sum(1 for d in range(1, n+2) if (n+1)%d==0))

answer, d = solve_sieve()
assert answer == 986262, f"Expected 986262, got {answer}"
print(answer)