3
$\begingroup$

By chance I stumbled upon the OEIS list A033677 of the smallest divisor of $n$ greater or equal to $\sqrt{n}$. Roughly speaking if we use the classic enhanced sieve of Eratosthenes, $\sqrt{n}$ is the typical upper limit to find a divisor $d \gt 1$ of $n$, so if $n$ is composite then it is expected that $\exists d \in [2,\sqrt{n}]$.

I did the same exercise but instead of $\sqrt{n}$ using as the limit the square root of the last sieved prime, which is indeed the previous closest prime $p$ to $n$ and made the calculation of the smallest divisor of $n$ greater or equal to $\lceil \sqrt{p} \rceil$.

Testing with Python and if I did not make an error, curiously I obtained exactly the same list than A033677 for every $n \in [3,6\cdot 10^6]$ (after that point it gets slower, I will try with PARI\GP later). So I wonder if it is possible to use the above mentioned $\lceil \sqrt{p} \rceil$ upper limit (the ceil of the square root of the last sieved prime) instead of $\sqrt{n}$ to find a divisor of $n$, if any.

This is the (very basic) Python code that compares one by one the elements of the sequence A033677 with the sequence of smallest divisor of $n$ greater or equal to $\sqrt{p}$, please feel free to use it:

from sympy import prevprime, divisors
    for n in range (3,10000000):
        A0033677_Value=0
        for d in divisors(n):
            if d>=sqrt(n):
                A0033677_Value=d
                break

        for d in divisors(n):
            if d>int(sqrt(prevprime(n))):
                if A0033677_Value == d:
                    print("SUCCESS "+str(n))
                else:
                    print("ERROR " + str(n) + "\t" + str(A0033677_Value)+"\t"+str(prevprime(n))+"\t"+str(d))
                    return
                break

If the observation is true, the property would be something like this:

$\forall n$ (composite)$\ \exists d: d|n\ , d \in [2,\lceil \sqrt{p_1} \rceil], p_1 \in \Bbb P, p_1\lt n,\ \land \not\exists\ p_2: p_1 \lt p_2 \lt n$.

For instance for $n=20,21,22,23$ we would look for a divisor of $n$ in the interval $[2,\lceil \sqrt{19} \rceil]$ because $19$ is the last sieved prime before $n$. As we already sieved $19$ in a former step it is in our list of already available primes and thus we can used (meaning we already know at this point that $19$ is prime). Then applying Eratosthenes as usual it would be detected that $n=20,21,22$ are composite and $n=23$ is the next prime.

UPDATE: as kindly explained by @Slade in the comments, in some cases (e.g when $n$ is a perfect square) having the same divisor $d$ over $\sqrt{n}$ and $\sqrt{p}$ does not imply that we can find a divisor at the interval $[2,\sqrt{p}]$ and it is required to go up to $[2,\lceil \sqrt{p}\rceil]$, meaning that the first divisor is exactly $\lceil \sqrt{p}\rceil$. That is the reason why the ceil function is used to set the upper limit.

If true I am not sure if it might be significant. By Bertrand's postulate, there should be a prime between $[\frac{n}{2},n]$, so in the best of cases, the previous prime would be $p_i=\frac{n}{2}$, so it would imply for that best of cases the use of $\sqrt{\frac{n}{2}}$ as the upper limit for the sieve instead of $\sqrt{n}$.

I would like to ask the following questions:

  1. Would it be possible to use $\lceil \sqrt{p} \rceil $ instead of $\sqrt{n}$? Was already in use that approach?

  2. Is there a counterexample (probably very big)? If not, what could be the reason behind it? Thank you!

UPDATE: the code below tests the Sieve of Eratosthenes using the modified algorithm as explained above, including the special condition for perfect squares. It seems to work so far up to $10^5$. I will test further.

from gmpy2 import is_prime, is_square
    # modified Eratosthenes, upper sieving limit sqrt(p)
        lopM=[2] #list of already sieved primes
        lp=2 # last prime sieved
        for pos in range(3,1000008):
            ul=int(sqrt(lp)) #upper limit
            if is_square(pos):
                ul=ul+1 # correction for perfect squares
                # basically: if is a perfect square we would continue for
            if ul==1:
                ul=2 # exclude 1 of possible divisors
            comp=False #composite detected
            for j in lopM: # using the list of already known primes
                if j in range(2,ul+1): # while j is under the upper limit
                    if (pos%j)==0:
                        comp=True
                        break
                else: # we arrived to the upper limit
                    break
                if comp==False:
                    lopM.append(pos)
                    lp=pos

        for elem in lopM:
            if not is_prime(elem): # sanity check
                print("ERROR, not prime " + str(elem))
                return
        print("Primes sieved: " + str(len(lopM)) + " and last prime was " + str(lp))
$\endgroup$
  • $\begingroup$ Don't you need the Sieve to calculate $p$? In such a case, you can't use $p$ in the Sieve itself. $\endgroup$ – Crostul Apr 11 '16 at 7:36
  • $\begingroup$ @Crostul I could be wrong but if you are sieving $n$ you already sieved the primes before $n$, so they are available in your list of already sieved primes. $\endgroup$ – iadvd Apr 11 '16 at 7:39
  • $\begingroup$ @Crostul I have added an example for $n=20,21,22$ using $p=19$. Thank you for the feedback! $\endgroup$ – iadvd Apr 11 '16 at 7:45
  • 1
    $\begingroup$ If I understand correctly, your code is demonstrating that the first divisor $>\sqrt{p}$ is also $\geq \sqrt{n}$. This is a little different from replacing $\sqrt{n}$ by $\sqrt{p}$: for example, if $n=9$, then $p=2$, and we have to search all the way up to $\sqrt{p}+1$ to find a divisor of $n$. $\endgroup$ – Slade Apr 11 '16 at 8:39
  • 1
    $\begingroup$ Right. I was confused by the suggestion of a counter-example. Given $p(\pi(\sqrt{n}))$ if there were a composite of primes g.t. $p$ it would exceed $n.$ So it is just the sieve. $\endgroup$ – daniel Apr 11 '16 at 15:09
1
$\begingroup$

1) As other people stated, imagine $n=q^2$, $q$-prime, then $p_{\pi(q^2)} < q^2 < p_{\pi(q^2)+1}$ which is $\sqrt{p_{\pi(q^2)}} < q < \sqrt{p_{\pi(q^2)+1}}$. Bertrand's postulate is not going to help, because if you stick to any bound $\leq \sqrt{p_{\pi(q^2)}}$, the algorithm will tell you $q^2$ is prime.

2) If $n=q\cdot b$, $q$-prime and $q<b$, then $p_{\pi(n)} < q\cdot b < p_{\pi(n)+1}$. Assuming Oppermann's conjecture is true (some references here), then $q<\sqrt{p_{\pi(n)}}$, otherwise (suppose contrary) if $$\sqrt{p_{\pi(n)}} \leq q \Rightarrow p_{\pi(n)} \leq q^2 < q \cdot (q+1) \leq q\cdot b < p_{\pi(n)+1}$$ and according to that conjecture there will be a prime between $q^2$ and $q \cdot (q+1)$. This contradicts the fact that $p_{\pi(n)+1}$ is the next prime after $p_{\pi(n)}$. So, technically, you can lower the bound in this particular case and assuming Oppermann's conjecture (!)

$\endgroup$
  • $\begingroup$ great explanation, thank you. I am going to run later a test for 1) because for small integers does not happen as you mention, so I guess this happens for a big counterexample, right? For instance: $101^2=10201$ the previous prime is $10193$ and $\sqrt{10193}=100.9$ as 10201 is a square we jump up to $100+1=101$ as $101$ is in our list of already sieved primes and divides $10201$ then $10201$ is not prime. So this is a counterexample of your explanation at 1)... but I suppose this hold for small integers but not for big integers. I will try to find a counterexample with a Python test. $\endgroup$ – iadvd Apr 13 '16 at 0:03
  • $\begingroup$ I think that's not a counter example, but rather an example because you are considering $101$ as the lower bound and not any $p$ lower than $p \leq \sqrt{10193}=100.9 < 100+1$ $\endgroup$ – rtybase Apr 13 '16 at 6:48
  • $\begingroup$ understood, if that is what it means, I agree with the explanation. But that point was added to the question (if I understood correctly the point): in the case of perfect squares the upper bound would be $\lceil \sqrt{p} \rceil$. Indeed the code I added at the end of the question does that. $\endgroup$ – iadvd Apr 13 '16 at 8:50
  • 1
    $\begingroup$ Yep, but I couldn't omit this case, for completeness ;) Also, my previous comment re Andrica's conjecture would suggest $\sqrt{p_{\pi(q^2)}} < q < \sqrt{p_{\pi(q^2)+1}}$ and $\sqrt{p_{\pi(q^2)+1}} - \sqrt{p_{\pi(q^2)}} < 1$ then $\left \lceil \sqrt{p_{\pi(q^2)}} \right \rceil=q$ $\endgroup$ – rtybase Apr 13 '16 at 9:13

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.