← All problems

Erdős Problem #945 — Long runs of consecutive integers with distinct divisor counts

74 years old · traced to

For a positive integer mm, let τ(m)\tau(m) denote its number of positive divisors. For real x≥1x\geq 1, define F(x)F(x) as the greatest integer k≥0k\geq 0 for which some kk consecutive positive integers not exceeding xx have pairwise distinct divisor counts:

F(x)=max⁡{k≥0: ∃m∈Z≥1, m+k−1≤x, τ(m),τ(m+1),…,τ(m+k−1) are pairwise distinct}.F(x)=\max\left\{k\geq 0:\ \exists m\in\mathbb Z_{\geq 1},\ m+k-1\leq x,\ \tau(m),\tau(m+1),\ldots,\tau(m+k-1)\text{ are pairwise distinct}\right\}.

Estimate the growth of F(x)F(x). In particular, does there exist a constant C>0C>0 such that F(x)≤(log⁡x)CF(x)\leq (\log x)^C for all sufficiently large xx? Equivalently at the level of existence of a fixed logarithmic exponent, must every sufficiently large interval [X,X+(log⁡X)C][X,X+(\log X)^C] contain two integers with the same number of positive divisors? Erdős and Mirsky (1952) Erdős Problem #945

Background

Erdős and Mirsky introduced this question in their 1952 study of the distribution of values of the divisor function, writing d(n)d(n) for what is now denoted τ(n)\tau(n). Their paper studies both the distinct values assumed by the function up to a bound and how long a consecutive run can avoid repeating a value. These are related questions, but the latter asks for local structure in the sequence τ(1),τ(2),…\tau(1),\tau(2),\ldots, rather than only the number of values attained globally. Erdős and Mirsky (1952) Erdős and Mirsky (1952)

Erdős later suggested that the original construction, with further work, might give a lower bound of order (log⁡x)1−o(1)(\log x)^{1-o(1)}. This is reported as a proposed improvement to the lower bound, not as an established estimate. Erdős Problem #945

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.