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

[al-mahed]

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

p,q are primes, n is positive whole number ==> p = q + 2^n

5 = 3 + 2^1
7 = 5 + 2^1 = 3 + 2^2
11 = 7 + 2^2
13 = 5 + 2^3
17 = 13 + 2^2
19 = 3 + 2^4
23 = 7 + 2^4
29 = 13 + 2^4
31 = 23 + 2^3
37 = 29 + 2^3

87 = 23 + 2^6
101 = 37 + 2^6

1213 = 701 + 2^9
1217 = 1153 + 2^6
1223 = 967 + 2^8

seems that this is really truth, but fails for some primes (997, 6659 are some primes that this is not true)

I wonder if there is some property which could be used to discriminate such primes

 

[CompuChip]

You can, however, write
997 = (-1051) + 2^(11)
and
6659 = (-16 770 557) + 2^24
where both 1,051 and 16,770,557 are prime.

 

[ice109]

You can, however, write
997 = (-1051) + 2^(11)
and
6659 = (-16 770 557) + 2^24
where both 1,051 and 16,770,557 are prime.

how did you figure that out?

 

[CompuChip]

Had a hunch that n might be s.t. 2^n > p.
Then it took just a little trial and error and a Mathematica system.
Probably not too hard to write a program that does it automatically.

 

[CompuChip]

Actually, here is an ugly (but effective) one

CheckConjecture[n_] := Module[{},
  If[!PrimeQ[n], Print[n, " is not prime"]; Return[]];
  For[i = 0, i <= Sqrt[n], i++, 
   If[n - 2^i // PrimeQ, 
    Print[StringForm["`` = `` + 2^``", n, n - 2^i, i]]; Break[], 
    0
   ]
  ];
 ]

It finds the one for 6659 in less than 0.01 second
(note, upper boundary is selected somewhat arbitrarily. I think it would be very odd if you happened to plug in a prime for which it even needs to get close).

Here is the result for the first 100 prime numbers

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

and for some arbitrary large ones

9544791479 = 9544791463 + 2^4
22129347137 = 22129347133 + 2^2
4648194659 = 4648194643 + 2^4
11534533159 = 11400315431 + 2^27
20435808557 = 20435808493 + 2^6
11932479739 = 11932446971 + 2^15
14934903251 = 14934641107 + 2^18
21592521889 = 21592519841 + 2^11
20643758743 = 20643758741 + 2^1
17469583409 = 17468534833 + 2^20
3084406151 = 3017297287 + 2^26
7767771523 = 7767771521 + 2^1

Note how the powers of two hardly increase.
In fact, if you have access to Mathematica yourself, you might find it interesting to plot the powers of two separately:

PowerOfTwo[n_] := 
 Module[{}, If[! PrimeQ[n], Print[n, " is not prime"]; Return[-1]];
  For[i = 0, i <= Sqrt[n], i++, 
   If[n - 2^i // PrimeQ, Return[i], -1]]]
{Range[1, 5000], Composition[PowerOfTwo, Prime] /@ Range[1, 5000]} // Transpose // ListPlot
(Composition[PowerOfTwo, Prime] /@ Range[1, 10000]) // Tally // ListPlot

 

[al-mahed]

You can, however, write
997 = (-1051) + 2^(11)
and
6659 = (-16 770 557) + 2^24
where both 1,051 and 16,770,557 are prime.

I was thinking on positive whole numbers

 

[al-mahed]

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

in another words: given the prime 31

we have:

7 = 5 + 2^1 = 3 + 2^2

23 = 7 + 2^4

31 = 23 + 2^3 ==>

==> 31 = 3 + 2^2 + 2^3 + 2^4

my idea was: if a I prove that every single prime could be written as a sum of a prime and a power of 2 (and extract the exacly reason why some of then couldn't), maybe I could derive some properties of the distribution of primes in terms of the power of 2 series

If you generate such list that I am asking for (a prime as the minor prime possible plus some powers of 2), perhaps some interesting pattern in the powers will shows up

 

[dodo]

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.

 

[CRGreathouse]

http://www.research.att.com/~njas/sequences/A065381 are those primes that cannot be represented in this way. A list of the first 1000 such primes is here:
http://www.research.att.com/~njas/sequences/b065381.txt

See also http://www.research.att.com/~njas/sequences/A078687 , the number of ways to represent each prime as p + 2^k.

 

[CRGreathouse]

Up to 10 million there are 664,579 primes, of which 102,613 cannot be represented in this way. Up to 50 million there are 4,77,446 primes, of which 477,446 cannot be represented in this way.

 

[al-mahed]

CRg. do you know who was the first to have the same insight?

I was speculating about goldbach's conjeture just for curiosity and this insight came to me, was very nice to see a possible pattern coming out!

Will it be that anybody knows a proof for that?

 

[al-mahed]

Seems that the number of primes that cannot be represented in such way decrease comparatively with the total of primes

 

[CRGreathouse]

CRg. do you know who was the first to have the same insight?

I was speculating about goldbach's conjeture just for curiosity and this insight came to me, was very nice to see a possible pattern coming out!

Will it be that anybody knows a proof for that?

What insight? What do you want a proof of? I just gave some totals, which are proved by direct computation.

Seems that the number of primes that cannot be represented in such way decrease comparatively with the total of primes

I expect that the number will fluctuate depending on how far the primes are from a power of 2, but the prime number theorem combined with the divergence of the harmonic series suggests that 'most' primes should be represented that way, and that for N(n) = the number of primes < n not representable in the form p + 2^k,
lim N(n)/pi(n) = 0.

What does everyone think? I'm curious about the cardinality of A065381: is it finite?

 

[al-mahed]

I think that you did not see that I had open the thread, I'm saying that I have this insight of represent primes as a prime plus 2^n once when I was studying goldbach's conjeture. Could be not a big deal, but I had this "insight" and now I see that someone had the same insight, I just asked you about more information of that.

Nothing is proved by direct computation, as you know, in terms of infinity, or do you think that a massive data could prove that there are infinite primes in p + 2^n form?

regards

 

[CRGreathouse]

nothing is proved by direct computation in terms of infinity, or do you think that a massive data could prove that there are infinite primes in p + 2^n form?

So what insight were you referring to that I had when you said "CRg. do you know who was the first to have the same insight?"?

 

[al-mahed]

I edited, read above, I mean that I have the insight... sorry, my english is not so good...

 

[CRGreathouse]

Call S the set of primes that can be represented in the form p + 2^k.

I'm saying that I have this insight of represent primes as a prime plus 2^n once when I was studying goldbach's conjeture.

It's been studied -- there are half a dozen or so sequences in the OEIS -- but I haven't found any sources beyond those listed in the sequences above.

The twin prime conjecture (more generally, de Polignac's conjecture or the first Hardy-Littlewood conjecture) implies that S is infinite.

Nothing is proved by direct computation, as you know, in terms of infinity, or do you think that a massive data could prove that there are infinite primes in p + 2^n form?

I do think it might be possible to prove results about the cardinality or cocardinality of the set by direct computation, yes. I don't have a method at the moment, though.

 

[al-mahed]

Ok, cardinality is another thing as you know...

I was just thinking on how to prove that S is infinite... I have a clue... but, infortunally twin primes conjecture ==> S is infinite, not <==, i.e., a proof of the infinity of S do not implies that the twin prime conjecture is true.

 

[CRGreathouse]

I was just thinking on how to prove that S is infinite... I have a clue... but, infortunally twin primes conjecture ==> S is infinite, not <==, i.e., a proof of the infinity of S do not implies that the twin prime conjecture is true.

Of course if your conjecture implied the twin prime conjecture (which it does not, as you pointed out) one might take that as evidence that your conjecture was 'hard', probably too hard to solve. Still, it won't be easy -- a proof of the conjecture that S is infinite might be the biggest step toward a proof of the twin prime conjecture since Chen's theorem 35 years ago.

 

[al-mahed]

You are right, we can see that somehow the two problems are connected !

We may be able to make some progress if we write the primes a little bit different ... can you see how?

 

[al-mahed]

in fact, w don't need to prove that S is infinite, by Dirichlet:

if n, a and b are positive whole numbers, b > 0, gcd(a,b)=1

the arithmetical progression (a + bn) shows infinite primes

so we should write a = p (prime), b = 2 and n = 2^x, and we will know that S is infinite

 

[CRGreathouse]

OK, here's a heuristic. Take Cramer's model where each number n has a 1/log(n) chance of being prime. Then the expected chance that p-2 is prime is 1/log(p-2), the chance that p-4 is prime is 1/log(p-4), and so on. Estimate each of these probabilities but the last by 1/log(p) because log(p-2^k) is about log(p) when 2^k is small compared to p, and estimate it by 3/log(p) for the last (since you expect that losing the first bit will make a number smaller by a factor of 2 or 4 with roughly equal chance). Estimate the total probability by adding these directly*, which gives (lg (p) + 2) / log(p), which limits toward a constant as p -> infty. Since this constant is large we expect S to be infinite.

* Instead of taking the product of 1 - pr_k for each, hoping that the overlap will be small. It's not, unfortunately, but this still makes the case that S should be large.

 

[CRGreathouse]

That's not what the theorem says. You can choose a and b, but n just ranges over the integers. You could set a = p, b = 2^k for some k, but that will just show that there are infinitely many primes of the form
p + n * 2^k
which isn't what you want.

 

[CRGreathouse]

A better heuristic, though one that still needs some work, suggests that in the limit 23.7% of primes cannot be represented in this form and the remainder can be. This uses a slowly-growing function that converges to a power of the limit form of e.

 

[al-mahed]

That's not what the theorem says. You can choose a and b, but n just ranges over the integers. You could set a = p, b = 2^k for some k, but that will just show that there are infinitely many primes of the form
p + n * 2^k
which isn't what you want.

you right, find a condition to n be 2^x is probably the same problem that I was working on

the problem with probabilities is that we only have evidences in these cases, not a prove, but I will read your message more carefuly at night!

regards

 

[CRGreathouse]

the problem with probabilities is that we only have evidences in these cases, not a prove, but I will read your message more carefuly at night!

More than just evidence, less than a proof: it's a heuristic based on the known distribution of the primes. The Cramer probability that p - 2^k is prime is roughly (slightly more than) 1 - 1/log(p), so the chance that an number has no such form is (1 - 1/log(p))^(lg p) where lg is the binary logarithm.

Actually the Cramer-Maier model would be more appropriate, since we know that the numbers are odd. That would suggest probability (1 - 2/log(p))^(lg p) which limits toward 5.6%.

 

[al-mahed]

consider the set S = (p_1, p_2, p_3,...p_r | p_i = p_j + 2^{n_k} \forall i,j,k =1,2,3 ...) is finite

write N such that N = p_1*p_2*p_3*...*p_r + 2^x ==&gt; gcd(N,p_i) = 1 \forall i = 1,2,3,...,k ==>

==> N = q_1*q_2*q_3*...*q_s


if consider that none of the primes q have the form p + 2^n => contradiction, S is not finite ==> S is infinite

the difficult is that there are primes we cannot write in this form

 

[al-mahed]

a direct proof must show that there are allways at least one q of the form p + 2^n, pretty much more hard to do

 

[al-mahed]

it is very clever in fact, but an absolute proof is our "everest"

More than just evidence, less than a proof: it's a heuristic based on the known distribution of the primes. The Cramer probability that p - 2^k is prime is roughly (slightly more than) 1 - 1/log(p), so the chance that an number has no such form is (1 - 1/log(p))^(lg p) where lg is the binary logarithm.

Actually the Cramer-Maier model would be more appropriate, since we know that the numbers are odd. That would suggest probability (1 - 2/log(p))^(lg p) which limits toward 5.6%.

 

[CRGreathouse]

Here's another angle. The infinitude of http://www.research.att.com/~njas/sequences/A057732 ), would easily prove it.

 

[al-mahed]

Here's another angle. The infinitude of http://www.research.att.com/~njas/sequences/A057732 ), would easily prove it.

the same cardinality?

 

[CRGreathouse]

I expect that both A057732 and your S are countably infinite, giving them the same cardinality \aleph_0.

 

[al-mahed]

I notice another thing:

let S be the set of primes of the form p+2^n

if there are infinite primes of the form p - 2^n must be at least one prime of the form p + 2^n

let p = q - 2^n ==> p +2^n = q - 2^n + 2^n ==> q = p + 2^n ==>

==> for every prime of the form p - 2^n there is a prime of the form p + 2^n

of course this is not a prove that S is infinite, but we have another angle to attack:

if a prime that is not of the form p + 2^n is of the form p - 2^n (we must prove this statement), both sets are infinite because they have the same cardinality

 

[CRGreathouse]

Call S the set of primes of the form p + 2^k and S' the set of primes of the form p - 2^k.

If S' is infinite and S is finite, then there is some s in S which is of the form p + 2^k for an infinite number of integers k. Since this is impossible (primes are finite, and we're not considering negative numbers prime), if S' is infinite only if S is infinite.

 

[al-mahed]

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

 

[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&#039;, 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
<br /> 2 = 2^1
<br /> 3 = 2^0 + 2^1
<br /> 4 = 2^2
<br /> 5 = 2^0 + 2^2
<br /> 6 = 2^1 + 2^2
<br /> 7 = 2^0 + 2^1 + 2^2
<br /> 8 = 2^3
<br /> 9 = 2^0 + 2^3
<br /> 10 = 2^1 + 2^3
<br /> 11 = 2^0 + 2^1 + 2^3
<br /> 12 = 2^2 + 2^3
<br /> 13 = 2^0 + 2^2 + 2^3
<br /> 14 = 2^1 + 2^2 + 2^3
<br /> 15 = 2^0 + 2^1 + 2^2 + 2^3
<br /> 16 = 2^4
<br /> 17 = 2^0 + 2^4
<br /> 18 = 2^1 + 2^4
<br /> 19 = 2^0 + 2^1 + 2^4
<br /> 20 = 2^2 + 2^4 <br /> <br /> 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 &gt; 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
<br /> 2 = 2^1
<br /> 3 = 2^0 + 2^1
<br /> 4 = 2^2
<br /> 5 = 2^0 + 2^2
<br /> 6 = 2^1 + 2^2
<br /> 7 = 2^0 + 2^1 + 2^2
<br /> 8 = 2^3
<br /> 9 = 2^0 + 2^3
<br /> 10 = 2^1 + 2^3
<br /> 11 = 2^0 + 2^1 + 2^3
<br /> 12 = 2^2 + 2^3
<br /> 13 = 2^0 + 2^2 + 2^3
<br /> 14 = 2^1 + 2^2 + 2^3
<br /> 15 = 2^0 + 2^1 + 2^2 + 2^3
<br /> 16 = 2^4
<br /> 17 = 2^0 + 2^4
<br /> 18 = 2^1 + 2^4
<br /> 19 = 2^0 + 2^1 + 2^4
<br /> 20 = 2^2 + 2^4 <br /> <br /> 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?