# Conjecture: There are infinitely many $N \in \Bbb{N}$ such that $p$ a prime $p \leq \sqrt{N+1} \implies p \mid N$?

Conjecture. There are infinitely many $$N$$ such that if $$p$$ is a prime $$\leq \sqrt{N+1}$$ then $$p \mid N$$.

Is this another hard to prove number theory conjecture, or do you have some idea of how to solve it?

• How many such $N$ have you found? – lulu May 9 at 12:53
• @lulu: 4, 6, 12, 18, ..., 30, not 42, ... – AbstractAlgebraLearner May 9 at 12:54
• Is it "... if $\forall p\leq \sqrt{N+1}$ ..." or "... if $\exists p\leq \sqrt{N+1}$ ... "? – rtybase May 9 at 12:54
• @it's for all prime $p$ such that $p^2 - 1 \leq N$ or equiv. $p \leq \sqrt{N+1}$, then... – AbstractAlgebraLearner May 9 at 12:55
• I don't find that intuitive at all. That's why I am asking what the numerical evidence is. – lulu May 9 at 12:57

If I'm interpreting your conjecture correctly, it is false. Let's say a number $$N$$ is an enjoyable number if, for all primes $$p\le \sqrt{N+1}$$, $$p$$ divides $$N$$. So for example, $$30$$ is an enjoyable number because $$\sqrt{31} \approx 5.6$$, and all primes $$\le 5.6$$ divide $$30$$.

Why can there not be infinitely many enjoyable numbers? Suppose $$N$$ is an enjoyable number. Then $$N$$ is divisible by every prime smaller than or equal to $$\sqrt{N+1}$$. In particular, $$N$$ is divisible by the product of all such primes. The prime counting function has the lower bound $$\pi(x)> \frac{x}{\log x}$$ The product of all primes less than or equal to $$\sqrt{N+1}$$ is bounded below by $$2^{\pi(\sqrt{N+1})}>2^{\frac{\sqrt{N+1}}{\log(\sqrt{N+1})}} = 4^{\frac{\sqrt{N+1}}{\log(N+1)}}$$ which is clearly asymptotically bigger than $$N$$, and computationally is bigger than $$N$$ for all $$N\ge 1473$$. Hence all enjoyable numbers must be smaller than $$1473$$.

Update: I did a computer of all integers up to $$1473$$. The complete set of enjoyable numbers is $$\{1,2,4,6,12,18,30\}$$. My Haskell code below:


-- Integer square root
isqrt :: (Integral a, Enum a, Ord a) => a -> a
isqrt n = pred $$head$$ filter (\k -> k^2 > n) [1..]

-- checks if the first argument is divisible by the second
divis :: Integral a => a -> a -> Bool
divis n = (0 == ) . (rem n)

-- checks if the first argument is not divisible by the second
sivid :: Integral a => a -> a -> Bool
sivid n = (0 /= ) . (rem n)

-- list of all primes
primes :: (Integral a, Enum a) => [a]
primes = 2:(filter (\ k -> and $$map (sivid k)$$ takeWhile (not . ( > k) . (^2)) primes) [3..])

-- multiplies all the primes up to n
pp :: (Integral a, Enum a, Ord a) => a -> a
pp n = product $takeWhile ( not . (> n) ) primes -- checks if a number is enjoyable is_enjoyable :: (Integral a, Enum a, Ord a) => a -> Bool is_enjoyable n = divis n $$pp$$ isqrt$ succ n

-- set of all enjoyable numbers
enjoyables :: [Integer]
enjoyables = filter is_enjoyable [1..1473]


If $$N$$ is divisible by every prime $$p\le\sqrt{N+1}$$, then $$N$$ is divisible by the product of all those primes. But the product of all the primes up to $$x$$ is known to be asymptotic to $$e^x$$, and $$e^{\sqrt{N+1}}$$ grows much much faster than $$N$$. So there are only finitely many such $$N$$.