Consecutive numbers that share the same sum of prime factors

1.5k Views Asked by At

Let $f(n)$ denote the sum of the prime factors of $n$ (with multiplicity).

I have been looking for pairs of consecutive numbers $n,n+1$ such that $f(n)=f(n+1)$.

Case #$1$:

  • $f(8)=f(2\cdot2\cdot2)=2+2+2=6$
  • $f(9)=f(3\cdot3)=3+3=6$

Case #$2$:

  • $f(15)=f(3\cdot5)=3+5=8$
  • $f(16)=f(2\cdot2\cdot2\cdot2)=2+2+2+2=8$

Are these the only two such pair of numbers to exist?

I think that it might be related to Catalan's conjecture.

2

There are 2 best solutions below

4
On BEST ANSWER

Note that $f(5) = 5 = 2 + 3 = f(2 \cdot 3) = f(6)$, so $(5, 6)$ is another such pair.

There are more, too: The pairs $(n, n + 1)$, $n < 1000$, that satisfy the criteria are $$(5, 6), (8, 9), (15, 16), (77, 78), (125, 126), (714, 715), (948, 949).$$ This (or perhaps the sequence of $n$) is the Ruth–Aaron sequence, so named because of the significance of those players w.r.t. the numbers $714$ and $715$ in baseball history. For more terms, see this list of the first $10^5$ $n$ satisfying the condition, or this list of the $\sim 4.4 \cdot 10^5$ pairs with $n < 10^{13}$, including prime factorizations (the latter is a large file, obviously).

It's apparently not known whether there are infinitely many such pairs (a large such $n$ apparently has $3108$ digits), but this would follow from Schinzel's Hypothesis H; see Ruth–Aaron Numbers Revisited (C. Pomerance), which also gives the asymptotic upper bound of $O\left(\frac{n \log^4 \log n}{\log^2 n}\right)$ Ruth–Aaron number $\leq n$ as $n \to \infty$. (This bound is strong enough to ensure that the sum of reciprocals of Ruth–Aaron Numbers is bounded.)

There are also triples $(n, n + 1, n + 2)$ such that $f(n) = f(n + 1) = f(n + 2)$; the smallest of these is given by $n = 417\,162$, for which $f(n) = 533$. It's not known whether any quadruplets exist.

See this related MathOverflow post.

1
On

No, there are many more. These are the ones smaller than 10000: $$ 5,8,15,77,125,714,948,1330,1520,1862,2491,3248,\\ 4185,4191,5405,5560,5959,6867,8280,8463 $$ Some more data: there are 149 with $n<10^6$ and 523 with $n<10^7$.