Detailed mathematical approach

Problem Summary

We must count the integers \(n\) with \(1<n<10^7\) such that \(n\) and \(n+1\) have the same number of positive divisors. If \(d(m)\) denotes the divisor-count function, the required quantity is

$A=\sum_{n=2}^{10^7-1}\mathbf{1}_{d(n)=d(n+1)}.$

Consecutive integers are always coprime, so this is not a question about two numbers sharing prime factors. Instead, it asks when two different factorizations happen to produce the same divisor count. The implementations therefore avoid factoring one pair at a time and compute the whole divisor-count table in a single structured pass.

Mathematical Approach

The problem is governed by the arithmetic function \(d(m)\), also written \(\tau(m)\). If

$m=\prod_{i=1}^{r} p_i^{a_i},$

then the number of positive divisors is

$d(m)=\prod_{i=1}^{r}(a_i+1).$

This explains why neighboring integers can still tie. For example, \(14=2^1\cdot 7^1\) and \(15=3^1\cdot 5^1\), so both have \(4\) divisors even though \(\gcd(14,15)=1\).

The identity behind the sieve

Factoring each integer separately would repeat the same work many times. The key observation used by all three implementations is the equivalent identity

$d(m)=\sum_{k\mid m} 1=\sum_{k=1}^{10^7+1}\mathbf{1}_{k\mid m}.$

For a fixed candidate divisor \(k\), the integers divisible by \(k\) are exactly

$k,2k,3k,\dots.$

So if an array starts at zero and we add \(1\) to every multiple of \(k\), then \(k\) contributes exactly once to each number it divides and never contributes to numbers it does not divide.

The loop invariant

After the outer loop has processed \(1,2,\dots,D\), the table entry at \(m\) equals

$c_D(m)=\sum_{k=1}^{D}\mathbf{1}_{k\mid m}.$

That is the number of divisors of \(m\) that are at most \(D\). Whenever \(m\le D\), every positive divisor of \(m\) has already appeared, so \(c_D(m)=d(m)\). By running the sieve through \(10^7+1\), the implementations guarantee that every entry needed in the final comparison stage already stores the exact divisor count.

Worked example: \(14\) and \(15\)

The factorization formula gives

$14=2^1\cdot 7^1,\qquad 15=3^1\cdot 5^1,$

hence

$d(14)=(1+1)(1+1)=4,\qquad d(15)=(1+1)(1+1)=4.$

The sieve sees the same fact from a different angle: the entry for \(14\) is incremented by the passes for \(1,2,7,14\), while the entry for \(15\) is incremented by the passes for \(1,3,5,15\). Once the table has been filled, the pair \((14,15)\) is recognized automatically as a match.

From divisor counts to the final answer

After the sieve, nothing subtle remains. The answer is simply the number of adjacent equalities in the divisor-count sequence:

$A=\#\{n:2\le n<10^7,\ d(n)=d(n+1)\}.$

So the second phase is a linear scan through neighboring entries. This is the right mathematical reduction for Problem 179: build the global sequence \(d(1),d(2),\dots,d(10^7)\) once, then test adjacency.

How the Code Works

Building the divisor-count table

The C++, Python, and Java implementations allocate an array that covers the needed range and initialize it with zeros. The outer loop selects a divisor candidate \(d\), and the inner loop visits every multiple of \(d\), adding one at each visited position. In array form, this realizes the identity \(d(m)=\sum_{k\mid m}1\) for all \(m\) simultaneously instead of recomputing it number by number.

The C++ implementation also includes a small checkpoint at \(100\): in that shorter range, the correct count is \(15\). That sanity check confirms that the sieve and the final scan agree on a case that is easy to verify independently.

Counting consecutive matches

Once the table is complete, the implementation performs a single pass over \(n=2,3,\dots,10^7-1\). Whenever the counts at \(n\) and \(n+1\) are equal, it increments the answer. The three language versions are mathematically identical here; they differ only in syntax and in the concrete container types used to store the table.

Complexity Analysis

The sieve performs

$\sum_{d=1}^{10^7+1}\left\lfloor\frac{10^7+1}{d}\right\rfloor$

array updates, because divisor \(d\) touches each of its multiples exactly once. This is a harmonic sum, so the running time is \(O(N\log N)\) with \(N=10^7\), more precisely \(N\log N+O(N)\).

The final adjacency scan is \(O(N)\), which does not change the overall asymptotic cost. Memory usage is \(O(N)\) for the divisor-count table. That tradeoff is exactly what makes the problem practical: one global sieve and one linear pass replace millions of repeated factorizations.

Footnotes and References

1. Project Euler Problem 179: https://projecteuler.net/problem=179
2. Divisor function: Wikipedia - Divisor function
3. Prime factorization: Wikipedia - Prime factorization
4. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes
5. Harmonic series: Wikipedia - Harmonic series