Project Euler Problem 179

Solution

Answer: 986262

Let $d(n)$ denote the number of positive divisors of $n$.

We seek the count of integers

$$1<n<10^7$$

such that

$$d(n)=d(n+1).$$

---

Mathematical analysis

For any integer with prime factorization

$$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},$$

the divisor-count function is

$$d(n)=(a_1+1)(a_2+1)\cdots(a_k+1).$$

Example:

$$14=2^1\cdot 7^1$$

so

$$d(14)=(1+1)(1+1)=4.$$

Similarly,

$$15=3^1\cdot5^1$$

so

$$d(15)=4.$$

Thus $14$ and $15$ qualify.

---

Brute force is impossible

A naive approach would:

1. Factor every $n\le 10^7$,
2. Compute $d(n)$,
3. Compare consecutive values.

Factoring each number independently up to $10^7$ would be far too slow.

We need a sieve-style method.

---

Efficient divisor sieve

The key observation is:

If we initialize an array

$$d[0],d[1],\dots,d[N]$$

with zeros, then every integer $i$ contributes $1$ divisor to each multiple of $i$.

Indeed, $i$ divides exactly:

$$i,2i,3i,\dots$$

Therefore we can compute divisor counts using:

for i in 1..N:
    for multiple in i,2i,3i,...:
        d[multiple] += 1

This is analogous to the Sieve of Eratosthenes.

---

Complexity

The total work is

$$\sum_{i=1}^N \frac{N}{i} = N\sum_{i=1}^N \frac1i \approx N\log N.$$

For $N=10^7$, this is feasible in optimized Python/PyPy.

Memory usage:

• one integer array of size $10^7+1$.

---

Python implementation

# Project Euler 179
# Count integers 1 < n < 10^7 such that
# n and n+1 have the same number of divisors.

LIMIT = 10**7

# divisor_count[n] will store d(n)
divisor_count = [0] * (LIMIT + 2)

# Sieve to compute number of divisors for every n
for i in range(1, LIMIT + 1):
    for multiple in range(i, LIMIT + 1, i):
        divisor_count[multiple] += 1

# Count consecutive integers with equal divisor counts
answer = 0

for n in range(2, LIMIT):
    if divisor_count[n] == divisor_count[n + 1]:
        answer += 1

print(answer)

---

Code walkthrough

Step 1 — Create divisor array

divisor_count = [0] * (LIMIT + 2)

We allocate space for divisor counts.

Initially every number has divisor count $0$.

---

Step 2 — Divisor sieve

for i in range(1, LIMIT + 1):

Treat $i$ as a divisor.

---

for multiple in range(i, LIMIT + 1, i):

Iterate through all multiples of $i$.

Since $i\mid multiple$, we increment the divisor count:

divisor_count[multiple] += 1

After all loops finish:

$$\text{divisor_count}[n]=d(n).$$

---

Step 3 — Compare neighbors

for n in range(2, LIMIT):

This checks

$$2 \le n \le 9,999,999.$$

---

if divisor_count[n] == divisor_count[n + 1]:

If consecutive integers have the same divisor count, increment the answer.

---

Small example verification

For numbers up to $15$:

$n$	$d(n)$
14	4
15	4

So $14$ qualifies.

The algorithm correctly detects this because both entries in the sieve become $4$.

---

Final verification

The answer should be:

• positive,
• on the order of millions (since equal divisor counts occur fairly often),
• well below $10^7$.

The known computed result from the sieve is:

$$986262$$

which is consistent with expected density.

Answer: 986262