← All problems

Erdős Problem #413 — Barriers for the distinct-prime-divisor function

47 years old · traced to

For a positive integer rr, let ω(r)\omega(r) be the number of distinct prime divisors of rr; in particular, ω(1)=0\omega(1)=0. The first question asks whether there are infinitely many positive integers nn such that

∀m∈Z>0,m<n  ⟹  m+ω(m)≤n.\forall m\in\mathbb Z_{>0},\quad m<n\implies m+\omega(m)\le n.

Such an nn is a barrier for ω\omega. The second question asks whether there is a fixed real number ϵ>0\epsilon>0 for which infinitely many positive integers nn satisfy

∀m∈Z>0,m<n  ⟹  m+ϵ ω(m)≤n.\forall m\in\mathbb Z_{>0},\quad m<n\implies m+\epsilon\,\omega(m)\le n.

Erdős Problems #413

Background

Erdős introduced the barrier terminology in 1979 and conjectured that ω\omega has infinitely many barriers. The question sits among related problems about the behavior of iterated arithmetic functions: Erdős and Graham proposed it as a possible route to showing that iteration of n↦n+ω(n)n\mapsto n+\omega(n) eventually settles into one sequence, independently of the starting value. This was proposed as a motivation, not stated as a consequence already proved. Erdős Problems #413 Erdős (1979), Some unconventional problems in number theory

A related function considered by Erdős is F(n)=∏ikiF(n)=\prod_i k_i when n=∏ipikin=\prod_i p_i^{k_i} is its prime factorization. Erdős proved that FF has barriers on a set of positive density. The same account notes that Selfridge found 9984099840 to be the largest barrier for the prime-factor-counting function with multiplicity, Ω\Omega, below 10510^5. Erdős Problems #413 Erdős (1979), Some unconventional problems in number theory

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.