I made the following conjecture


by al-mahed
Tags: conjecture
al-mahed
al-mahed is offline
#37
Dec24-07, 10:27 PM
P: 258
Quote Quote by CRGreathouse View Post
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
dodo is offline
#38
Dec25-07, 06:28 AM
P: 688
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
al-mahed is offline
#39
Dec25-07, 10:45 AM
P: 258
Quote Quote by Dodo View Post
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 [tex]S \subset\ S'[/tex], 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
al-mahed is offline
#40
Dec26-07, 06:04 PM
P: 258
Let all positive whole number be written as a sum of power of two:

[tex]1 = 2^0[/tex]
[tex]
2 = 2^1[/tex]
[tex]
3 = 2^0 + 2^1[/tex]
[tex]
4 = 2^2[/tex]
[tex]
5 = 2^0 + 2^2[/tex]
[tex]
6 = 2^1 + 2^2 [/tex]
[tex]
7 = 2^0 + 2^1 + 2^2[/tex]
[tex]
8 = 2^3 [/tex]
[tex]
9 = 2^0 + 2^3[/tex]
[tex]
10 = 2^1 + 2^3[/tex]
[tex]
11 = 2^0 + 2^1 + 2^3[/tex]
[tex]
12 = 2^2 + 2^3[/tex]
[tex]
13 = 2^0 + 2^2 + 2^3[/tex]
[tex]
14 = 2^1 + 2^2 + 2^3[/tex]
[tex]
15 = 2^0 + 2^1 + 2^2 + 2^3[/tex]
[tex]
16 = 2^4 [/tex]
[tex]
17 = 2^0 + 2^4[/tex]
[tex]
18 = 2^1 + 2^4[/tex]
[tex]
19 = 2^0 + 2^1 + 2^4[/tex]
[tex]
20 = 2^2 + 2^4

etc...[/tex]

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 =[tex]\frac{x}{ln(x)}[/tex]

The number of primes between [tex] 2^n[/tex] and [tex] 2^{n+1}[/tex] is approximately =

[tex]\frac{2^{n+1}}{ln(2^{n+1})} - \frac{2^n}{ln(2^n)}[/tex] = [tex]\frac{2^n}{ln(2)}*(\frac{2}{n+1} - \frac{1}{n})[/tex] = [tex]\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})[/tex]

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

for n increasing the Tchebychef's theorem underestimates the amount of primes
CRGreathouse
CRGreathouse is offline
#41
Dec27-07, 08:32 AM
Sci Advisor
HW Helper
P: 3,680
I'm not sure why you're measuring the primes between [itex]2^n[/itex] and [itex]2^{n+1}[/itex]. The relevant probabilities are

[tex]1/\ln(p+2)[/tex]
[tex]1/\ln(p+4)[/tex]
[tex]1/\ln(p+8)[/tex]
. . .

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

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

[tex]\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[/tex]

so the product is 0 and so we do expect that all odds are of the form [itex]p-2^n[/itex] for prime p and some positive n.
al-mahed
al-mahed is offline
#42
Dec27-07, 12:45 PM
P: 258
This is the point: seems to me that you already are considering that there are such primes of the form [tex]p + 2^n[/tex], and we don't know yet. Or did I not understand some particular point?

My idea on measuring the primes between [itex]2^n[/itex] and [itex]2^{n+1}[/itex]:

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

My idea: [tex]\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})[/tex] 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.

Quote Quote by CRGreathouse View Post
I'm not sure why you're measuring the primes between [itex]2^n[/itex] and [itex]2^{n+1}[/itex]. The relevant probabilities are

[tex]1/\ln(p+2)[/tex]
[tex]1/\ln(p+4)[/tex]
[tex]1/\ln(p+8)[/tex]
. . .
al-mahed
al-mahed is offline
#43
Dec27-07, 12:58 PM
P: 258
* because obviously [tex]2^0 + 2^a + 2^b + 2^n + 2^k - 2^k[/tex] is the same prime, so we can keep adding exponents until find some k such that [tex]2^0 + 2^a + 2^b + 2^n + 2^k[/tex] represents a prime; and as we know that for every prime of the form [tex]p - 2^n[/tex] there is a prime of the form [tex]p + 2^n[/tex], this should give us our proof.

ps: I had to write this sentence here because TEX become crazy and change the expressions
CompuChip
CompuChip is offline
#44
Dec29-07, 06:04 AM
Sci Advisor
HW Helper
P: 4,301
Quote Quote by al-mahed View Post
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

Quote Quote by Dodo View Post
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
[tex]491 - 3 = 2^8 + 2^7 + 2^6 + 2^5 + 2^3[/tex].

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]}
]
Attached Thumbnails
primes.jpg  
al-mahed
al-mahed is offline
#45
Dec29-07, 10:51 AM
P: 258
Quote Quote by CompuChip View Post
Sure I will do that, if it makes you happy
Thank you CompuChip!!! You did a very good job !!

Quote Quote by al-mahed View Post
This is the point: seems to me that you already are considering that there are such primes of the form [tex]p + 2^n[/tex], 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 [tex]p+3, p+5, p+9, p+17,..., p+2^n+1[/tex], or [tex]p+1, p+3, p+7, p+15,..., p+2^n-1[/tex] 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 [tex]p - 2^n[/tex] 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 [tex] 2, 2^2, 2^3, ..., 2^n, ... [/tex] be prime numbers, when only 2 is a prime number ==> both results cannot be the same
CRGreathouse
CRGreathouse is offline
#46
Dec29-07, 11:13 AM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by al-mahed View Post
3. to exclude p should give us the same result of calculate the probabilities of [tex] 2, 2^2, 2^3, ..., 2^n, ... [/tex] 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/cha...ann/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
al-mahed is offline
#47
Jan2-08, 10:18 PM
P: 258
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 = [tex]\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})[/tex] give us an estimate of the amount of primes between [tex]2^{n+1} and \ 2^n[/tex]

The formula [tex]\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})[/tex] should give us the probability of a particular sum of powers of two (inside the " nth-class [tex]2^n[/tex] " whose amount of numbers is obviously = [tex]2^n[/tex] ) represent a prime.

The formula [tex]\frac{1}{2^n}[/tex] 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 = [tex]\frac{\frac{1}{ln(2)}*(\frac{n-1}{n^2+n})}{2^n}[/tex]

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

The questions are:

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

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

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

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

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 ([tex]p_k = q + 2^{n_k}[/tex] 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 [tex]p_1 = q + 2^{n_1}; p_2 = q + 2^{n_2}; p_3 = q + 2^{n_3}; ...; p_k = q + 2^{n_k}[/tex], because even if there is not a prime such that [tex]p_k = q + 2^{n_k}[/tex] 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 [tex]2^1[/tex] is the first class such that among the elements there is a prime (in fact, the only element is a prime)
CRGreathouse
CRGreathouse is offline
#48
Jan3-08, 09:45 AM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by al-mahed View Post
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.

Quote Quote by al-mahed View Post
The expression Q = [tex]\frac{2^n}{ln(2)}*(\frac{n-1}{n^2+n})[/tex] give us an estimate of the amount of primes between [tex]2^{n+1} and \ 2^n[/tex]

The formula [tex]\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})[/tex] should give us the probability of a particular sum of powers of two (inside the " nth-class [tex]2^n[/tex] " whose amount of numbers is obviously = [tex]2^n[/tex] ) represent a prime.
Good so far. It might be worth simplifying to [itex]1/n\log2[/itex] since if n is large the minor terms have little effect.

Quote Quote by al-mahed View Post
The formula [tex]\frac{1}{2^n}[/tex] 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.

Quote Quote by al-mahed View Post
The probability of both events is = [tex]\frac{\frac{1}{ln(2)}*(\frac{n-1}{n^2+n})}{2^n}[/tex]
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
[tex]\frac{n-1}{n(n+1)\log2}\approx\frac{1}{n\log2}[/tex], the probability of being prime, for the chosen number.

Quote Quote by al-mahed View Post
Let this particular sum be = q, so we ask if there are infinite prime numbers p such that [tex] p = q + 2^n[/tex].
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.

Quote Quote by al-mahed View Post
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 ([tex]p_k = q + 2^{n_k}[/tex] 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 [tex]p_1 = q + 2^{n_1}; p_2 = q + 2^{n_2}; p_3 = q + 2^{n_3}; ...; p_k = q + 2^{n_k}[/tex], because even if there is not a prime such that [tex]p_k = q + 2^{n_k}[/tex] 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
[tex]\sum_{k=1}^\infty\frac{1}{(2^k + q)\log(2^k+q)}\approx C+\sum_{k=2}^\infty\frac{1}{k\cdot2^k}[/tex]
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
CRGreathouse is offline
#49
Jan3-08, 09:50 AM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by al-mahed View Post
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.

A094076 seems to strongly suggest that such an infinite set exists.
al-mahed
al-mahed is offline
#50
Jan3-08, 07:14 PM
P: 258
Quote Quote by CRGreathouse View Post
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.

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 [tex]2^{n+1} - 2^n = 2^n[/tex] could be usefull to infer adjacent classes relations, or even not adjacent classes relations.

Quote Quote by CRGreathouse View Post
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 !

Quote Quote by CRGreathouse View Post

Quote Quote by al-mahed
The formula [tex]\frac{1}{2^n}[/tex]
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, [tex]5 = 2^0 + 2^2[/tex] 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 [tex]x = 2^0 + 2^2 + 2^n[/tex] be a prime number? The probability of x be prime "times" the probability of [tex]2^0 + 2^2 = 5[/tex] be combined with an exponent [tex]2^n[/tex]. But you are right, this last probability is wrong.

Quote Quote by CRGreathouse

Quote Quote by al-mahed
Let this particular sum be = q, so we ask if there are infinite prime numbers p such that [tex] p = q + 2^n[/tex].
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:

[tex]1 = 2^0[/tex]
[tex]
2 = 2^1[/tex]
[tex]
3 = 2^0 + 2^1[/tex]
[tex]
4 = 2^2[/tex]
[tex]
5 = 2^0 + 2^2[/tex]
[tex]
6 = 2^1 + 2^2 [/tex]
[tex]
7 = 2^0 + 2^1 + 2^2[/tex]
[tex]
8 = 2^3 [/tex]
[tex]
9 = 2^0 + 2^3[/tex]
[tex]
10 = 2^1 + 2^3[/tex]
[tex]
11 = 2^0 + 2^1 + 2^3[/tex]
[tex]
12 = 2^2 + 2^3[/tex]
[tex]
13 = 2^0 + 2^2 + 2^3[/tex]
[tex]
14 = 2^1 + 2^2 + 2^3[/tex]
[tex]
15 = 2^0 + 2^1 + 2^2 + 2^3[/tex]
[tex]
16 = 2^4 [/tex]
[tex]
17 = 2^0 + 2^4[/tex]
[tex]
18 = 2^1 + 2^4[/tex]
[tex]
19 = 2^0 + 2^1 + 2^4[/tex]
[tex]
20 = 2^2 + 2^4

etc...[/tex]

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[tex]^{[1]}[/tex]). For example, 3th-class (exponent 2^3):

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

[tex]8 = 2^3 [/tex] the first element is the exception

[tex]9 = 2^0 + 2^3[/tex] where [tex]2^0[/tex] is an element of the zero-class

[tex]10 = 2^1 + 2^3[/tex] where [tex]2^1[/tex] is an element of the first class

[tex]11 = 2^0 + 2^1 + 2^3[/tex] where [tex]2^0+2^1[/tex] is an element of the first class

[tex]12 = 2^2 + 2^3[/tex] where [tex]2^2[/tex] is an element of the second class

[tex]13 = 2^0 + 2^2 + 2^3[/tex] where [tex]2^0+2^2[/tex] is an element of the second class

[tex]14 = 2^1 + 2^2 + 2^3[/tex] where [tex]2^2+2^3[/tex] is an element of the second class

[tex]15 = 2^0 + 2^1 + 2^2 + 2^3[/tex] where [tex]2^1+2^2+2^3[/tex] 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.

Quote Quote by CRGreathouse
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
[tex]\sum_{k=1}^\infty\frac{1}{(2^k + q)\log(2^k+q)}\approx C+\sum_{k=2}^\infty\frac{1}{k\cdot2^k}[/tex]
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
al-mahed is offline
#51
Jan3-08, 07:22 PM
P: 258
We know that [tex]\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... \ =1[/tex], but your sum above seems to converges to 0.16667 or something like that
CRGreathouse
CRGreathouse is offline
#52
Jan3-08, 09:18 PM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by al-mahed View Post
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, [tex]5 = 2^0 + 2^2[/tex] 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?

Quote Quote by al-mahed View Post
Then in the nth-class what is the probability of [tex]x = 2^0 + 2^2 + 2^n[/tex] be a prime number? The probability of x be prime "times" the probability of [tex]2^0 + 2^2 = 5[/tex] be combined with an exponent [tex]2^n[/tex]. 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.

Quote Quote by al-mahed View Post
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[tex]^{[1]}[/tex]).
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?

Quote Quote by al-mahed View Post
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.

Quote Quote by al-mahed View Post
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.

Quote Quote by al-mahed View Post
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
CRGreathouse is offline
#53
Jan3-08, 09:22 PM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by al-mahed View Post
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
al-mahed is offline
#54
Jan6-08, 09:51 AM
P: 258
Quote Quote by CRGreathouse View Post
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.


Register to reply

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