What is the probability that some number of the form $10223 \cdot 2^{n} + 1$ is prime?

Question

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} (1 - \frac{1}{\ln (10223 \cdot 2^{n})})

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?

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? — Gerry Myerson
– Gerry Myerson, Commented Oct 30, 2011 at 9:49
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 composite, so one knows that your set will contain prime(s) if and only if $n ⩾ n_{0}$ for a given $n_{0} ⩾ 2$ , but there seems to be no probabilistic model of any kind involved. Or do you choose $n$ randomly? Please explain. — Did
– Did, Commented Oct 30, 2011 at 10:02
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, \dots, 10223 \cdot 2^{n} + 1$ is prime as $n \to \infty$ ? — student
– student, Commented Oct 30, 2011 at 12:47
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. — David E Speyer
– David E Speyer, Commented Oct 30, 2011 at 16:20
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 \cdot 2^{1} + 1$ or $10223 \cdot 2^{2} + 1$ are or are not prime (they are not). — Did
– Did, Commented Oct 30, 2011 at 16:32

joriki · Accepted Answer · 2011-10-31 09:12:47Z

First, regarding Didier's question about how to assign a probability to something which is either true or false, I highly recommend Towards a Philosophy of Real Mathematics by David Corfield.

In the present context, we can ask: If we had some way of determining whether there is at least one prime in this set, what would be the maximal price at which a rational self-interested actor would buy a bet to receive $€ 1$ in case it turns out that there is one?

This will depend in a complicated way on the actor's knowledge of the history of the Sierpinski problem: How far this set has been probed so far; how far the corresponding sets for other numbers that didn't turn out to be Sierpinski numbers had to be probed to find primes, etc.

But I'm guessing that your question isn't intended to take all this into account, and rather aims at a hypothetical rational self-interested actor who has no specific knowledge of the Sierpinski problem, but is aware of more general facts about primes, including density results related to the prime number theorem. Such an actor might calculate the "probability" of all numbers in this set being composite on the basis of an independence assumption roughly as

p = \prod_{n} (1 - \frac{1}{\log (10223 \cdot 2^{n} + 1)}) \approx \prod_{n} (1 - \frac{1}{\log 10223 + n \log 2})

and thus

\log p \approx \sum_{n} \log (1 - \frac{1}{\log (10223 \cdot 2^{n} + 1)}) \approx - \sum_{n} \frac{1}{\log 10223 + n \log 2} .

This logarithm diverges to $- \infty$ , so our hypothetical self-interested actor would buy the bet at any price below $€ 1$ .

Given that this model predicts that there shouldn't be any Sierpinski numbers at all but we know that there are, the independence assumption is unwarranted and it would be unwise to base any bets on it. To arrive at a more sound assessment of the value of such a bet would require an in-depth analysis of the history of the Sierpinski problem.

[Edit in response to the comments:]

It was rightly pointed out that I glossed over the possibility that there might be Sierpinski numbers despite the "probability" for this being $0$ . However, my conclusion that a rational self-interested actor would abandon the naive model based on the independence assumption upon learning of the existence of Sierpinski numbers was correct.

Let's denote by $I$ the applicability of the independence assumption, by $S$ the existence of a Sierpinski number and by $A$ the existence of at least one prime in the set under consideration. Let's say the actor originally had degree $P (I)$ of belief in the applicability of the independence assumption and didn't know the first thing about Sierpinski numbers. Then the value of the bet to her would be $P (A) = P (I) P (A | I) + P (\neg I) P (A | \neg I)$ , where $P (A | I) = 1$ is the probability calculated above and $P (A | \neg I)$ is the probability she would ascribe to $A$ if the independence assumption were found not to apply. If her original degree of belief in the independence assumption is very high, that is, nearly $1$ , the value of the bet is nearly $€ 1$ .

Now upon learning that there are in fact Sierpinski numbers, assuming that this would influence her determination of $P (A)$ only via $P (I)$ , she would perform a Bayesian update as follows:

\begin{array}{rcl} P (A | S) & = & P (I | S) P (A | I) + P (\neg I | S) P (A | \neg I) \\ = & \frac{P (I \cap S)}{P (S)} P (A | I) + \frac{P (\neg I \cap S)}{P (S)} P (A | \neg I) \\ = & P (A | \neg I) \end{array}

since $P (I \cap S) = 0$ , as the probability for $S$ under the independence assumption is zero. Thus $P (A | S) = P (A | \neg I)$ , that is, learning of the existence of Sierpinski numbers has the effect of abandoning the independence assumption.

Which chapters of "Towards a Philosophy of Real Mathematics" you mean are interesting? — boumol
– boumol, Commented Oct 30, 2011 at 16:43
All this is well and good, My Lord, but what is this probability at the end? Ya know, a number, possibly between zero and one... // More seriously, this comment of mine you kindly allude to in your answer merely signals that evoking the probability that the number $10223 \cdot 2^{n} + 1$ is or is not prime, for a given $n$ (as the OP was very nearly doing in the pre-@David version of the post and as the OP squarely did in a subsequent comment), is absurd. // Thanks for your post. — Did
– Did, Commented Oct 30, 2011 at 16:47
@joriki I think you forget that an event of probability zero can still happen. Since you get a probability of zero, it doesn't mean the event cannot happen, it only means it is improbable to happen. Wouldn't your probability still be zero if the events are independent, and only finitely many numbers are prime? Or a set of zero density? — N. S.
– N. S., Commented Oct 30, 2011 at 17:10
@Didier: I disagree -- if $n$ is high enough that we can't immediately check the truth of the statement on a computer, it makes just as much sense to speak of the probability that $10223 \cdot 2^{n} + 1$ is prime as it does for the same statement with an existential quantifier over $n$ . It makes sense under some interpretations of probabilities and not under others. I don't see any difference in that regard between a given $n$ and an existentially quantified $n$ . — joriki
– joriki, Commented Oct 30, 2011 at 23:00
This answer has received two downvotes. Please leave comments to explain the reasons for downvotes; see the FAQ: "If you see misinformation, vote it down. Add comments indicating what, specifically, is wrong." This is an interesting and controversial topic, and we could be having a productive discussion about it. — joriki
– joriki, Commented Oct 31, 2011 at 14:28

Stack Exchange Network

What is the probability that some number of the form $10223 \cdot 2^{n} + 1$ is prime?

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

Strictly Necessary Cookies

Performance Cookies

Functional Cookies

Targeting Cookies

What is the probability that some number of the form 10223⋅2n+110223⋅2n+1 is prime?

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions

What is the probability that some number of the form $10223 \cdot 2^{n} + 1$ is prime?