I made the following conjecture

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*

Quote by 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.

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

Code:

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

Code:

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

Code:

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:

Code:

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

Quote by 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.

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

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 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

Quote by 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?

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

Quote by al-mahed

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

Quote by al-mahed

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.

Quote by al-mahed

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.

Quote by al-mahed

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.

Similar Threads for: I made the following conjecture
Thread	Forum	Replies
Cells are made of molecules,molecules are made of atoms,atoms are made of energy.so..	Biology	9
BKL Conjecture	Special & General Relativity	0
Name that conjecture	General Math	4
Proof of Golbach's conjecture and the twin prime conjecture	Linear & Abstract Algebra	9
My Conjecture	General Discussion	0

CompuChip Blog Entries: 5 Recognitions: Homework Help Science Advisor	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.

CompuChip Blog Entries: 5 Recognitions: Homework Help Science Advisor	I made the following conjecture 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.

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 Recognitions: Homework Help Science Advisor	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 A078687, the number of ways to represent each prime as p + 2^k.

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?