2
$\begingroup$

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?

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

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]
| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.