Logo
FAQ Tags Prizes Definitions Links
All Problems Random Solved Random Open
4 solved out of 11 shown
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)}$?
It is easy to see that almost all numbers are not practical. This may be true with $m=n!$. Erdős originally showed that $h(n!) <n$. Vose [Vo85] has shown that $h(n!)\ll n^{1/2}$.

Related to [304].

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 has found a counterexample. 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$.
$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$.
The answer is yes (in fact with $2$ replaced with any constant $c>1$), proved by Maier and Tenenbaum [MaTe84].

See also [449].

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].
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))$?

Erdős [Er35] proved that $\delta(n)<(\log n)^{-c}$ for some $c>0$. Tenenbaum [Te75] showed that $\delta(n)=(\log n)^{(-1+o(1))\alpha}$ where \[\alpha=1-\frac{1+\log\log 2}{\log 2}=0.08607\cdots.\]

This has been resolved by Ford [Fo08]. Among many other results, Ford proves \[\delta(n)\asymp \frac{1}{(\log n)^\alpha(\log\log n)^{3/2}},\] and that the second conjecture is false (i.e. $\delta'(n) \geq \delta(n)$ for some constant $c>0$)

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$?
Erdős and Graham also ask whether there is a good inequality known for $\sum_{n\leq x}\tau^*(n)$.
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$?
See also [447].
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$?
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$?

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$. Does \[\sum_{n\in A}\frac{1}{n}\] converge?
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.
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.

Melfi [Me15] has proved that there are infinitely many primitive weird numbers, conditional on various well-known conjectures on the distribution of prime gaps. For example, it would suffice to show that $p_{n+1}-p_n <\frac{1}{10}p_n^{1/2}$ for sufficiently large $n$.