Is Every Prime > 3 a Sum of a Prime and a Power of Two?

[CRGreathouse]

yes, S' infinite <==> S infinite, but to prove S' infinity seems to be as difficult as the original problem... if we prove that we could put all the primes into these two sets:

1. S is infinite ==> S' is infinite *
2. S' is infinite ==> S is infinite

* S infinity ==> S' infinity because if q = p + 2^n, q > 2^n ==> q - 2^n = p positive

Certainly there are many primes not in either S or S', so there goes that approach.

 

[al-mahed]

Certainly there are many primes not in either S or S', so there goes that approach.

Sorry about my poor english but I did not follow you... you mean that in fact there are primes not in S or S'? Primes that cannot be written as p + 2^n or p - 2^n?

 

[dodo]

Post #9 shows examples of primes not of the form p + 2^n. I imagine that finding counterexamples for p - 2^n (in particular, checking those on A065381) is harder, since there is no limit to p or 2^n.

 

[al-mahed]

Post #9 shows examples of primes not of the form p + 2^n. I imagine that finding counterexamples for p - 2^n (in particular, checking those on A065381) is harder, since there is no limit to p or 2^n.

I made another conjecture: those primes that cannot be written as p + 2^n could be written as p - 2^n

Consider the two sets:

S = set of primes of the form p + 2^n
S' = set of primes of the form p - 2^n

If we prove that all primes should be in one of these two sets the infinity of the two sets will be proved.

In fact post #5 shows that the primes not in S may could be found in the infinity of the negative integer line as -p + 2^n, which I wonder is the same thing of find this primes in the infinity of the positive integer line as p - 2^n. We can search to infinity for them, increasing both p and 2^n until find a match.

This is why $$S \subset\ S'$$, I think. This is why trying to show that primes are in the form p + 2^n contain "gaps" = p - 2^n.

And now, by Tchebychef: for m > 1 there is at least one prime p such that m < p < 2m

if we put m = 2^n, n a natural > 0 ==> 2^n < p < 2^(n+1)

perhaps this theorem could be usefull

 

[al-mahed]

Let all positive whole number be written as a sum of power of two:

$$1 = 2^0$$
$$2 = 2^1$$
$$3 = 2^0 + 2^1$$
$$4 = 2^2$$
$$5 = 2^0 + 2^2$$
$$6 = 2^1 + 2^2$$
$$7 = 2^0 + 2^1 + 2^2$$
$$8 = 2^3$$
$$9 = 2^0 + 2^3$$
$$10 = 2^1 + 2^3$$
$$11 = 2^0 + 2^1 + 2^3$$
$$12 = 2^2 + 2^3$$
$$13 = 2^0 + 2^2 + 2^3$$
$$14 = 2^1 + 2^2 + 2^3$$
$$15 = 2^0 + 2^1 + 2^2 + 2^3$$
$$16 = 2^4$$
$$17 = 2^0 + 2^4$$
$$18 = 2^1 + 2^4$$
$$19 = 2^0 + 2^1 + 2^4$$
$$20 = 2^2 + 2^4 etc...$$

We know by Tchebychef: for m > 1 there is at least one prime p such that m < p < 2m

if we put m = 2^n, n a natural > 0 ==> 2^n < p < 2^(n+1)

We know by Gauss: the number of primes from 1 to x is approximately =$$\frac{x}{ln(x)}$$

The number of primes between $$2^n$$ and $$2^{n+1}$$ is approximately =

$$\frac{2^{n+1}}{ln(2^{n+1})} - \frac{2^n}{ln(2^n)}$$ = $$\frac{2^n}{ln(2)}*(\frac{2}{n+1} - \frac{1}{n})$$ = $$\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})$$

and we know that $$2^n > n^2$$ for $$\geq 3$$ ==> $$\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})$$ diverges for n --> $$\infty$$

for n increasing the Tchebychef's theorem underestimates the amount of primes

 

[CRGreathouse]

I'm not sure why you're measuring the primes between $2^n$ and $2^{n+1}$. The relevant probabilities are

$$1/\ln(p+2)$$
$$1/\ln(p+4)$$
$$1/\ln(p+8)$$
. . .

Thus the relevant question is: Does $$(1-1/\ln(p+2))(1-1/\ln(p+4))\cdots$$ diverge to 0?

Ignoring p, this is $$(1-k)(1-k/2)(1-k/3)\cdots$$ for $$k=1/\ln2$$.

$$\prod_n(1-k/n)=\exp\sum_n\ln(1-k/n)=\exp\left(-\sum_n k/n+k^2/2n^2+\cdots\right)\ge\exp\left(-\sum_n k/n\right)=e^{-\infty}=0$$

so the product is 0 and so we do expect that all odds are of the form $p-2^n$ for prime p and some positive n.

 

[al-mahed]

This is the point: seems to me that you already are considering that there are such primes of the form $$p + 2^n$$, and we don't know yet. Or did I not understand some particular point?

My idea on measuring the primes between $2^n$ and $2^{n+1}$:

Lets discriminate the numbers in classes according to the highest exponent, such that the nth-class has $2^n$ numbers, etc. Considering some prime number in nth-class like $2^0 + 2^a + 2^b + 2^n$, we should have $2^0 + 2^b + 2^n$, $2^0 + 2^a + 2^n$ or $2^0 + 2^a + 2^b$ = prime, or if for some reason this particular prime couldn't be written of the form $p + 2^n$, we should have $2^0 + 2^a + 2^b + 2^n + 2^k$ a prime number for some $2^k$ exponent, writting this prime in the $p - 2^n$ form.

My idea: $$\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})$$ should give us the number of primes expected in the nth-class, and then we'll be able do find the probability that some particular prime number have a permutation of the exponents that represents another prime number. By doing these calculations I hope that the probability increases when n increases.

Honestly I don't feel that these statistical procedures could give us an absolute proof, only heuristics evidences.

I'm not sure why you're measuring the primes between $2^n$ and $2^{n+1}$. The relevant probabilities are

$$1/\ln(p+2)$$
$$1/\ln(p+4)$$
$$1/\ln(p+8)$$
. . .

 

[al-mahed]

* because obviously $$2^0 + 2^a + 2^b + 2^n + 2^k - 2^k$$ is the same prime, so we can keep adding exponents until find some k such that $$2^0 + 2^a + 2^b + 2^n + 2^k$$ represents a prime; and as we know that for every prime of the form $$p - 2^n$$ there is a prime of the form $$p + 2^n$$, this should give us our proof.

ps: I had to write this sentence here because TEX become crazy and change the expressions

 

[CompuChip]

compuchip, could you write an algoritm that expresse a prime as a sum of the minor prime possible and powers of two?

Sure I will do that, if it makes you happy

The minor prime possible is always 3 (or 2, if you allow 2^0), since the difference between 3 and the prime (or any positive integer, for that matter) can be expressed (uniquely) as a sum of powers of two; think of its binary representation.

This gives for the first 100 primes

{5,{1}}
{7,{2}}
{11,{3}}
{13,{3,1}}
{17,{3,2,1}}
{19,{4}}
{23,{4,2}}
{29,{4,3,1}}
{31,{4,3,2}}
{37,{5,1}}
{41,{5,2,1}}
{43,{5,3}}
{47,{5,3,2}}
{53,{5,4,1}}
{59,{5,4,3}}
{61,{5,4,3,1}}
{67,{6}}
{71,{6,2}}
{73,{6,2,1}}
{79,{6,3,2}}
{83,{6,4}}
{89,{6,4,2,1}}
{97,{6,4,3,2,1}}
{101,{6,5,1}}
{103,{6,5,2}}
{107,{6,5,3}}
{109,{6,5,3,1}}
{113,{6,5,3,2,1}}
{127,{6,5,4,3,2}}
{131,{7}}
{137,{7,2,1}}
{139,{7,3}}
{149,{7,4,1}}
{151,{7,4,2}}
{157,{7,4,3,1}}
{163,{7,5}}
{167,{7,5,2}}
{173,{7,5,3,1}}
{179,{7,5,4}}
{181,{7,5,4,1}}
{191,{7,5,4,3,2}}
{193,{7,5,4,3,2,1}}
{197,{7,6,1}}
{199,{7,6,2}}
{211,{7,6,4}}
{223,{7,6,4,3,2}}
{227,{7,6,5}}
{229,{7,6,5,1}}
{233,{7,6,5,2,1}}
{239,{7,6,5,3,2}}
{241,{7,6,5,3,2,1}}
{251,{7,6,5,4,3}}
{257,{7,6,5,4,3,2,1}}
{263,{8,2}}
{269,{8,3,1}}
{271,{8,3,2}}
{277,{8,4,1}}
{281,{8,4,2,1}}
{283,{8,4,3}}
{293,{8,5,1}}
{307,{8,5,4}}
{311,{8,5,4,2}}
{313,{8,5,4,2,1}}
{317,{8,5,4,3,1}}
{331,{8,6,3}}
{337,{8,6,3,2,1}}
{347,{8,6,4,3}}
{349,{8,6,4,3,1}}
{353,{8,6,4,3,2,1}}
{359,{8,6,5,2}}
{367,{8,6,5,3,2}}
{373,{8,6,5,4,1}}
{379,{8,6,5,4,3}}
{383,{8,6,5,4,3,2}}
{389,{8,7,1}}
{397,{8,7,3,1}}
{401,{8,7,3,2,1}}
{409,{8,7,4,2,1}}
{419,{8,7,5}}
{421,{8,7,5,1}}
{431,{8,7,5,3,2}}
{433,{8,7,5,3,2,1}}
{439,{8,7,5,4,2}}
{443,{8,7,5,4,3}}
{449,{8,7,5,4,3,2,1}}
{457,{8,7,6,2,1}}
{461,{8,7,6,3,1}}
{463,{8,7,6,3,2}}
{467,{8,7,6,4}}
{479,{8,7,6,4,3,2}}
{487,{8,7,6,5,2}}
{491,{8,7,6,5,3}}
{499,{8,7,6,5,4}}
{503,{8,7,6,5,4,2}}
{509,{8,7,6,5,4,3,1}}
{521,{9,2,1}}
{523,{9,3}}
{541,{9,4,3,1}}

where a line like
{491,{8,7,6,5,3}}
should be read as
$$491 - 3 = 2^8 + 2^7 + 2^6 + 2^5 + 2^3$$.

In the attachment I have plotted the occurring powers for the first 1000 primes (except 2 and 3). Have fun

PS the Mathematica code, in case anyone wants to reproduce this

FindPowers[n_] := Module[{m = n - 3, result = {}}, 
  While[m > 0, AppendTo[result, Floor[Log[2, m]]]; m -= 2^Floor[Log[2, m]]]; 
  result
]

ListPlot[
  Function[{number, powers}, {number, #} & /@ powers] @@@ Table[{n, FindPowers[Prime[n]]}, {n, 3, 1000}], 
  Ticks -> {Automatic, Range[0, 12]}
]

 

[al-mahed]

Sure I will do that, if it makes you happy

Thank you CompuChip! You did a very good job !

This is the point: seems to me that you already are considering that there are such primes of the form $$p + 2^n$$, and we don't know yet. Or did I not understand some particular point?

CRGreathouse, nevermind what I said, I do understand now reading more carefully what is your idea. I was just confused because:

1. using numbers like $$p+3, p+5, p+9, p+17,..., p+2^n+1$$, or $$p+1, p+3, p+7, p+15,..., p+2^n-1$$ to calculate the convergence to zero, seems to return almost the same result, so I think that this approach may not work

2. this seems to work only with p fixed, so we cannot search for $$p - 2^n$$ because we cannot calc the log of negative numbers (in case of to exclude a fixed p), and specially because we should increase p when n increases, so p cannot be a fixed constant such that it can be excluded

3. to exclude p should give us the same result of calculate the probabilities of $$2, 2^2, 2^3, ..., 2^n, ...$$ be prime numbers, when only 2 is a prime number ==> both results cannot be the same

 

[CRGreathouse]

3. to exclude p should give us the same result of calculate the probabilities of $$2, 2^2, 2^3, ..., 2^n, ...$$ be prime numbers, when only 2 is a prime number ==> both results cannot be the same

For information on the Cramer model of the primes, see (for example):
http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf

The magnitude of the number is the only thing that matters for the Gauss-Tchebychev expectation 1/log(x). Obviously if you know about the divisibility of the number by small primes that will tell you more -- in fact this can be stated explicitly in what I call the Cramer-Maier model of the primes -- but that's only changing a multiplicative constant; the magnitude remains only the exponential part 2^k.

 

[al-mahed]

I was thinking about this approach (I don't know the difference between odds, chances and probability in english, so I used the word probability) :


The expression Q = $$\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})$$ give us an estimate of the amount of primes between $$2^{n+1} and \ 2^n$$

The formula $$\frac{\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})}{2^{n+1} - 2^n} = \frac{\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})}{2^n*(2 - 1)} = \frac{1}{ln(2)}*(\frac{n-1}{n^2+n})$$ should give us the probability of a particular sum of powers of two (inside the " nth-class $$2^n$$ " whose amount of numbers is obviously = $$2^n$$ ) represent a prime.

The formula $$\frac{1}{2^n}$$ should give us the probability of a particular number be this particular sum of powers of two + some power of two, because every number has a unique sum of powers of two representation.

The probability of both events is = $$\frac{\frac{1}{ln(2)}*(\frac{n-1}{n^2+n})}{2^n}$$

Let this particular sum be = q, so we ask if there are infinite prime numbers p such that $$p = q + 2^n$$.

The questions are:

1) what is the probability of the same prime represent another primes taking increasing exponents, for example: $$p_1 = q + 2^{n_1}, p_2 = q + 2^{n_2}, p_3 = q + 2^{n_3}, ..., p_k = q + 2^{n_k}$$; or

2) what is the probability of "there are infinite classes with at least one prime of the form $$p = q + 2^n$$ inside the class"?$$/$$

The first questions I think may be answered by the product:

$$\prod^{n}_{k=2} \frac{\frac{1}{ln(2)}*(\frac{k-1}{k^2+k})}{2^k}$$ = $$\prod^{n}_{k=2} \frac{\frac{1}{ln(2)}*(\frac{k-1}{k*(k+1)})}{2^k}^{[1]}$$

This product converges to zero because it represents the probability of each of the existing classes as having at least a prime number such like that ($$p_k = q + 2^{n_k}$$ with q fixed), and I think that this is because the fixed "q".

But this is not the "right question to ask" since this result cannot be interpreted as a proof of the "non infinity" (I don't know if exists such word in english...) of the set of $$p_1 = q + 2^{n_1}; p_2 = q + 2^{n_2}; p_3 = q + 2^{n_3}; ...; p_k = q + 2^{n_k}$$, because even if there is not a prime such that $$p_k = q + 2^{n_k}$$ in each of the existing classes we still could have infinite number primes of that form in another classes (like only in odd classes, etc).

Then I think that perhaps could be more prolific to work with the more general question:

" to calculate the probability of an any prime of the nth-class, considering all primes into this class, be combined with an exponent -2^n such that will be equal to a prime of the (n-1)th-class

OR the probability of an any prime of the (n-1)th-class, considering all primes into this class, be combined with an exponent +2^n such that will be equal to a prime of the (n-1)th-class

OR the probability of an any prime of the nth-class, considering all primes into this class, be combined with an exponent -2^m (m<n) such that will be equal to a prime of the same nth-class

OR the probability of an any prime of the nth-class, considering all primes into this class, be combined with an exponent +2^m (m<n) such that will be equal to a prime of the same nth-class"

This should increase our chances, because the probabilities will be added. But supose that we find a result that diverge to infinite, or that is convergent to a value > 1, in this cases how to interpret such results in terms of probabilities?

[1] k=1 doesn't matter because $$2^1$$ is the first class such that among the elements there is a prime (in fact, the only element is a prime)

 

[CRGreathouse]

I was thinking about this approach (I don't know the difference between odds, chances and probability in english, so I used the word probability)

Chance and probability have almost exactly the same meaning in English. I'd shy away from odds because it's sometimes used differently: 2:1 odds against means 1/3 probability, for example.

The expression Q = $$\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})$$ give us an estimate of the amount of primes between $$2^{n+1} and \ 2^n$$

The formula $$\frac{\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})}{2^{n+1} - 2^n} = \frac{\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})}{2^n*(2 - 1)} = \frac{1}{ln(2)}*(\frac{n-1}{n^2+n})$$ should give us the probability of a particular sum of powers of two (inside the " nth-class $$2^n$$ " whose amount of numbers is obviously = $$2^n$$ ) represent a prime.

Good so far. It might be worth simplifying to $1/n\log2$ since if n is large the minor terms have little effect.

The formula $$\frac{1}{2^n}$$ should give us the probability of a particular number be this particular sum of powers of two + some power of two, because every number has a unique sum of powers of two representation.

This is the probability that a number is a given number in the range, say 2^n - 78352785. I'm not sure this is what you want to do.

The probability of both events is = $$\frac{\frac{1}{ln(2)}*(\frac{n-1}{n^2+n})}{2^n}$$

Now you're just being silly. You know there's just one number in the range which is your chosen number, so the probability is 0 for all other numbers in the range and
$$\frac{n-1}{n(n+1)\log2}\approx\frac{1}{n\log2}$$, the probability of being prime, for the chosen number.

Let this particular sum be = q, so we ask if there are infinite prime numbers p such that $$p = q + 2^n$$.

This can't be what you mean. q is strictly between 0 and 1, so there are no prime numbers of this form.

If you mean "p = q + 2^n, where p and q are prime" then we're back to your original question.

This product converges to zero because it represents the probability of each of the existing classes as having at least a prime number such like that ($$p_k = q + 2^{n_k}$$ with q fixed), and I think that this is because the fixed "q".

But this is not the "right question to ask" since this result cannot be interpreted as a proof of the "non infinity" (I don't know if exists such word in english...) of the set of $$p_1 = q + 2^{n_1}; p_2 = q + 2^{n_2}; p_3 = q + 2^{n_3}; ...; p_k = q + 2^{n_k}$$, because even if there is not a prime such that $$p_k = q + 2^{n_k}$$ in each of the existing classes we still could have infinite number primes of that form in another classes (like only in odd classes, etc).

I agree that it's the wrong question. I'm not sure at all about your form, though: the expected number of primes 2^k + q for a fixed odd q is
$$\sum_{k=1}^\infty\frac{1}{(2^k + q)\log(2^k+q)}\approx C+\sum_{k=2}^\infty\frac{1}{k\cdot2^k}$$
for some (small) constant C.

But if you accept that each such class (for given prime q) is finite, then the problem simplifies to "are there infinitely many primes q such that q+2^k is prime for some integer k?".

 

[CRGreathouse]

This should increase our chances, because the probabilities will be added. But supose that we find a result that diverge to infinite, or that is convergent to a value > 1, in this cases how to interpret such results in terms of probabilities?

Even better, since we agree that the expected number in each "class" is finite, consider showing that there is an infinite set of primes q such that q+2^k is prime for some integer k.

http://www.research.att.com/~njas/sequences/A094076 seems to strongly suggest that such an infinite set exists.

 

[al-mahed]

Even better, since we agree that the expected number in each "class" is finite, consider showing that there is an infinite set of primes q such that q+2^k is prime for some integer k.

http://www.research.att.com/~njas/sequences/A094076 seems to strongly suggest that such an infinite set exists.

As a first "look" seems to be an strong suggestion indeed! I'll think about something!

Perhaps the fact $$2^{n+1} - 2^n = 2^n$$ could be usefull to infer adjacent classes relations, or even not adjacent classes relations.

Chance and probability have almost exactly the same meaning in English. I'd shy away from odds because it's sometimes used differently: 2:1 odds against means 1/3 probability, for example.

Got it !

The formula $$\frac{1}{2^n}$$
should give us the probability of a particular number be this particular sum of powers of two + some power of two, because every number has a unique sum of powers of two representation.

This is the probability that a numbe is a given number in the range, say 2^n - 78352785. I'm not sure this is what you want to do.

I was trying to calculate the probability of "a given number be prime" and "be a paticular sum of powers of two plus another power of two". What I meant saying "particular sum of powers of two" is "a fixed sum", for example, $$5 = 2^0 + 2^2$$ is the only sum of powers of two for 5, called "particular sum of powers of two" or "q".

Then in the nth-class what is the probability of $$x = 2^0 + 2^2 + 2^n$$ be a prime number? The probability of x be prime "times" the probability of $$2^0 + 2^2 = 5$$ be combined with an exponent $$2^n$$. But you are right, this last probability is wrong.

Let this particular sum be = q, so we ask if there are infinite prime numbers p such that $$p = q + 2^n$$.

This can't be what you mean. q is strictly between 0 and 1, so there are no prime numbers of this form.

If you mean "p = q + 2^n, where p and q are prime" then we're back to your original question.

This is not what I meant, q is not strictly between 0 and 1 because q = a particular sum of powers of two, I did not make myself clear.

My mistake was the second probability calculation, let me try to make myself clear and correct the mistake:

Lets take a look on:

$$1 = 2^0$$
$$2 = 2^1$$
$$3 = 2^0 + 2^1$$
$$4 = 2^2$$
$$5 = 2^0 + 2^2$$
$$6 = 2^1 + 2^2$$
$$7 = 2^0 + 2^1 + 2^2$$
$$8 = 2^3$$
$$9 = 2^0 + 2^3$$
$$10 = 2^1 + 2^3$$
$$11 = 2^0 + 2^1 + 2^3$$
$$12 = 2^2 + 2^3$$
$$13 = 2^0 + 2^2 + 2^3$$
$$14 = 2^1 + 2^2 + 2^3$$
$$15 = 2^0 + 2^1 + 2^2 + 2^3$$
$$16 = 2^4$$
$$17 = 2^0 + 2^4$$
$$18 = 2^1 + 2^4$$
$$19 = 2^0 + 2^1 + 2^4$$
$$20 = 2^2 + 2^4 etc...$$

This should let us conclude, without any formal proof, that all the elements of a "class" (considering a "class" the set of all elements with the same highest exponent) are a sum of the highest exponent of the class and each of the elements of all the precedents "classes" (but not the first element 2^n itself$$^{[1]}$$). For example, 3th-class (exponent 2^3):

[1] this is because $1+2^1+2^2+...+2^n=2^{n+1}-1$,i.e, the total of the precedent exponents (which I call "classes") is the the total of elements of the following class minus one

$$8 = 2^3$$ the first element is the exception

$$9 = 2^0 + 2^3$$ where $$2^0$$ is an element of the zero-class

$$10 = 2^1 + 2^3$$ where $$2^1$$ is an element of the first class

$$11 = 2^0 + 2^1 + 2^3$$ where $$2^0+2^1$$ is an element of the first class

$$12 = 2^2 + 2^3$$ where $$2^2$$ is an element of the second class

$$13 = 2^0 + 2^2 + 2^3$$ where $$2^0+2^2$$ is an element of the second class

$$14 = 2^1 + 2^2 + 2^3$$ where $$2^2+2^3$$ is an element of the second class

$$15 = 2^0 + 2^1 + 2^2 + 2^3$$ where $$2^1+2^2+2^3$$ is an element of the second class

This lead us to ask for the probability of an arrangement of 2-exponents of a prime in the last class, already taking off the greater 2-exponent, be exacly a prime of one of the precedent classes.

More generally, we could ask for the probability of an arrangement of 2-exponents of a prime in the last class be exacly a prime of one of the precedent classes, tanking off ONE of the any 2-exponents (but not 2^0 obviously). This should consider an arrangement inside the class itself.

And of course we can extend this to the primes of the form p - 2^n.

Hope I make myself clear now, please consider the english barrier.

I agree that it's the wrong question. I'm not sure at all about your form, though: the expected number of primes 2^k + q for a fixed odd q is
$$\sum_{k=1}^\infty\frac{1}{(2^k + q)\log(2^k+q)}\approx C+\sum_{k=2}^\infty\frac{1}{k\cdot2^k}$$
for some (small) constant C.

But if you accept that each such class (for given prime q) is finite, then the problem simplifies to "are there infinitely many primes q such that q+2^k is prime for some integer k?".

Why did you use sum instead product?

 

[al-mahed]

We know that $$\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... \ =1$$, but your sum above seems to converges to 0.16667 or something like that

 

[CRGreathouse]

I was trying to calculate the probability of "a given number be prime" and "be a paticular sum of powers of two plus another power of two". What I meant saying "particular sum of powers of two" is "a fixed sum", for example, $$5 = 2^0 + 2^2$$ is the only sum of powers of two for 5, called "particular sum of powers of two" or "q".

Terminology: I say call 5 = 1 + 4 the unique binary expansion for 5. When you say fixed that makes me wonder what it's fixed in relation to. Are you asking about solutions to n = 1 + 4, where the "5" part above now varies but the "1 + 4" part is fixed? This of course has only one solution, which gives the 1/2^n probability you mentioned -- but what's the point?

Then in the nth-class what is the probability of $$x = 2^0 + 2^2 + 2^n$$ be a prime number? The probability of x be prime "times" the probability of $$2^0 + 2^2 = 5$$ be combined with an exponent $$2^n$$. But you are right, this last probability is wrong.

Actually I also gave the wrong probability, but it's not important. As long as you can show that there are infinitely many prime p with where p + 2^k is prime for some k, you've proved the result, regardless of how many such k there are for a given p.

This should let us conclude, without any formal proof, that all the elements of a "class" (considering a "class" the set of all elements with the same highest exponent) are a sum of the highest exponent of the class and each of the elements of all the precedents "classes" (but not the first element 2^n itself$$^{[1]}$$).

You're saying that the numbers between 2^n and 2^(n+1) are just 2^n plus a number from {0, 1, ..., 2^n}. Sure, that's right... but what of it?

This lead us to ask for the probability of an arrangement of 2-exponents of a prime in the last class, already taking off the greater 2-exponent, be exacly a prime of one of the precedent classes.

I'll admit, I have no idea what you just write here. Let me try to work through it and you can help me, okay?

What you call a k-class I call a (k+1)-bit number. So you're asking for the probability that a (k+1)-bit number, less its most significant bit (2^k), is prime "of one of the precedent classes". The precedent classes would then be those numbers below 2^k. But since the number minus 2^k is always under 2^k, this is just the probability that a (k+1)-bit number, less its most significant bit, is prime.

Alright, I can see how that is relevant. This is the power of two that leaves the smallest remainder when subtracted from the original, making the remaining number most likely to be prime.

More generally, we could ask for the probability of an arrangement of 2-exponents of a prime in the last class be exacly a prime of one of the precedent classes, tanking off ONE of the any 2-exponents (but not 2^0 obviously). This should consider an arrangement inside the class itself.

This is just a restricted version of your original question, not allowing for the possibility of subtracting a power of two not present in the binary expansion of the number.

Why did you use sum instead product?

I was going to ask you why you used the product. The expected number of occurrences of independent events of probability p1, p2, ..., pn is p1 + p2 + ... + pn.

 

[CRGreathouse]

As a first "look" seems to be an strong suggestion indeed! I'll think about something!

Actually you led me to do at least 60 CPU-hours of work on problems related to A094076, so I'm clearly interested. It's a fascinating sequence; its irregularities lead me to wonder about the appropriateness of standard heuristic arguments in this case. But it is surely reasonable to conjecture that there are infinitely many positive members of the sequence, which implies your conjecture.

If I make enough progress on it I'll send Sloane the updates and post them here as well.

 

[al-mahed]

Actually you led me to do at least 60 CPU-hours of work on problems related to A094076, so I'm clearly interested. It's a fascinating sequence; its irregularities lead me to wonder about the appropriateness of standard heuristic arguments in this case. But it is surely reasonable to conjecture that there are infinitely many positive members of the sequence, which implies your conjecture.

If I make enough progress on it I'll send Sloane the updates and post them here as well.

You are trully making efforts to find a solution! I am spending my time to find some kind of proof, or at least to find another implication between the infinity of p +- 2^n set (called S here) and the twin prime conjecture (we know that the twin prime conjecture ==> infinity of S, but what about a necessary condition "<=="; find it and we prove twin prime conj. proving the infinity of S)

I'll make a comment about another observation of mine that involves twin prime conjecture.

In order to find an appropriate heuristic argument could be more prolific if we work in the same particular direction, because there are a lot of possibilities.

 

[al-mahed]

Terminology: I say call 5 = 1 + 4 the unique binary expansion for 5. When you say fixed that makes me wonder what it's fixed in relation to. Are you asking about solutions to n = 1 + 4, where the "5" part above now varies but the "1 + 4" part is fixed? This of course has only one solution, which gives the 1/2^n probability you mentioned -- but what's the point?

No, I am asking about the "1+4" part is fixed and the 2^n part varies.

You're saying that the numbers between 2^n and 2^(n+1) are just 2^n plus a number from {0, 1, ..., 2^n}. Sure, that's right... but what of it?

I am trying to state some things without any doubt, even the obvious one. I think that write all the numbers in the binary form (actually I'm not really using another numerical base) should help to see my arguments more cleary.

I'll admit, I have no idea what you just write here. Let me try to work through it and you can help me, okay??

In fact, I suck in english and also in probabilities (my bigger weakness), as you can see!

What you call a k-class I call a (k+1)-bit number. So you're asking for the probability that a (k+1)-bit number, less its most significant bit (2^k), is prime "of one of the precedent classes". The precedent classes would then be those numbers below 2^k. But since the number minus 2^k is always under 2^k, this is just the probability that a (k+1)-bit number, less its most significant bit, is prime.

Exactly, you stated accurately. And if we consider the number less any bit (2^g, here g < k, or the most significant bit 2^k itself) we are including the k-class, or the (k+1)-bit numbers, in our calculation, i.e., we are seeking for "matches" in the same class.

About your last statement I am not sure (actually I don't know) if the probability of "a (k+1)-bit number, less its most significant bit, is prime" is the same probability of 1/ln[(k)-bit] be prime, but I think this is not relevant here.

Alright, I can see how that is relevant. This is the power of two that leaves the smallest remainder when subtracted from the original, making the remaining number most likely to be prime.

Actually I did not think about this in these terms, I was thinking in terms of increasing the possibilities of find another prime number using the binary expansion of an any prime number.

This is just a restricted version of your original question, not allowing for the possibility of subtracting a power of two not present in the binary expansion of the number.

Lets call p = q +- 2^n, p,q are prime numbers, a "match". I was trying to say that if we consider the k-class itself, not only the precedent classes, this is a little bit more general.

The question remains the same at its most general case: given a prime number p (which has an unique binary expansion, like all the other integer numbers), we ask for the possibilities of find a prime number q "inside" its binary expansion such that p = q +-2^n.

What I am asking you to consider is to look for the probability of making "matches" looking at the binary expansion of the other prime numbers discriminated in classes, i.e, another angle to see these possibilities, because we know that in the last class all the precedent prime numbers binary expansions shows up. I know this is a little obscure to you because of my bad english, it's already difficult to explain in my own language, but I'll try to be more intelligible to you with some examples!

Note that somehow, adding and deducting exponets must cover a portion of the adjacent classes. Let's see 2 classes considering only the odd numbers:

First:

$$5 = 2^0 + 2^2$$
$$7 = 2^0 + 2^1 + 2^2$$


Second:

$$9 = 2^0 + 2^3$$
$$11 = 2^0 + 2^1 + 2^3$$
$$13 = 2^0 + 2^2 + 2^3$$
$$15 = 2^0 + 2^1 + 2^2 + 2^3$$


First of all I would like to comment an obvious relation:

$$2^{n+1} + 2^n = 2^n$$

How many odd numbers could be represented by, for example, $$5 + 2^n$$ in the following class?

The prime number 5 has 1 significant (excluding $$2^0$$, because if we add or deduct $$2^0=1$$ of an odd number we must find an even number, and this is not important for what we want) binary part (or 2-exponent) $$2^2$$, so we should ask for the probability of $$2^0+2^2+2^3-2^3$$ or $$2^0+2^2+2^2-2^2\ = 2^0+2^3-2^2$$, whose "binary elements" that represents an odd number in the folloing class are $$2^0+2^2+2^3$$ and $$2^0 + 2^3$$ respectively, are = $$p - 2^x$$, where p is prime.

Prime number that has only one significant bit should make a "match" with no more than 2 odd numbers in the following class.

Prime numbers that has 2 significant bits are in one of these cases:

Let $$p = 2^0+2^a+2^b$$ be this prime ==> $$p = 2^0+2^a+2^b+2^c-2^c$$, and x = b+1 exponent of the following class, then:

1)c=x>b ==> $$p = 2^0+2^a+2^b+2^x-2^x$$,

2)c=b ==> $$p = 2^0+2^a+2^{b+1}-2^b$$ = $$p = 2^0+2^a+2^x-2^b$$

3) c=a<b, and b+1=a ==> $$p = 2^0+2^{a+1}+2^b-2^a$$ = $$p = 2^0+2^b+2^b-2^a$$ = $$p = 2^0+2^x-2^a$$

if c=a<b, but b+1>a, then the third case is not possible.

Prime numbers with 1 significant bit could find 2 odd numbers as a "match" in the following class.

Prime numbers with 2 significant bits could find 2 odd numbers as a "match" in the following class, and 3 if and only if the difference of the exponents of the 2 significant bits = 1.

Prime numbers with 3 significant bits could find 2 odd numbers as a "match" in the following class, 3 if and only if the difference of the exponents of the last 2 significant bits = 1, and 4 if and only if the difference of a bit and the following bit = 1 for all.

The maximum number of "matches" for a prime number in the following class = number of bits of the prime + 1.

Which is the relevance of this? I was thinking on estimate the probability of the amount of primes in the precedent class cover any prime of the following class, obviously considering the amount of primes of the following class. But the difficulty here is that 2 or more primes in the precedent class could be exactly the same prime in the following class, reducing the possibilities in the following class (in fact we can see this happening when we evidence that a given prime has more that one way to be written as a sum of a prime and a power of two).

Restrict this "method" only to adjacent "classes" is obviously the worst case possible, because we cannot work with "matches" in the same "class" and from non-adjacent "classes" neither.

I was going to ask you why you used the product. The expected number of occurrences of independent events of probability p1, p2, ..., pn is p1 + p2 + ... + pn.

Because I think they are not independent, p is only a prime number if p - 2^n, for an any n, is a prime number to, according to our definition. But you must be aware that I really never dedicated myself to study probabilities. I'll improve myself on this topic.

 

[al-mahed]

I noticed that the amount of numbers with k-terms in a "class" is given by the coefficients of the paschal triangle (or Newton's binomial) as shown below:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

Where:
the first line is the class $$2^0$$ with $$2^0 = 1$$ element
the second line is the class $$2^1$$ with $$2^1 = 1 + 1 =2$$ elements
the third line is the class $$2^2$$ with $$2^2 = 1 + 2 + 1 = 4$$ elements
the fourth line is the class $$2^3$$ with $$2^3 = 1 + 3 + 3 + 1 =8$$ elements
and so on...

The subgroups inside the class, whose amount of elements are the coefficients of the binomial expansion, contains only numbers with the same total of terms (or what you call bits; for instance, 2^0 + 2^3 + 2^8 = 3-terms number). Let us call "x-number" the number which represents the coefficient in the paschal triangle. So, the first column of a line is a subgroup with x-numbers having one term (in fact, every first column subgroup is always an 1-term number and x = 1), the second column of a line is a subgroup with x-numbers having 2 terms, the third column of a line is a subgroup with x-numbers having 3 terms, and so on...

For instance, the fourth line "1 4 6 4 1", representing the $$2^3$$= 3th-class, must be read in this fashion: one number having one term, four numbers having two terms, six numbers having three terms, four numbers having four terms, and one number having five terms.

Now, we want to calculate the probability of an any prime number, like 5, beeing "inside" the binary expansion of another prime number such that p = 5 + 2^n for any n. As 5 has 2 terms (2^0 and 2^2), obviously we are interested in the subgroups of the following classes whose numbers has exactly 3 terms.

Looking at the triangle again, the subgroup of 5 is in red, so we are interested in the subgroups in blue:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

Now we can ask for the probabilities in these terms: what is the probability of a prime number "q" in the precedent class be another prime number "p" in the following class such that the first prime number is "inside" the binary expansion of the other prime number such that p = q + 2^n such that n is the most significant bit of the following class?

If q = 5, the probability $$(P_1)$$ of a number be inside the subgroup with 3 numbers in the 3th-class is = $$\frac{3}{2^3}$$, the probability $$(P_2)$$ of one of the three numbers in this subgroup has 5 as a number "inside" its binary expansion is = $$\frac{1}{3}$$, and the probability $$(P_3)$$ of this number in this subgroup be a prime number is = $$\frac{1}{ln(2)}*(\frac{n-1}{n^2+n})$$ = $$\frac{1}{ln(2)}*(\frac{1}{6})$$ in this case.

This lead us to conclude that the probability of a prime number with k-terms in the nth-class be equal to a prime number with (k-1)-terms of the precedent class plus a power of two is = $$(P_1)*(P_2)*(P_3)$$ = $$\frac{\frac{1}{ln(2)}*(\frac{n-1}{n^2+n})}{2^n}$$ as I said before.

But now I see, as you said, that the probability of a prime number "q" in the precedent class be another prime number "p" in the following class such that the first prime number is "inside" the binary expansion of another prime number such that p = q + 2^n for an any n (n beeing the most significant bit of an any class) is the addition of the probabilities in each increasing class. Call P this probability, then:

$$P = \frac{1}{ln(2)}*\left\{\frac{n_1-1}{(n_1^2+n_1)*2^{n_1}} + \frac{n_2-1}{(n_2^2+n_2)*2^{n_2}} + \frac{n_3-1}{(n_3^2+n_3)*2^{n_3}} + \cdots \right\}$$ which I think clearly converges to a small real number

This is the worse case, because we are working with primes of the form p + 2^n when p - 2^n seems to be more abundant. We are considering only relations between adjacent classes, when there are "matches" in the same class (i.e. p and q are in the same class and the relation p = q +-2^n holds).

I need to generalize these heuristics for all cases, and I'm sure that the result will be interesting.

 

[al-mahed]

I committed an error of typewriting on post #55.

Where are written the follow:

"First of all I would like to comment an obvious relation:

$$2^{n+1} + 2^n = 2^n$$"

please read the follow:

"First of all I would like to comment an obvious relation:

$$2^{n+1} - 2^n = 2^n$$"

 

[al-mahed]

A remarkable heuristics from the particular case of 5 given above is:

given the paschal triangle

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

such that the diagonal line in blue represents the waited sub-groups of the "classes" where the prime numbers of the form 5 + 2^n will be found

lets think about the following argument: if all primes of a certain "class" always will be in the sub-group represented for this line in blue this certainly strengthen the hypothesis of that there are infinitely many prime numbers of the form 5 + 2^n

this hypothesis is strongly unlikely since the probability of "m" prime numbers beeing all inside the same subgroup with $$\left(^{n}_{k}\righ)$$ elements is $$\prod^{\infty}_{n=2}$$$$\frac{\left(^{n}_{k}\righ)}{2^{n+m}}$$ where $$m = \frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})$$ and k is the column of the "class", which diverges to zero when n becomes bigger.

this let us to conclude that it is extremely probable that there is a prime number out of these sub-groups for at least one of the "classes" represented by the diagonal line in blue.

lets point its sub-group in green

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

now I can give the same argument for this new prime number such which I gave for number 5, that is, I want to calculate the probability of the subgroups represented below in orange having inside a prime number such that the prime number in the green subgroup plus an any power of two 2^n represents another prime number in an any nth-class.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

And I can extend the same argument to this orange line as I did to the blue line (that is pretty much unlikely that all primes shall be inside the subgroups of one of these two diagonals lines, blue and orange), and so on$$^{[1]}$$... If I consider that an any prime number could "appear" in an any "class" such that its subgroup is a subgroup on the left of a "line of probability" (a diagonal line of another prime number), this possibility should strengthen the conjecture "there are infinitely many primes of the form p+2^n". This is shown in pink as follows:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...​

[1]someone could affirm: you are considering that there is to few diagonal lines in order that the probability of the event "all the existing prime numbers shall be lying into one of these sub-groups, of these diagonal lines" will be very small; and the answer is: if I decrease the probability of there is a prime number out of these sub-groups for at least one of the 'classes' represented by the diagonal line of an any number the number of another diagonal lines will be increased in such hypothesis, so the result will be the same in both directions.

Then I think that statistically speaking the conjecture is proved by these arguments, or other similar arguments!

 

[al-mahed]

the probability of "m" prime numbers beeing all inside the same subgroup with $$\left(^{n}_{k}\righ)$$ elements is $$\prod^{\infty}_{n=2}$$$$\frac{\left(^{n}_{k}\righ)}{2^{n+m}}$$ where $$m = \frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})$$ and k is the column of the "class", which diverges to zero when n becomes bigger.

This is wrong, I made a mistake in the calculation, in fact the probability is


$$\prod^{\infty}_{n=2}$$$$\frac{\left(^{n}_{k}\righ)}{2^n}*\frac{1}{ln(2)}*(\frac{n-1}{n^2+n}) \approx \prod^{\infty}_{n=2}$$$$\frac{\left(^{n}_{k}\righ)}{n*2^n*ln(2)}$$ which diverges to zero when n becomes bigger also

 

[husseinshimal]

wrong example

dear sir,in your post you gave awrong example,namely87.it is no prime number.i would like to refere that some times it worthless to search about how to express prime numbers?

 

[al-mahed]

dear sir,in your post you gave awrong example,namely87.it is no prime number.i would like to refere that some times it worthless to search about how to express prime numbers?

You're right, 87 = 3*29, but in fact this simple wrong example doesn't change anything about the further discussion

 

[al-mahed]

is there any news about it?

 

[CRGreathouse]

is there any news about it?

I can't remember where we were. Do you mean your original conjecture?

Every prime number > 3 could be written as a sum of a prime number and a power of two.

As I commented on http://www.research.att.com/~njas/sequences/A094076 (see my PDF there), 2^k + 3367034409844073483 is composite for all natural numbers k, even though 3367034409844073483 is prime. So the conjecture fails.

 

[al-mahed]

I can't remember where we were. Do you mean your original conjecture?



As I commented on http://www.research.att.com/~njas/sequences/A094076 (see my PDF there), 2^k + 3367034409844073483 is composite for all natural numbers k, even though 3367034409844073483 is prime. So the conjecture fails.

but p = 3367034409844073483 - 2^60 (=1152921504606850000) is a prime number

 

[al-mahed]

the original conjecture is: all prime numbers can be expressed as q + 2^k, q is prime

but there are some gaps, like 997 and 6659 (997 and 6659 must be expressed as q - 2^k)

so the second form of conjecture is: all prime numbers can be expressed as q - 2^k, q is prime

what you found? you found that for a particular prime there are no prime numbers such that p = 2^k + 3367034409844073483 is prime, for all natural k

wich means 3367034409844073483 cannot be expressed as q - 2^k

but as 3367034409844073483 can be expressed as q + 2^60 this is not a counter example of both conjecture forms

I used excel and the program primo 3.0.6, I don't know if excel did a mistake in calculating the corret value for 2^60 = 1152921504606850000

3367034409844073483 is a gap of the second conjecture form

 

[CompuChip]

I used excel and the program primo 3.0.6, I don't know if excel did a mistake in calculating the corret value for 2^60 = 1152921504606850000

3367034409844073483 is a gap of the second conjecture form

2^60 = 1152921504606846976
Don't trust programs like Excel for doing math

3367034409844073483 can be written in the form prime + 2^n in two ways: 2^10 + 3367034409844072459 or 2^30 + 3367034408770331659
However, 3367034409844073483 - 2^60 is not prime, it is 137 x 16161408067425011.

 

[CRGreathouse]

the original conjecture is: all prime numbers can be expressed as q + 2^k, q is prime

but there are some gaps, like 997 and 6659 (997 and 6659 must be expressed as q - 2^k)

so the second form of conjecture is: all prime numbers can be expressed as q - 2^k, q is prime

So your actual conjecture is that for all primes p, there is some positive integer k with either p - 2^k or p + 2^k prime. Is that right?

In that case it suffices to show that all members of http://www.research.att.com/~njas/sequences/A065381 (alas, not currently accessible; let me look it up tomorrow) which I can use to find the first small example not known to work.

 

[al-mahed]

CompuCHIP:

:) all right, I don't have the best programs as you and Charles, so I must trust in excel and other bullCH... sorry for my 5rd world resources

CGR:

Nice to talk with you again! it is nice to see that I am still the most iluded amatheur EVER :)... in fact I am back to "paper" since my last post here, I have a complicated life... one year and 30 years old, now we have almost the same cardinality kkkkkk

well, let's see... seems that U show with some "formal" math in your sloane pdf some stuff we discuss here before, like that "classes" chat... in fact you did pretty much more if you are right in your counter example... I really cannot follow you at the moment, I mean, analyse your arguments (need to study again the elementary number theory)...

but I noticed that compuchip did show that your pdf is wrong because 3367034409844072459 is prime number

 

[CRGreathouse]

:) all right, I don't have the best programs as you and Charles, so I must trust in excel and other bullCH... sorry for my 5rd world resources

Might I recommend Pari/GP? You can download it from here:
http://pari.math.u-bordeaux.fr/download.html

but I noticed that compuchip did show that your pdf is wrong because 3367034409844072459 is prime number

No. My PDF showed that 3367034409844073483 + 2^k is never prime, and it isn't. My paper didn't show anything about 3367034409844073483 - 2^k.

And I repeat my question to you. Is your full, final conjecture "for all primes p, there is some positive integer k with either p - 2^k or p + 2^k prime"?

 

[al-mahed]

And I repeat my question to you. Is your full, final conjecture "for all primes p, there is some positive integer k with either p - 2^k or p + 2^k prime"?

yes.

do know a counter example in both ways? p - 2^k and p + 2^k never prime number?