Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cramér model

  1. Oct 20, 2006 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I was trying to do some heuristics with the Cramér model, but I wasn't able to find a good asymptotic for a certain quantity and I thought I'd see if anyone had something good. I did check a few sequences on the OEIS first, but I didn't notice anything there.

    Essentially, I'm looking to predict the rough density/probability of primes in factorial/primorial sequences. Consider [itex]n!+1[/itex], for example. In the naive Cramér model the chance it's prime is

    [tex]\frac{1}{\log(n!)}\approx\frac{1}{n(\log(n)-1)}[/tex]

    but since it is relatively prime to 2, 3, ..., n a better 'probability' would be

    [tex]\frac{1}{n(\log(n)-1)}\prod_{p\le n}\frac{p}{p-1}[/tex]

    My questions:
    1. Is there a name for this extended model? I've seen it before, but I don't recall its name. Actually it's a system of models, one for each positive n, in which the probability of N being prime is 0 if N is divisible by some prime less than or equal to n, and prod{p/(p-1)}/log(N) over the primes less than or equal to n. The original model corresponds to n = 1.
    2. Is there a simple approximation for the product I use above? Its values are 1, 2, 3, 3.75, 4.375, 4.8125, ... for 1, 2, 3, 5, 7, 11, ....
    3. My immediate interest is in A046029, which I've been working on calculating (checking up to 10,000). If my understanding is correct, the above huristic suggests a chance of 1/n (limiting as n becomes large) for each number to be prime, and as such in the sequence. This in turn suggests that the sequence has an infinite number of elements since the harmonic series diverges. Are there any problems with this analysis?
     
    Last edited: Oct 20, 2006
  2. jcsd
  3. Oct 20, 2006 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    I can't say I can recall it having a name of it's own.

    Yes, Merten's theorem.



    Caldwell and Gallot have a paper about the heuristic for the primorials and factorials, http://www.utm.edu/~caldwell/preprints/primorials.pdf
     
  4. Oct 20, 2006 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    When my eyes ran over the formula earlier today (in my new Crandall & Pomerance), I realized that this was what I needed. I wish I realized that earlier.

    This gives

    [tex]\frac{e^\gamma}{n}[/tex]

    as an asymptotic density, which seems to fit my estimates pretty closely. That suggests an infinite number of primes of the form (n!)^2+1 by the divergence of the harmonic series -- right?

    In any case there are no primes of this form from 77 to 7000, by my checking. I'm going to submit this to Sloan's list, with this heuristic (or an improvement?), along with a correction to the entry, when I get to 10,000.
     
  5. Oct 21, 2006 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Should be half that density if you're looking at (n!)^2+1.
     
  6. Oct 21, 2006 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Yeah, sorry. I had it right on my scratch paper.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?