5
$\begingroup$

I know there are fast ways to rule it out for special cases, but assuming it is actually true, how fast can you verify it?

I also wonder about sequences the primes are a subset of such as OEIS A050376 and A000961, whether verifying an index is any easier in those.

$\endgroup$
  • $\begingroup$ Just to be clear, if you had 101 you want to know how long to get an answer of 26 ? I'm thinking computer plus big database of primes, but perhaps you are thinking of primes beyond what has been sieved and want an algorithm. That seems like a big ask but I'll watch for answers with interest ! $\endgroup$ – Martin Hansen Apr 9 '19 at 8:24
  • $\begingroup$ No, I mean if someone hands you 101 and says that it is the 26th prime, how can you confirm that it is true quickly? Except, for much bigger primes and indexes, so that finding all smaller primes isn't practical. $\endgroup$ – Harald Korneliussen Apr 9 '19 at 8:56
  • $\begingroup$ It's a while ago (2006) but I generated all primes up to 2038074743, about 15 million of them. Your welcome to the text files if they are of any use. I think it took over a week of computer time then, probably a lot less now. Possibly you already have better. $\endgroup$ – Martin Hansen Apr 9 '19 at 9:32
  • $\begingroup$ @MartinHansen I will be interested in that list of primes. Can you share? $\endgroup$ – Nilotpal Kanti Sinha Apr 9 '19 at 14:28
5
$\begingroup$

I presume your question is that you know that the given number is a prime and you only want to know if it is the $n$-th prime or not. Here is an approach.

As starting point you can use explicit bounds on the $n$-th prime such as Dusart's

$$ n\log n + n\log\log n - n < p_n < n\log n + n\log\log n $$

which holds for $n \ge 6$ or use new recent tighter bounds by Christian Axler. This will narrow down your search range to less than $n$ integers which can then be handled by a brute force computer search.

$\endgroup$
  • $\begingroup$ But within those bounds, how would you brute force it? I can for instance see that 101 is within the bounds the formula gives for n=26, but so are a couple of other primes. How do I rule them out? $\endgroup$ – Harald Korneliussen Apr 9 '19 at 15:03

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.