2
$\begingroup$

I have a function in javascript that is supposed to calculate the nth prime.

function largestPrime(n) {
    //const start = Date.now(); add this for testing performance
    if (n < 2) {
        return -1;
    }
    if(n === 2){
        return 2;
    }
    let arr = [];

    let i = 3;
    while(arr.length < n) {
        if (helper(i, arr)) {
            arr.push(i);
        }
        i += 2;
    }
    //let retVal; add this for testing performance
    //if(Date.now() - start > 1000){
    //    retVal = `${((Date.now() - start) / 1000).toFixed(2)}s`;
    //}else{
    //    retVal = `${(Date.now() - start)}ms`;
    //}
    //console.log(`Calculated after ${retVal}.`);

    return ([2, ...arr])[n-1];
}

It used a helper function to check if the number is prime:

function helper(n, arr){
    let i = 0;
    while(10*i*i<n){
        if(n % arr[i] === 0){
            return false;
        }
        i++;
    }
    return true;
}

The issue lies with this: while(10*i*i<n). Why does this work? It reduces the amount of calculations by a ton but it doesn't seem to have any reason behind it. After realising that I don't have to check for num % 2 === 0 because i += 2 I shifted the array of primes one index to the left. Before the max I could check for before the calculations became inaccurate was while(5*i*i<n). Does anyone have a way to generalize this? If it can be generalized then I can try shifting the array to the left once more.

I tested 5 through 10 all the way upto the 100.000.000th prime (which is 2038074743 for anyone curious) and they still work.

//f(1000000)=15485863 en f(2000000)=32452843 en f(3000000)=49979687: 5 work upto 4000000
//f(1000000)=15485863 en f(2000000)=32452843 en f(3000000)=49979687: 6 work upto 4000000
//f(1000000)=15485863 en f(2000000)=32452843 en f(3000000)=49979687: 7 work upto 4000000
//f(1000000)=15485863 en f(2000000)=32452843 en f(3000000)=49979687: 8 work upto 4000000
//f(1000000)=15485863 en f(2000000)=32452843 en f(3000000)=49979687: 9 work upto 4000000
//f(1000000)=15485863 en f(2000000)=32452843 en f(3000000)=49979687: 10 work upto 4000000
//f(1000000)=15485843 en f(2000000)=32452789: 11 worked for smaller numbers
$\endgroup$
4
  • 1
    $\begingroup$ Nah this is a math question about the prime counting function, just not obvious to see. $\endgroup$ Commented Mar 18 at 13:50
  • $\begingroup$ @RandomMathEnthusiast i got the same response from Stack Overflow ;-; $\endgroup$ Commented Mar 18 at 13:58
  • $\begingroup$ This is an appropriate question for this site. It is a non trivial number theory problem, just presented in javascript rather than prose. $\endgroup$ Commented Mar 18 at 14:04
  • $\begingroup$ Or maybe I should say it uses a nontrivial result from number theory. $\endgroup$ Commented Mar 18 at 14:38

1 Answer 1

Reset to default
3
$\begingroup$

If a number is composite, it will have a prime factor less than it's square root. Or the contrapositive, if a prime factor less than a square root does not exist, then a number is prime.

So using $$p(k)^2 < n$$

You want to establish

$$10k^2 < n$$

For a sequence $p(k)$ (this is your arr), with: $$\begin{array} {r|rrrrrrrr} k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \cdots \\ p & 3 & 5 & 7 & 11 & 13 & 17 & 19 & \cdots \end{array}$$

Use the transitivity of $<$, that is, $a < b \text{ and } b < c \implies a < c$ . So choose $a=10k^2$, $b=p(k)^2$, $c=n$ . We already have $b<c$, so we need to establish $a<b$:

$$10k^2 < p(k)^2$$ $$k\sqrt{10} < p(k)$$ We can see the inequality holds for how much of $p$ is written above, but to establish that in general we need an exact bound on the prime counting function $\pi$. For prime $y$, $\pi(y) = z$ corresponds to $p(z - 1) = y$ . For example $p(2) = 7$ means $\pi(7) = 3$ means there are 3 primes less than 7, which are 2, 3, 5.

$$\pi(p(z - 1)) = z$$

$$(k- 1)\sqrt{10} < p(k - 1)$$ $$\pi((k- 1)\sqrt{10}) < \pi(p(k - 1))$$ $$\pi((k - 1)\sqrt{10}) < k$$ $$j = (k - 1)\sqrt{10}$$ $$j/\sqrt{10} + 1 = k$$ $$\pi(j) < j/\sqrt{10} + 1$$

So now just need an upper bound of the prime counting function. Here is one just looked up:

$$\pi(j) < \frac{j}{\log j}\left(1+\frac{3}{2\log j}\right)$$ $$\pi(j) < \frac{j}{\log j}+ \frac{3j}{2(\log j)^2}$$ So need to establish: $$\frac{j}{\log j}+ \frac{3j}{2(\log j)^2} < j/\sqrt{10} + 1$$ The dominating term $j/\sqrt{10}$ will eventually be larger than the dominating term $j / \log j$, so it is eventually true. $$\frac{j}{\log j}\left(1+\frac{3}{2\log j}\right) < j/\sqrt{10} + 1$$ $$\frac{1}{\log j}\left(1+\frac{3}{2\log j}\right) < 1/\sqrt{10} + 1/j$$ $$\frac{1}{\log j}\left(1+\frac{3}{2\log j}\right) < 1/\sqrt{10}$$

Numerically it holds for $j=72$ , so if $k \sqrt{10} < p(k)$ holds up to $j=72$ which is $k \approx 23.7$ then the algorithm works. Which it easily does because the algorithm's bound is very loose.

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.