Veryprimes, Quiteprimes

[Antreas P. Hatzipolakis]

FWD MESSAGE -----------------------------------------------------------------

Subject: Re: Veryprimes defined
Author: Malcolm Harper <pirround at NOSPAMhotmail.com>
Date: Fri, 10 Sep 1999 21:01:00 GMT
Newsgroups: sci.math


Jim Ferry <jferry at uiuc.edu> wrote in message
news://37D7D610.3522DF2B@uiuc.edu...
> Clive Tooth wrote:
> >
> > Informally, a number is a veryprime if it is a long way from being
divisible
> > by its trial factors.
> >
> > More formally: a positive integer, V, is a veryprime iff:
> >
> > * V is prime.
> >     and
> > * For every odd prime, p, which is less than the square root of V, we
have:
> >   V = (p-1)/2 (mod p) or V = (p+1)/2 (mod p).
>
> Being somewhat looser about "long way from divisible" doesn't add many
> more veryprimes.  Consider these three versions of the definition:
>
> An integer V > 1 is veryprime iff all primes p <= sqrt(V) satisfy:
>
> |2 (V mod p) - p| <= 1        (very strong)
> |2 (V mod p) - p| <= sqrt(p)  (strong)
> |2 (V mod p) - p| <= p/2      (weak)
>
> Pardon the computery use of "V mod p" (0 <= (V mod p) < p).
>
> Then the (original) very strong veryprimes are
> 2, 3, 5, 7, 11, 13, 17, 19, 23, 37, 43, 47, 53, 67, 73, 137.
>
> The strong veryprimes are the above together with
> 227.
>
> The weak veryprimes are (both of) the above together with
> 103, 107, 157, 173, 347, 487, 773.
>
> (I checked the first 100,000 primes in each case.)
>
> Being much looser produces a more interesting definition:
>
> An integer V > 1 is *quiteprime* iff all primes p <= sqrt(V) satisfy:
>
> |2 (V mod p) - p| <= p + 1 - sqrt(p).
>
> Of the first 10 primes, 10 are quiteprime; of the first 100, 73; and
> so on, as indicated here:
>
> 10/10, 73/100, 256/1000, 504/10000, 584/100000
>
> Anyone care to comment (rigorously or heuristically) on the
> finiteness and/or asymptotic density of overprimes?
Here Jim means quiteprimes as he points out in another post.

Lets generalize the problem a bit.
For each prime p choose w(p) residue classes (mod p) to be excluded and
suppose w(p)>=c*p^a log p for some positive constants a and c.  Fix t.

Call a natural number n interesting if n is not in any of the w(p) excluded
residue classes (mod p) for any p <= n^t.  Very strong veryprimes have w(p)
= p-2 so they are interesting with t = 1/2 and a in (0,1).  Similarly strong
and weak veryprimes are interesting for the same a and t.  For quiteprimes
choose t=1/2 and a in (0,1/2).  They are interesting, but not quite so
interesting as veryprimes.

Once a,t and the excluded classes are chosen, let N(X) be the number of n<=X
that are interesting.
N(X) - N(X^(1/2))
= # n : X^(1/2)<n<=X, n not excluded for any p <= n^t
<= # n : n<=X, n not excluded for any p <= X^(t/2)
A probable value for this last would be
X*prod(p<=X^(t/2),(1 - (w(p)/p) ) ) so that
N(X) - N(X^(1/2)) <<  X*exp(-K*X^(a*t/2)) for some K>0.
The right-hand term goes to zero quickly enough that the telescoping series
formed by adding terms on the left is bounded.  This implies that the number
of quiteprimes is finite.

Notes:
1.  Of course this argument fails.  Choose x_1 and for each prime p<=x_1
exclude all classes except x_1 (mod p).  Now inductively set x_n = x_(n-1) +
prod(p<=x_(n-1),p) then for primes p such that x_(n-1)<p<=x_n exclude all
classes but x_n (mod p).  This produces an infinite set of interesting
numbers with t=1 and w(p)=p-1 so that a can be as large as you like in
(0,1).  The x_n grow very quickly: x_n ~ exp(x_(n-1)).
[Q]  Are there better counter-examples.  I'm sure there are.

2.  What if we formalize this using the large sieve.  I think we get
something like
N(X) - N(X^(1/2)) << X^(1-a*t/2).  So
N(X) << X^(1-a*t/2)
This would prove a zero density for quiteprimes.  I'm sure the bound can be
improved.  (How much?)

Malcolm

END ---------------------------------------------------------------



APH