Is it true that \[\sum_{n\in A}\frac{1}{n}<\infty?\]
Is it true that \[\sum_{n\in A}\frac{1}{n}<\infty?\]
An example of an $A$ with this property where \[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}\log N>0\] is given by the set of $p^2$, where $p\equiv 3\pmod{4}$ is prime.
Elsholtz and Planitzer [ElPl17] have constructed such an $A$ with \[\lvert A\cap\{1,\ldots,N\}\rvert\gg \frac{N^{1/2}}{(\log N)^{1/2}(\log\log N)^2(\log\log\log N)^2}.\]
Schoen [Sc01] proved that if all elements in $A$ are pairwise coprime then \[\lvert A\cap\{1,\ldots,N\}\rvert \ll N^{2/3}\] for infinitely many $N$. Baier [Ba04] has improved this to $\ll N^{2/3}/\log N$.
For the finite version see [13].
For the infinite version see [12].
In [Er92c] Erdős asks about the general version where $a\nmid (b_1+\cdots+b_r)$ for $a<\min(b_1,\ldots,b_r)$, and whether $\lvert A\rvert \leq N/(r+1)+O(1)$.
Solved by Tao [Ta23b], who proved that \[ \lvert A\rvert \leq \left(1+O\left(\frac{(\log\log x)^5}{\log x}\right)\right)\pi(x).\]
In [Er95c] Erdős further asks about the situation when $\phi(a_1)\leq \cdots \leq \phi(a_t)$.
Can one show that there exists an $\epsilon>0$ such that there are infinitely many $n$ where $m+\epsilon \omega(m)\leq n$ for all $m<n$?
Erdős also believed that $\Omega$, the count of the number of prime factors with multiplicity), should have infinitely many barriers. Selfridge found the largest barrier for $\Omega$ which is $<10^5$ is $99840$.
In [ErGr80] this problem is suggested as a way of showing that the iterated behaviour of $n\mapsto n+\omega(n)$ eventually settles into a single sequence, regardless of the starting value of $n$ (see also [412] and [414]).
Erdős and Graham report it could be attacked by sieve methods, but 'at present these methods are not strong enough'.
Ryan Alweiss has provided the following simple argument showing that the answer is yes: suppose we have some red/blue colouring without this property. Without loss of generality, suppose $1$ is coloured red, and then either $3$ or $5$ must be blue.
Suppose first that $3$ is blue. If $n\geq 6$ is red then (considering $1,n,2n-1$) we deduce $2n-1$ is blue, and then (considering $3,n+1,2n-1$) we deduce that $n+1$ is red. In particular the colouring must be eventually constant, and we are done.
Now suppose that $5$ is blue. Arguing similarly (considering $1,n,2n-1$ and $5,n+2,2n-1$) we deduce that if $n\geq 8$ is red then $n+2$ is also red, and we are similarly done, since the colouring must be eventually constant on some congruence class modulo $2$.
In [Er79] Erdős says 'it is extremely doubtful' that there are infinitely many such $n$, and in fact suggets that \[\lim_{n\to \infty}\max_{m<n}(\tau(m)+m-n)=\infty.\]
In [Er79d] Erdős says it 'seems certain' that for every $k$ there are infinitely many $n$ for which \[\max_{n-k<m<n}(m+\tau(m))\leq n+2,\] but 'this is hopeless with our present methods', although it follows from Schinzel's Hypothesis H.
See also [413].
In fact, the answer to this question as written is easily seen to be no, since there are no solutions to $2^k\equiv -1\pmod{7}$, and hence this fails with $p=2$ and $q=7$. It is possible that Erdős meant to exclude such obstructions, by amending this to 'odd primes' or 'all sufficiently large primes' or such.
Even with such amendments, this problem is false is a strong sense: Alan Tong has provided the following elegant elementary proof that, for any given prime $p$, there are infinitely many primes $q$ such that this statement is false: let $m$ be the product of all primes $\leq p$, and choose a prime $q$ congruent to $-1$ modulo $4m$. If $p$ is the greatest prime divisor of $n$ then, using quadratic reciprocity, every prime divisor of $n$ is a quadratic residue modulo $q$, and hence $n$ is a quadratic residue modulo $q$. On the other hand, since $q\equiv 3\pmod{4}$ we know that $-1$ is not a quadratic residue modulo $q$, and hence $n\not\equiv -1\pmod{q}$, so it is impossible for $q\mid n+1$.
Tong asks whether, for any given odd prime $q$, there are infinitely many primes $p$ such that there is no integer $n$ with $P(n)=p$ and $P(n+1)=q$.
Sampaio independently observed that the answer to Erdős' original problem is no if one of the primes can be $2$ - for example this is false with $p=19$ and $q=2$, since if $n+1=2^k$ and $19\mid n$ then (since $2$ is a primitive root modulo $19$) we must have $18\mid k$, and hence $73\mid 2^{18}-1\mid n$. A similar argument works with $19$ replaced by any prime $p>13$ for which $2$ is a primitive root, using a result of Rotkiewicz [Ro64b] that for every prime $p>13$ there is a prime $q>p$ which divides $2^{p-1}-1$.
Problem 6 in the 12th Romanian Master of Mathematics Competitions in 2020 was to prove that there exist infinitely many odd primes $p$ such that, for every $n$, $P(n)P(n+1)\neq 2p$.
Estimate $f(m)$. In particular is it true that $f(m)\ll m^{1/2}$?