Re: Another twin primes conjecture

From: Lance Lamboy (lance.lamboy_at_lamboy.nospam.com)
Date: 06/19/04 

Date: Fri, 18 Jun 2004 20:49:46 -0400

On Sat, 19 Jun 2004 00:07:09 +0000, Quinn Tyler Jackson wrote:

>> Could you refresh me on what Hpi and HPC are. I have no clue.
>
> Just my abbreviations for "Harris' Prime Counter".
>
> Turns out I was likely correct about my assumption that Hpi(i)-Hpi(i-1)
> being a quick primality test. Because of the optimization I made, doing
> two counts in a row like that, with the larger number first, behaves
> with O(n) (or thereabouts) complexity.

I have not looked at Harris' Prime Counter, but from what I understand:

it calculates the number of primes less than or equal to a specified value
(commonly called the pi function);

it works correctly;

it works in O(n); and

the best known algorithm for this problem works in O(sqrt(n)).

Is that basicly correct?

Assuming that my understanding of HPC is correct then your HPC(i)-HPC(i-1)
is a primality test. Let a=HPC(i-1). Clearly HPC(i) can only be a or
a+1. If HPC(i) is a+1 then that necessarily implies that i is prime.

However having said that, it is not fast. It is O(n). Using the best
known algorithm in place of HPC would result in O(sqrt(n)).

Miller-Rabin would be much faster.

> And it certainly appears to be more elegant than some of the Primality
> Tests I've seen, q.v.:
>
> http://primes.utm.edu/curios/includes/file.php?file=primetest.html
>
> because it reduces to a simple delta of pi(i) functions. Of course,
> that means that a "twin prime" test reduces to a highly optimized delta
> test as well.
>
> I'm double checking my results before I post the template-ized version
> of the HPC (it includes a isprime(n) and istwinprime(n, n2) function
> that I also have to double check, so it's taking a bit longer than I
> expected -- that and I've got the flu -- but bear with me and the code
> will come).

Take your time. Since there are already prime checker implementations no
one is waiting. In fact, unless you can improve upon the existing
implementations no one will care.

> --
> Quinn 

-- 
Lance Lamboy
"I tell them the truth and they think it's hell." ~ Harry S. Truman

Relevant Pages

  • Re: Evaluation of MegaSnakeOil by "expert" + "Primes in P"
    ... MAJOR WORLDWIDE MATHEMATICAL BREAKTHROUGH – MEGANET CORPORATION ... DETERMINISTIC ALGORITHM IN THE WORLD TO WORK IN POLYNOMIAL TIME ... 1,000 bits primality test - 0.5 Sec ...
    (sci.crypt)
  • Re: returning none when it should be returning a list?
    ... It divide next by the list of previous ... Your basic algorithm as described above sounds workable, ... the Sieve of Eratosthenesis a relatively simple ... If you want to look further into the subject, see the Primality Test ...
    (comp.lang.python)
  • Re: Another twin primes conjecture
    ... Just my abbreviations for "Harris' Prime Counter". ... being a quick primality test. ... means that a "twin prime" test reduces to a highly optimized delta test as ... the HPC and istwinprime ...
    (sci.math)