[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1515.0. "prime number distribution" by STAR::ABBASI () Sun Nov 03 1991 22:26

    
    How many primes are there between  N!+2 and N!+N for any N ?
    and how did you find the answer ?
    
    /Nasser
T.RTitleUserPersonal
Name
DateLines
1515.1FYI, info on bookSTAR::ABBASISun Nov 03 1991 22:3922
    FYI,
    the book that mentioned the above, is called "Mathematics: the new
    golden age" by Keith Devlin. ,1988, 280 pages, cost $8.95. a very good 
    book, contents are :
    1. prime numbers, factoring and secret codes.
    2. sets, infinity and the undecidable.
    3. number systems and the class number problem
    4. beauty from chaos.
    5. simple groups
    6. hilbert tenth problem
    7. the four-colour problem
    8. fermat's last theorem
    9. hard problems about complex numbers <-- here is a very good outline
       of the riemman hypothesis, i dont understand it yet, but according
       to the auther, it is one of the most important unsolved problems in
       mathematics ! that is a good challange , anyone wants a PhD thesis
       topic? here is one !
    10. knots and other topolgical matters
    11. efficency of algorithms.
    
    /Nasser
    
1515.2infoBODACH::CMORRISEven is evil, truth a prime numberMon Nov 04 1991 06:044
    Publisher ? ISBN number ?
    
    Thanks
    CJ
1515.3ELIS::GARSONV+F = E+2Mon Nov 04 1991 09:1415
    re .0
    
    For completeness... there are no primes in that range.
    
    Since N! = 1 * 2 * 3 * ... * N,
    
    k | N! for k = 2,...,N
    
    so k | N! + k for k = 2,...,N
    
    so N! + k is not prime for k = 2,...,N
    
    
    And a follow up question...what about N! + 1
    Is it always prime? never prime? Is there some pattern?
1515.4HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Mon Nov 04 1991 11:4714

N!+1 can't always be prime.


"proof"

	It is impossible to find a closed form f(N) which is prime for all
	N.  If N!+1 were always prime, this would be violated.

Not to mention the fact that 5! is 5*4*3*2=120, and 121 is divisible by 11.
So, as long as 11 can be proved to be unequal to 1 (left to reader)...


1515.5Could you prove that please.LUPUS::J_JOSEPHWolf in the fold.Mon Nov 04 1991 12:066
> 	It is impossible to find a closed form f(N) which is prime for all
> 	N.  

But can you prove that?

-Jonathan
1515.6Prime generatorsCIVAGE::LYNNLynn Yarbrough @WNP DTN 427-5663Mon Nov 04 1991 12:4216
In fact there is a simple formula that always generates primes, of the form
[n**A] - i.e. it has been proved (by Selberg, I think) that there exists a
real constant A such that the integer part of n to the A is always prime 
for integer n > 2.
[I am recalling this from 30 years back, and the details are fuzzy. I think
someone established 2<A<3, but I may be wrong. I haven't seen anything about 
approximations to A.] 

Osman's comment is correct about polynomials with integer coefficients:
there is no p(n) that produces primes for all values of n.

I also saw recently an infinite matrix whose elements are generated by a
simple formula in {x,y}, and a simple function P, such that if n is in the
matrix then P(n) is composite, and if n is not in the matrix then P(n) is
prime. I will try to reproduce it here, if I can find it; I think it was in
a recent JRM. 
1515.7HERON::BLOMBERGTrapped inside the universeMon Nov 04 1991 12:453
    
    Could it be true, that if N+1 is prime, then N!+1 is divisible
    by N+1 ?
1515.8Wilson's TheoremCIVAGE::LYNNLynn Yarbrough @WNP DTN 427-5663Mon Nov 04 1991 13:459
>    Could it be true, that if N+1 is prime, then N!+1 is divisible
>    by N+1 ?

Yes. This is called Wilson's theorem, which is actually more general:

	If *and only if* N+1 is prime, then N!+1 is divisible by N+1.

so this is a test (albeit expensive) for primality. A proof can be found in 
most Num Thy texts.
1515.9ZFC::deramoShout! A little bit louder now...Mon Nov 04 1991 13:5312
>.4
>	It is impossible to find a closed form f(N) which is prime for all
>	N.  If N!+1 were always prime, this would be violated.

>.6
>Osman's comment is correct about polynomials with integer coefficients:
>there is no p(n) that produces primes for all values of n.

	f(N) = p(n) = 17

:-)
Dan
1515.10ELIS::GARSONV+F = E+2Tue Nov 05 1991 05:0112
    re .various
    
    So far we have
    
    N!+1 is prime for the special cases N=1,2
    
    N!+1 is divisible by N+1 when N+1 is prime (and so N!+1 is not prime)
    
    
    N!+1 is not divisible by N+1 when N+1 is not prime
    This leaves open the question as to whether N!+1 is prime when N+1 is
    not prime. Any takers?
1515.11more book infoSTAR::ABBASITue Nov 05 1991 11:375
    soeone asked about the book info:
    publisher is pelican, ISBN # 0-14-022728-8
    got my copy from Barnes and Nobel in nashua. you could order one from
    there too.
    /nasser
1515.12N!+1 is not prime when N+1 is not primeSTAR::ABBASITue Nov 05 1991 11:4610
    ref  <<< Note 1515.10 by ELIS::GARSON "V+F = E+2" >>>
    >This leaves open the question as to whether N!+1 is prime when N+1 is
    >not prime. Any takers?
    
    proof by producing one counter example
    ---------------------------------------
    N= 5, N+1= 6 , not prime
    
    N! = 120, N!+1 = 121 , but 121 not prime (121 is divided by 11 with no
    reminder)
1515.13Proof that N+1 | N!+1 => N+1 is primeELIS::GARSONV+F = E+2Wed Nov 06 1991 04:2219
re .8
    >Yes. This is called Wilson's theorem, which is actually more general:
    >	If *and only if* N+1 is prime, then N!+1 is divisible by N+1.

Suppose that N+1 | N!+1

Let z | N+1, therefore

Case A). z = N+1
Case B). z < N+1

     z | N+1  and  N+1 | N!+1   =>   z | N!+1
    but z < N+1   =>   z <= N   =>   z | N!
    therefore z | 1
    so z = 1

Combining A) and B)

z | N+1 => z = N+1 or z = 1, so by definition N+1 is prime
1515.14Proof that N+1 is prime => N+1 | N!+1ELIS::GARSONV+F = E+2Wed Nov 06 1991 07:3061
1515.15what is the status of this formula?STAR::ABBASIWed Mar 18 1992 05:0516
    i'd like to know if this is a theory or a hypothesis ?
    
           PI(x) LOG(x)
          ------------- = 1 ,   when x grows very large
                x
    
    Where PI(x) is the number of primes not exceeding x.
    
    i wanted to know if we know the above is known to be true or is still 
    need to be proved?
    
    thanks,
    /nasser
            
    
    
1515.16Prime number theorem3D::ROTHGeometry is the real life!Wed Mar 18 1992 10:2818
    It looks right - there are some even sharper estimates on the
    distribution of primes that are amazingly accurate.  The simplest
    is a logarithmic integral (that I don't recall off the top of my head)
    but correction terms can be added to get an even better fit.  These
    go back to Gauss & Legendre, but were first proven in the late
    19'th century.  Riemann originated the most accurate estimates.

    The simplest proof I know of uses complex analysis, but there is an
    "Elementary" proof by Selberg.

    If you look in Hans Reisel's book on prime numbers he discusses
    these approximations, as well as some amazing algorithms that will
    actually *count* the primes within an interval and not just approximate
    their density.

    Selberg's proof is in Hua's book on number theory.  It's many pages...

    - Jim
1515.17ZFC::deramoDan D'EramoWed Mar 18 1992 12:4412
I thought the "elementary" proof was by Selberg and Erdos.

I believe it was proven much earlier that if the limit
exists, then it must be one.  The harder part was showing
that the limit does indeed exist.  I don't remember who
gave the first (nonelementary) proof.

I *think* that "elementary" in this context means can be
done within first order Peano Arithmetic in the language
{0,successor,+,*}.

Dan
1515.18RieselHERON::BLOMBERGTrapped inside the universeWed Mar 18 1992 14:004
    .16
    
    Just in case someone looks for the book, his name is Riesel.