On Friday 28 January 2005 06:40, you wrote:

> What is known about primes of this form: n!/n#+1

Mike Oakes already gave the asymptotics of primes of this form in a very

recent post, but I'll go through a similar argument and arrive at my own,

slightly modified formula. Whether it's better remains to be seen.

Just a comment before we start: what about the symmetric from n!/n# - 1? I

don't know why we shouldn't analyze it.

There is a theorem of Legendre that says the following: n! is divisible by p

with multiplicity

sum_{k >= 1} floor(n/p^k),

while n# is divisible by each p up to n with multiplicity one. Dividing one by

another, it's not hard to see that only factors of multiplicity 1 are

canceled in n!. These are exactly those for which floor(n/p) = 1 (no use

thinking about higher powers, because if floor(n/p) = 1, then floor(n/p^2) =

floor(n/p^3) = ... = 0). It's not hard to see these are the primes from

floor(n/2) to n itself.

Thus, n!/n# is divisible by all primes up to floor(n/2). I'll drop the floor()

operation for the upcoming asymptotic analysis. From my previous post, you

should know by now that n!/n# plus/minus 1 isn't divisible by any of these

primes, by Euclid's argument.

Assuming that n!/n# plus/minus 1 are `random' numbers (i.e. nothing is known

about their factors), they would be prime with probability 1/log(n!/n#). I'm

dropping the plus/minus 1 at the end because it doesn't affect the result,

either asymptotically or in practice. But they're not random, they're

divisible by all primes up to n/2. Thus we use Mertens's theorem to adjust

the probability by exp(gamma) log(n/2) = exp(gamma) (log(n) - log(2)) =

exp(gamma) (log(n) - 0.693). We also multiply this probability by 2 to

account for the two forms n!/n# + 1 and n!/n# - 1.

Now we need to estimate log(n!/n#) = log(n!) - log(n#). The first term is well

known to be n(log(n) - 1). The second term, according to the paper by Chris

Caldwell and Yves Gallot that Mike Oakes linked to on a previous post, is

approximately n itself. (A side note: I computed something similar to

log(n#), except that a prime p appeared to the highest power < n, i.e.

2^floor(log_2 n) 3^floor(log_3 n) ... and indeed these values are very close

to n itself, I believe even closer than log(n#).) Anyway...

log(n!/n#) = log(n!) - log(n#) = n(log(n) - 1) - n = n(log(n) - 2).

Thus, the number of compositorial primes of both forms (plus and minus) up to

n is expected to be

sum_{k=1..n} 2 exp(gamma) log(k/2)/(k(log(k) - 2)).

And asymptotically (i.e.log(k/2) ~ log(k), k(log(k) - 2) ~ k log(k)) we have

sum_{k=1..n} 2 exp(gamma) log(k)/(k log(k)) = sum_{k = 1..n} 2 exp(gamma)/k,

which, somewhat surprisingly, is nearly the same formula for n! plus/minus n#

plus/minus 1, except that we only have two possible forms here instead of

four, accounting for the factor 2 of difference.

Let's try this formula with the data provided by Mike Oakes. For n <= 10000,

34.27 primes were expected, while the actual count is 44. But let's consider

1000 <= n <= 10000 for a more accurate picture: in that case 9.995 primes

were expected but 8 were found. Again, anyone willing to throw more CPU power

at the problem so we can verify the asymptotics is welcome to do so.

Décio

[Non-text portions of this message have been removed]