Logo
Tags Prizes
More
FAQ Problem Lists Definitions Links How to help
All Random Solved Random Open
9 solved out of 23 shown (show only solved or open)
OPEN
We call $m$ practical if every integer $n<m$ is the sum of distinct divisors of $m$. If $m$ is practical then let $h(m)$ be such that $h(m)$ many divisors always suffice.

Are there infinitely many practical $m$ such that \[h(m) < (\log\log m)^{O(1)}?\] Is it true that $h(n!)<n^{o(1)}$? Or perhaps even $h(n!)<(\log n)^{O(1)}$?

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.

See also [304] and [825].

Additional thanks to: Ralf Stephan
SOLVED
Let $A\subset\mathbb{N}$ be infinite. Must there exist some $k\geq 1$ such that almost all integers have a divisor of the form $a+k$ for some $a\in A$?
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$.

Additional thanks to: Imre Ruzsa
SOLVED - $250
The density of integers which have two divisors $d_1,d_2$ such that $d_1<d_2<2d_1$ exists and is equal to $1$.
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].

SOLVED
A number $n$ is highly composite if $\tau(m)<\tau(n)$ for all $m<n$, where $\tau(m)$ counts the number of divisors of $m$. Let $Q(x)$ count the number of highly composite numbers in $[1,x]$.

Is it true that \[Q(x)\gg_k (\log x)^k\] for every $k\geq 1$?

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)}.\]

Additional thanks to: Julius Schmerling
SOLVED
Let $A\subseteq\mathbb{N}$ be infinite and $d_A(n)$ count the number of $a\in A$ which divide $n$. Is it true that, for every $k$, \[\limsup_{x\to \infty} \frac{\max_{n<x}d_A(n)}{\left(\sum_{n\in A\cap[1,x)}\frac{1}{n}\right)^k}=\infty?\]
The answer is yes, proved by Erdős and Sárkőzy [ErSa80].
SOLVED
Let $\delta(n)$ denote the density of integers which are divisible by some integer in $(n,2n)$. What is the growth rate of $\delta(n)$?

If $\delta'(n)$ is the density of integers which have exactly one divisor in $(n,2n)$ then is it true that $\delta'(n)=o(\delta(n))$?

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].

Additional thanks to: Zachary Chase and Kevin Ford
SOLVED
Let $\tau(n)$ count the divisors of $n$ and $\tau^+(n)$ count the number of $k$ such that $n$ has a divisor in $[2^k,2^{k+1})$. Is it true that, for all $\epsilon>0$, \[\tau^+(n) < \epsilon \tau(n)\] for almost all $n$?
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].

Additional thanks to: Kevin Ford
SOLVED
Let $r(n)$ count the number of $d_1,d_2$ such that $d_1\mid n$ and $d_2\mid n$ and $d_1<d_2<2d_1$. Is it true that, for every $\epsilon>0$, \[r(n) < \epsilon \tau(n)\] for almost all $n$, where $\tau(n)$ is the number of divisors of $n$?
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].

Additional thanks to: Kevin Ford
OPEN
How large must $y=y(\epsilon,n)$ be such that the number of integers in $(x,x+y)$ with a divisor in $(n,2n)$ is at most $\epsilon y$?
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)$.

Additional thanks to: Stijn Cambie
OPEN
For any $n$ let $D_n$ be the set of sums of the shape $d_1,d_1+d_2,d_1+d_2+d_3,\ldots$ where $1<d_1<d_2<\cdots$ are the divisors of $n$.

What is the size of $D_n\backslash \cup_{m<n}D_m$?

If $f(N)$ is the minimal $n$ such that $N\in D_n$ then is it true that $f(N)=o(N)$? Perhaps just for almost all $N$?

OPEN
Let $A$ be the set of all $n$ such that $n=d_1+\cdots+d_k$ with $d_i$ distinct proper divisors of $n$, but this is not true for any $m\mid n$ with $m<n$ (i.e. primitive practical numbers). Does \[\sum_{n\in A}\frac{1}{n}\] converge?
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.

Additional thanks to: Zachary Chase and Desmond Weisenberg
OPEN
Call $n$ weird if $\sigma(n)\geq 2n$ and $n\neq d_1+\cdots+d_k$, where the $d_i$ are distinct proper divisors of $n$.

Are there any odd weird numbers? Are there infinitely many primitive weird numbers, i.e. those such that no proper divisor of $n$ is weird?

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.

Additional thanks to: Desmond Weisenberg
SOLVED
Let $1=d_1<\cdots <d_{\tau(n)}=n$ be the divisors of $n$ and \[G(n) = \sum_{1\leq i<\tau(n)}\frac{d_i}{d_{i+1}}.\] Is it true that $G(n)\to \infty$ for almost all $n$? Can one prove an asymptotic formula for $\sum_{n\leq X}G(n)$?
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.

Additional thanks to: Terence Tao
SOLVED
Let $\delta_1(n,m)$ be the density of the set of integers with exactly one divisor in $(n,m)$. Is $\delta_1(n,m)$ unimodular for $m>n+1$ (i.e. increases until some $m$ then decreases thereafter)? For fixed $n$, where does $\delta_1(n,m)$ achieve its maximum?
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].

Additional thanks to: Stijn Cambie
OPEN
Let $k\geq 2$ and $n$ be sufficiently large depending on $k$. Let $A=\{a_1<a_2<\cdots \}$ be the set of those integers in $[n,n^k]$ which have a divisor in $(n,2n)$. Estimate \[\max_{i} a_{i+1}-a_i.\] Is this $\leq (\log n)^{O(1)}$?
See also [446].
OPEN
Let $h(n)$ be the largest $\ell$ such that there is a sequence of primes $p_1<\cdots p_\ell$ all dividing $n$ with $p_{i+1}\equiv 1\pmod{p_i}$. Let $H(n)$ be the largest $u$ such that there is a sequence of integers $d_1<\cdots d_u$ all dividing $n$ with $d_{i+1}\equiv 1\pmod{d_i}$.

Estimate $h(n)$ and $H(n)$. Is it true that $H(n)/h(n)\to \infty$ for almost all $n$?

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

See also [695].

OPEN
Let $\delta(m,\alpha)$ denote the density of the set of integers which are divisible by some $d\equiv 1\pmod{m}$ with $1<d<\exp(m^\alpha)$. Does there exist some $\beta\in (1,\infty)$ such that \[\lim_{m\to \infty}\delta(m,\alpha)\] is $0$ if $\alpha<\beta$ and $1$ if $\alpha>\beta$?
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].

OPEN
Let $t\geq 1$ and let $d_t$ be the density of the set of integers $n\in\mathbb{N}$ for which $t$ can be represented as the sum of distinct divisors of $n$.

Do there exist constants $c_1,c_2>0$ such that \[d_t \sim \frac{c_1}{(\log t)^{c_2}}\] as $t\to \infty$?

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}}.\]
OPEN
Is it true that, for any $n$, if $d_1<\cdots <d_t$ are the divisors of $n$, then \[\sum_{1\leq i<j\leq t}\frac{1}{d_j-d_i} \ll 1+\sum_{1\leq i<t}\frac{1}{d_{i+1}-d_i},\] where the implied constant is absolute?
See also [144].
OPEN
For integer $n\geq 1$ we define the factor difference set of $n$ by \[D(n) = \{\lvert a-b\rvert : n=ab\}.\] Is it true that, for every $k\geq 1$, there exist integers $N_1<\cdots<N_k$ such that \[\lvert \cap_i D(N_i)\rvert \geq k?\]
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$.
OPEN
Let $\epsilon>0$. Is it true that, for all large $n$, the number of divisors of $n$ in $(n^{1/2},n^{1/2}+n^{1/2-\epsilon})$ is $O_\epsilon(1)$?
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].

OPEN
Is there an absolute constant $K$ such that, for every $\epsilon>0$, if $n$ is sufficiently large then $n$ has at most $K$ divisors in $(n^{1/2},n^{1/2}+\epsilon n^{1/4})$.
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.
OPEN
If $\tau(n)$ counts the divisors of $n$ then let \[f(n)=\sum_{1\leq k\leq n}\tau(2^k-1).\] Does $f(2n)/f(n)$ tend to a limit?
Erdős [Er98] says that 'probably there is no simple asymptotic formula for $f(n)$ since $f(n)$ increases too fast'.