In a message dated 24/08/03 02:17:15 GMT Daylight Time, jfoug@... writes:

> this was a fun problem. I have found the smallest P(10) It is
> 39 digits long. 110100000010101111110001010011001110001 is the
> bit pattern.

Here's a back-of-an-envelope calculation as to why the smallest P(10) is of
this size.

Let N be an n-bit pattern which is a P(10), with m (<=n) "1" bits.

As Richard observed in his original post, m cannot have 2, 3, 5 or 7 as a
factor.
To join up the dots in his assertion:-
m cannot have 2 as a factor because, to base 3, N = m mod 2; and similarly
for the others.

From now on, m is to have this property, so N (considered to any base from 2
thru 10) is prime to 210.

Define the probability p = (1-1/2)*(1-1/3)*(1-1/5)*(1-1/7) = 8/35.

If any large number X is known not to be divisible by 2, 3, 5 or 7, the
probability of X being prime is enhanced by the factor 1/p = 35/8, and so is
(35/8)/log(X) by the PNT.

When interpreted as number to base b, N is of size b^n, so the probability
that N is prime is (35/8)*(1/log(b^n) = (35/8)/(n*log(b)).

The probabilities for the 9 different values of N to the 9 different bases 2
thru 10 can be expected to be independent.

So the probability that N is P(10) is:-
(35/8)^9/(n^9*log(2)*...*log(10)) = (9445/n^9)

We would need to do a proper Poisson-type calculation, but (on the back of an
envelope, remember) there are about (8/35)*2^n n-bit numbers with no. of bits
m prime to 210.

So the expected no. of P(10)'s with n bits = (8/35)*2^n*(9445/n^9)

This is 1 for n = 35 and a bit.

So either Jim was unlucky (Poisson strikes again...), or there are some
correction factors which I have overlooked and which I'm sure you eagle-eyed
readers will find.

(Of course, a similar analysis should apply to P(s) for any s; so one could
see how it shapes up for s=9, 8, ..; and note that for s=12 we get
significantly fewer candidate N's, since m must then be prime to 11 too; but I
have now
run out of envelope:-)

Mike


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