Problem 179: Consecutive Positive Divisors

Mathematical Analysis

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$:

Solution Approaches

Approach 1: Divisor Sieve (Primary)

1. Initialize $d[1 \ldots N] = 0$.
2. For $k = 1$ to $N+1$: increment $d[j]$ for all multiples $j \leq N+1$.
3. Count $n$ where $d[n] = d[n+1]$ for $2 \leq n < 10^7$.

Approach 2: SPF Sieve (Faster)

1. Compute smallest prime factor via linear sieve.
2. Factorize each $n$ and compute $d(n) = \prod(e_i + 1)$.
3. Count consecutive equal values.

Approach 3: Brute Force Factorization

For each $n$, trial-divide to find the prime factorization and compute $d(n)$. Time: $O(N \sqrt{N})$ — too slow.

Proof of Correctness

The divisor sieve correctly counts divisors: each $k$ contributes exactly 1 to $d[j]$ for every multiple $j$ of $k$. By definition, $d(n) = |\{k : k \mid n\}|$, and the sieve iterates over all $(k, j)$ pairs with $k \mid j$.

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)