13
$\begingroup$

I (David Speyer) took the liberty of doing a fairly major rewrite of this question. I hope I haven't gone too far, but I think there is an interesting question hiding here.


Sierpinski proved that there are infinitely many positive integers $k$ such that $k 2^n+1$ is composite for all positive $n$. Such a $k$ is called a "Sierpinski number of the second kind", which I'll shorten to "Sierpinski number" for the rest of this question. The smallest $k$ which has been proved to be a Sierpinski number is $78557$. However, there are no known primes of the form $10223 \cdot 2^n+1$, so $10223$ could be a Sierpinski number.

If you were to bet that $10223$ was a Sierpinski number, with the bet refereed by a perfectly honest, omniscient alien being, what odds would you accept?

This is particularly interesting, because a naive model suggests that there are no Sierpinski numbers. A naive model would be: for each $n$, independently pick a random integer uniformly between $10223 \cdot 2^n+1$ and $10223 \cdot 2^n (1.001)$. What is the probabilities that these are all composite?

Using the prime number theorem, we wind up looking at $$\prod_{n=1}^{\infty} \left( 1- \frac{1}{\ln(10223 \cdot 2^n)} \right)$$ and this product diverges to $0$. But this product also diverges to $0$ if we replace $10223$ by $78557$, contradicting Sierpinski's theorem.

So the challenge is to give a better probabilistic model, and calculate what result it gives. In one sense, the answers are subjective -- you will not be able to rigorously prove one model is better than another. But there are certainly arguments to be made for and against various models. And, if a perfectly honest, omiscient, alien bookie shows up at your door, don't you want to know how to bet?

  • 1
    The question in the body isn't the question in the title. Can you edit one or the other to bring them into alignment, so we know what you really want?2011-10-30
  • 1
    Regarding the last sentence of the present version of the post, you could explain how you assign a probability to something which is either true or false. For example, if $n=1$, your set is $\{20447\}$, and $20447$ [happens to be](http://www.mathwarehouse.com/arithmetic/numbers/prime-number/prime-factorization-calculator.php) composite, so one knows that your set will contain prime(s) if and only if $n\geqslant n_0$ for a given $n_0\geqslant2$, but there seems to be no probabilistic model of any kind involved. Or do you choose $n$ randomly? Please explain.2011-10-30
  • 1
    I means that Sierpinski's problem have been investigates for small values of $n$ so if $n$ is small then the probability is zero. But for large $n$ we don't know if the numbers are composites or not. So can we use for example prime number theorem to compute what is the probability that at least one number of the form $10223\cdot 2^1+1,\cdots ,10223\cdot 2^n+1$ is prime as $n\to \infty$?2011-10-30
  • 1
    joricki posted his answer while I was editing; not surprisingly, he makes many of the same points I do. Sadly, his model is still the naive one.2011-10-30
  • 0
    student: these are subtle matters and my previous comment asked for somewhat more cautious formulations from you. As if to confirm my worries, the assertion in your last comment that *if $n$ is small then the probability is zero* is, I think, meaningless. There is simply no way to define a probability that $10223\cdot2^1+1$ or $10223\cdot2^2+1$ are or are not prime (they are not).2011-10-30
  • 0
    @David: There is a misprint in your definiton of "Sierpinski number of the second kind". It says "for all k", and it should be "for all n".2011-10-30
  • 0
    @David: Corrected a typo in the statement of Sierpinski's result.2011-10-30
  • 0
    @David: Oh, and many thanks for your intervention here.2011-10-30
  • 0
    @David: Thanks! The question seems to be much better as my first version.2011-10-30
  • 0
    The number $N=10223\cdot2^n+1$ is not random. For one thing, it's odd, which pushes up its chances (suitably interpreted) of being prime. On the other hand, if $n$ is even, $N$ is a multiple of 3. If $n$ is 3 mod 4, $N$ is a multiple of 5. If $n$ is 1 mod 3, $N$ is a multiple of 7. Etc. A first attempt at a better probabilistic model would take these facts into account.2011-10-31
  • 0
    Related answer [here](http://math.stackexchange.com/questions/77210/probabilistic-proof-of-existence-of-an-integer/77224#77224).2011-11-01
  • 0
    You might interested in this paper:[Heuristics](http://www.utm.edu/staff/caldwell/preprints/Heuristics.pdf) by Chris Caldwell. I think it gives good hints to answer your question how to calculate the probilities and also wraps up the issues brought up by Didier/Joriki in a *Warning about Heuristics*.2012-05-22

1 Answers 1