It is easy to see that almost all numbers are not practical. Erdős originally showed that $h(n!) <n$. Vose [Vo85] proved the existence of infinitely many practical $m$ such that $h(m)\ll (\log m)^{1/2}$.

The sequence of practical numbers is A005153 in the OEIS.

The reward of \$250 is offered in [Er81h], apparently (although this is not entirely clear) for a proof or disproof of whether\[h(n!) <(\log n)^{O(1)}.\]See also [304] and [825].

View the LaTeX source

This page was last edited 31 October 2025.

2 comments on this problem

Asked by Erdős and Tenenbaum. Ruzsa gave the following simple counterexample: let $A=\{n_1<n_2<\cdots \}$ where $n_l \equiv -(k-1)\pmod{p_k}$ for all $k\leq l$, where $p_k$ denotes the $k$th prime.


Tenenbaum asked the weaker variant (still open) where for every $\epsilon>0$ there is some $k=k(\epsilon)$ such that at least $1-\epsilon$ density of all integers have a divisor of the form $a+k$ for some $a\in A$.

View the LaTeX source

1 comment on this problem

In [Er79] asks the stronger version with $2$ replaced by any constant $c>1$.

The answer is yes (also to this stronger version), proved by Maier and Tenenbaum [MaTe84]. (Tenenbaum has told me that they received \$650 for their solution.)

See also [449] and [884].

View the LaTeX source

This page was last edited 19 October 2025.

0 comments on this problem

Erdős [Er44] proved $Q(x)\gg (\log x)^{1+c}$ for some constant $c>0$.

The answer to this problem is no: Nicolas [Ni71] proved that\[Q(x) \ll (\log x)^{O(1)}.\]

View the LaTeX source

0 comments on this problem

The answer is yes, proved by Erdős and Sárkőzy [ErSa80].

View the LaTeX source

This page was last edited 28 October 2025.

0 comments on this problem

Besicovitch [Be34] proved that $\liminf \delta(n)=0$. Erdős [Er35] proved that $\delta(n)=o(1)$. Erdős [Er60] proved that $\delta(n)=(\log n)^{-\alpha+o(1)}$ where\[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\]This estimate was refined by Tenenbaum [Te84], and the true growth rate of $\delta(n)$ was determined by Ford [Fo08] who proved\[\delta(n)\asymp \frac{1}{(\log n)^\alpha(\log\log n)^{3/2}}.\]Among many other results in [Fo08], Ford also proves that the second conjecture is false, and more generally that if $\delta_r(n)$ is the density of integers with exactly $r$ divisors in $(n,2n)$ then $\delta_r(n)\gg_r\delta(n)$.

See also [448], [692], and [693].

View the LaTeX source

0 comments on this problem

This is false, and was disproved by Erdős and Tenenbaum [ErTe81], who showed that in fact the upper density of the set of such $n$ is $\asymp \epsilon^{1-o(1)}$ (where the $o(1)$ in the exponent $\to 0$ as $\epsilon \to 0$).

A more precise result was proved by Hall and Tenenbaum [HaTe88] (see Section 4.6), who showed that the upper density is $\ll\epsilon \log(2/\epsilon)$. Hall and Tenenbaum further prove that $\tau^+(n)/\tau(n)$ has a distribution function.



Erdős and Graham also asked whether there is a good inequality known for $\sum_{n\leq x}\tau^+(n)$. This was provided by Ford [Fo08] who proved\[\sum_{n\leq x}\tau^+(n)\asymp x\frac{(\log x)^{1-\alpha}}{(\log\log x)^{3/2}}\]where\[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\]See also [446] and [449].

View the LaTeX source

This page was last edited 19 October 2025.

0 comments on this problem

This is false - indeed, for any constant $K>0$ we have $r(n)>K\tau(n)$ for a positive density set of $n$. Kevin Ford has observed this follows from the negative solution to [448]: the Cauchy-Schwarz inequality implies\[r(n)+\tau(n)\geq \tau(n)^2/\tau^+(n)\]where $\tau^+(n)$ is as defined in [448], and the negative solution to [448] implies the right-hand side is at least $(K+1)\tau(n)$ for a positive density set of $n$. (This argument is given for an essentially identical problem by Hall and Tenenbaum [HaTe88], Section 4.6.)

See also [448].

View the LaTeX source

0 comments on this problem

It is not clear what the intended quantifier on $x$ is. Cambie has observed that if this is intended to hold for all $x$ then, provided\[\epsilon(\log n)^\delta (\log\log n)^{3/2}\to \infty\]as $n\to \infty$, where $\delta=0.086\cdots$, there is no such $y$, which follows from an averaging argument and the work of Ford [Fo08].

On the other hand, Cambie has observed that if $\epsilon\ll 1/n$ then $y(\epsilon,n)\sim 2n$: indeed, if $y<2n$ then this is impossible taking $x+n$ to be a multiple of the lowest common multiple of $\{n+1,\ldots,2n-1\}$. On the other hand, for every fixed $\delta\in (0,1)$ and $n$ large every $2(1+\delta)n$ consecutive elements contains many elements which are a multiple of an element in $(n,2n)$.

View the LaTeX source

0 comments on this problem

View the LaTeX source

6 comments on this problem

The integers in $A$ are also known as primitive pseudoperfect numbers and are listed as A006036 in the OEIS.

The same question can be asked for those $n$ which do not have distinct sums of sets of divisors, but any proper divisor of $n$ does (which are listed as A119425 in the OEIS).

Benkoski and Erdős [BeEr74] ask about these two sets, and also about the set of $n$ that have a divisor expressible as a distinct sum of other divisors of $n$, but where no proper divisor of $n$ has this property.

View the LaTeX source

This page was last edited 19 October 2025.

2 comments on this problem

Weird numbers were investigated by Benkoski and Erdős [BeEr74], who proved that the set of weird numbers has positive density. The smallest weird number is $70$.

Melfi [Me15] has proved that there are infinitely many primitive weird numbers, conditional on the fact that $p_{n+1}-p_n<\frac{1}{10}p_n^{1/2}$ for all large $n$, which in turn would follow from well-known conjectures concerning prime gaps.

The sequence of weird numbers is A006037 in the OEIS. Fang [Fa22] has shown there are no odd weird numbers below $10^{21}$, and Liddy and Riedl [LiRi18] have shown that an odd weird number must have at least 6 prime divisors.

If there are no odd weird numbers then every weird number has abundancy index $<4$ (see [825]).

See also [825].

This is problem B2 in Guy's collection [Gu04] (the \$10 is reported by Guy, offered by Erdős for a solution to the question of whether any odd weird numbers exist).

View the LaTeX source

This page was last edited 28 October 2025.

1 comment on this problem

Erdős writes it is 'easy' to prove $\frac{1}{X}\sum_{n\leq X}G(n)\to \infty$.

Terence Tao has observed that, for any divisor $m\mid n$,\[\frac{\tau(n/m)}{m} \leq G(n) \leq \tau(n),\]and hence for example $\tau(n)/4\leq G(n)\leq \tau(n)$ for even $n$. It is easy to then see that $G(n)$ grows on average, and in general behaves very similarly to $\tau(n)$ (and in particular the answer to the first question is yes). Tao suggests that this was a mistaken conjecture of Erdős, which he soon corrected a year later to [448].

Indeed, in [Er82e] Erdős recalls this conjecture and observes that it is indeed trivial that $G(n)\to \infty$ for almost all $n$, and notes that he and Tenenbaum proved that $G(n)/\tau(n)$ has a continuous distribution function.

View the LaTeX source

0 comments on this problem

Erdős proved that\[\delta_1(n,m) \ll \frac{1}{(\log n)^c}\]for all $m$, for some constant $c>0$. Sharper bounds (for various ranges of $n$ and $m$) were given by Ford [Fo08].

Cambie has calculated that unimodularity fails even for $n=2$ and $n=3$. For example,\[\delta_1(3,6)= 0.35\quad \delta_1(3,7)\approx 0.33\quad \delta_1(3,8)\approx 0.3619.\]Furthermore, Cambie [Ca25] has shown that, for fixed $n$, the sequence $\delta_1(n,m)$ has superpolynomially many local maxima $m$.

See also [446].

View the LaTeX source

0 comments on this problem

See also [446].

View the LaTeX source

0 comments on this problem

Erdős writes it is 'easy to see' that $h(n)\to \infty$ for almost all $n$ (which is proved in the comments by van Doorn), and believed he could show that the normal order of $h(n)$ is $\log_*(n)$ (the iterated logarithm).

See also [695].

View the LaTeX source

This page was last edited 15 October 2025.

1 comment on this problem

It is trivial that $\delta(m,\alpha)\to 0$ if $\alpha <1$, and Erdős could prove that the same is true for $\alpha=1$.

See also [696].

View the LaTeX source

0 comments on this problem

A problem of Benkoski and Erdős. In other words, this problem asks for an upper bound for the abundancy index of weird numbers. This could be true with $C=3$. We must have $C>2$ since $\sigma(70)=144$ but $70$ is not the distinct sum of integers from $\{1,2,5,7,10,14,35\}$.

Erdős suggested that as $C\to \infty$ only divisors at most $\epsilon n$ need to be used, where $\epsilon \to 0$.

Weisenberg has observed that if $n$ is a weird number with an abundancy index $\geq 4$ then it is divisible by an odd weird number. In particular, if there are no odd weird numbers (see [470]) then every weird number has abundancy index $<4$. Indeed, if $l(n)$ is the abundancy index and $n=2^km$ with $m$ odd then $l(n)=l(2^k)l(m)$, and $l(2^k)<2$ so if $l(n)\geq 4$ then $l(m)>2$, and hence $m$ is weird (as a factor of a weird number).

A similar argument shows that either there are infinitely many primitive weird numbers or there is an upper bound for the abundancy index of all weird numbers.

See also [18] and [470].

This is part of problem B2 in Guy's collection [Gu04] (the \$25 is reported by Guy as offered by Erdős for a solution to this question).

View the LaTeX source

This page was last edited 28 October 2025.

7 comments on this problem

Erdős [Er70] proved that $d_t$ always exists, and that there exist some constants $c_3,c_4>0$ such that\[\frac{1}{(\log t)^{c_3}} < d_t < \frac{1}{(\log t)^{c_4}}.\]

View the LaTeX source

0 comments on this problem

See also [144].

View the LaTeX source

5 comments on this problem

A question of Erdős and Rosenfeld [ErRo97], who proved this is true for $k=2$. Jiménez-Urroz [Ji99] proved this for $k=3$ and Bremner [Br19] proved this for $k=4$.

View the LaTeX source

0 comments on this problem

Erdős attributes this conjecture to Ruzsa. Erdős and Rosenfeld [ErRo97] proved that there are infinitely many $n$ such that there are four divisors of $n$ in $(n^{1/2},n^{1/2}+n^{1/4})$.

See also [887].

View the LaTeX source

0 comments on this problem

A question of Erdős and Rosenfeld [ErRo97], who proved that there are infinitely many $n$ with $4$ divisors in $(n^{1/2},n^{1/2}+n^{1/4})$, and ask whether $4$ is best possible here.

View the LaTeX source

0 comments on this problem

Erdős [Er98] says that 'probably there is no simple asymptotic formula for $f(n)$ since $f(n)$ increases too fast'.

Kovač and Luca [KoLu25] (building on a heuristic independently found by Cambie (personal communication)) have shown that there is no finite limit, in that\[\limsup_{n\to \infty}\frac{f(2n)}{f(n)}=\infty,\]and provide both theoretical and numerical evidence that suggests $\lim \frac{f(2n)}{f(n)}=\infty$.

View the LaTeX source

0 comments on this problem

A problem of Erdős and Mirsky [ErMi52], who proved that\[\frac{(\log x)^{1/2}}{\log\log x}\ll F(x) \ll \exp\left(O\left(\frac{(\log x)^{1/2}}{\log\log x}\right)\right).\]Erdős [Er85e] claimed that the lower bound could be improved via their method 'with some more work' to $(\log x)^{1-o(1)}$. Beker has improved the upper bound to\[F(x) \ll \exp\left(O\left((\log x)^{1/3+o(1)}\right)\right).\]Cambie has observed that Cramér's conjecture implies that $F(x) \ll (\log x)^2$, and furthermore if every interval in $[x,2x]$ of length $\gg \log x$ contains a squarefree number (see [208]) then every interval of length $\gg (\log x)^2$ contains two numbers with the same number of divisors, whence\[F(x) \ll (\log x)^2.\]See [1004] for the analogous problem with the Euler totient function.

This problem is discussed in problem B18 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 05 October 2025.

3 comments on this problem

A problem of Erdős and Mirsky [ErMi52]. More generally, they ask about the estimation of the longest run of consecutive integers $\leq x$ which have the same number of divisors.

Spiro [Sp81] proved that there are infinitely many $n$ such that $\tau(n)=\tau(n+5040)$, and Heath-Brown [He84] improved her method to prove this for $\tau(n)=\tau(n+1)$. More generally, he showed that the number of such $n\leq x$ is\[\gg \frac{x}{(\log x)^7}.\]This lower bound was improved to\[\gg \frac{x}{(\log\log x)^3}\]by Hildebrand [Hi87]. Erdős, Pomerance, and Sárközy [EPS87] proved an upper bound of\[\ll\frac{x}{\sqrt{\log\log x}}.\]See [1003] for the analogous question with the Euler totient function.

This is discussed in problem B18 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 28 September 2025.

2 comments on this problem

This follows easily from the generalised prime $k$-tuple conjecture. Eberhard [Eb25] has proved this unconditionally, and in fact proved that all positive rationals can be written as such a ratio.

See also [946].

View the LaTeX source

0 comments on this problem

Van der Corput [Va39] proved that\[\sum_{n\leq X} \tau(f(n))\gg_f X\log X.\]Erdős [Er52b] proved using elementary methods that\[\sum_{n\leq X} \tau(f(n))\ll_f X\log X.\]Such an asymptotic formula is known whenever $f$ is an irreducible quadratic, as proved by Hooley [Ho63]. The form of $c$ depends on $f$ in a complicated fashion (see the work of McKee [Mc95], [Mc97], and [Mc99] for expressions for various types of quadratic $f$). For example,\[\sum_{n\leq x}\tau(n^2+1)=\frac{3}{\pi}x\log x+O(x).\]Tao has a blog post on this topic.

View the LaTeX source

3 comments on this problem

A question of Erdős reported in problem B2 of Guy's collection [Gu04]. The function $f(n)$ is undefined for $n=2$ and $n=5$, but is likely well-defined for all $n\geq 6$ (which would follow from a strong form of Goldbach's conjecture).

The sequence of values of $f(n)$ is given by A167485 in the OEIS.

View the LaTeX source

3 comments on this problem

Erdős [Er81h] remarks that $n!$ or the least common multiple of $\{1,\ldots,n\}$ would be good candidates for an infinite sequence of $n$ with $h_\alpha(n)$ bounded.

The $\liminf$ is trivially $\geq 1$, just considering the term $i=1$. A positive answer to the main question was provided by Vose [Vo84] by constructing a specific sequence. It remains open whether the two explicit sequences mentioned above satisfy this property.

Erdős remarks that this problem occurred to him when considering $\sum_i \frac{d_{i+1}}{d_i}$. It is easy to see that\[\sum_{i} \frac{d_{i+1}}{d_i}> \tau(n)+\log n,\]and Erdős asked whether\[\liminf \left(\sum_{i} \frac{d_{i+1}}{d_i}-\tau(n)-\log n\right)<\infty,\]which would follow from an affirmative answer to the main question.

This resembles the function considered in [673].

View the LaTeX source

This page was last edited 19 October 2025.

8 comments on this problem

The function $\tau_\perp(n)$ was considered by Erdős and Hall [ErHa78]. It is trivial that $\tau_\perp(n)\geq \omega(n)$ (with equality for infinitely many $n$). Erdős and Hall prove, for all $\epsilon>0$ and sufficiently large $x$,\[\max_{n<x} \tau_\perp(n) > \exp((\log\log x)^{2-\epsilon}).\]Erdős and Simonovits (see [Er81h]) proved\[(2^{1/2}+o(1))^k < g(k) < (2-c)^k\]for some constant $c>0$.

View the LaTeX source

This page was last edited 19 October 2025.

1 comment on this problem