Duncan's conjecture
 

any odd n is expressible as "some prime" + "some power "k" of two "

eg. for n< or = 2^6, k is an element or elements of {1,2,...2^5}

interestingly the number of elements (powers of 2) different n will 'enjoy' between 1 and all such elements

eg. 53 = 2+51, 4+49, 8+45, [U]16 + 41[/U], 32 + 21

45 = [U]2+43[/U], [U]4+41[/U], [U]8+37[/U], [U]16 + 29[/U], [U]32 + 13

[/U]While I "see" this as obvious, a proof eludes me, largely because of the generality of the two terms. I suspect my conjecture is:
1. Likely true but if not, counter-examples will be hard to find;
2. A proof (for or against) is either immensely simple or immensely difficult.

I am interested in different methods to uniquely characterize integers beyond expressing them in different bases: a rose by any other name is a rose. (Useful and interesting methods.)

Any contributions would be most welcome, especially references to literature

Heuristics suggest that counter examples should be easy to find. It didn't take me long to find 1199.

[B]Simple Heuristic[/B]

There are about 500 odd numbers "n" between 1025 and 2047. Each of these has 10 numbers of form n-2[sup]k[/sup] - the conjecture says at least one of these will be prime. These are odd numbers of size about 2[sup]10[/sup], so we expect them to be prime on average about 2/ln(2[sup]10[/sup]) = 0.2885.

We expect them to be composite with probability 1-0.2885 = 0.7115

We expect all 10 to be composite with probability 0.7115[sup]10[/sup] = 0.0332

So we expect 0.332 * 500 = 17 of these numbers to be counterexamples.

It's trivial to compute counter examples. A Google search on the smallest above 1: [URL="http://www.google.com/search?hl=en&q=%22127%2C+149%2C+251%2C+331%2C+337%2C+373%22"]"127, 149, 251, 331, 337, 373"[/URL]

I find it interesting that 53 = 16 + 41.

This appears to be a relative anomaly of small numbers. As the number in question grows larger, the possibility that it fits the expression becomes less and less.

Fusion

[QUOTE=fltdabbler;112968]any odd n is expressible as "some prime" + "some power "k" of two "

eg. for n< or = 2^6, k is an element or elements of {1,2,...2^5}

Any contributions would be most welcome, especially references to literature[/QUOTE]

Sigh. What is it that compels people who are ignorant of a subject to
propose such speculations as this???

In point of fact, it has been proven that there are infinitely many numbers
that are NOT so representable. I believe that Richard Guy's book contains
a reference. I am not in my office at the moment, so I don't have the
book handy.

I suggest that the next time you want to speculate about such things that
you ask "Is it known whether......<such and such is true>", rather than
putting forth a conjecture in ignorance?

The conjecture was originally made in 1849 by Polignac and is not true, as noted by William and also by Jens. Check out the paper by Paul Erdös, [I]On integers of the form 2^k + p and some related problems[/I] in Summa Brasiliensis Mathematicae, 2(1950), pages 113-123. I don't have the paper in front of me, but as I recall, he discusses the history of the problem and proves that there are infinite arithmetic sequences of positive integers which cannot be represented in such a form. Such numbers are analogous to Riesel numbers when one replaces the exponent by a negative integer.

fltdabbler,

philmore gave the correct reference. Erdös' proof uses what are called "covering systems". There are a number of open problems with regards to this subject, as well as a number of results. If you go to the link: [url]http://arxiv.org/PS_cache/math/pdf/0507/0507374v3.pdf[/url]
you will find a recent paper on the subject. Their reference #16 (by Porubsky and Schonheim) is a good general paper on the subject.

(R.D. Silverman is also correct that Richard Guy's book on unsolved number theory problems has a section on this stuff.)

[quote=R.D. Silverman;113019]Sigh. What is it that compels people who are ignorant of a subject to
propose such speculations as this???

In point of fact, it has been proven that there are infinitely many numbers
that are NOT so representable. I believe that Richard Guy's book contains
a reference. I am not in my office at the moment, so I don't have the
book handy.

I suggest that the next time you want to speculate about such things that
you ask "Is it known whether......<such and such is true>", rather than
putting forth a conjecture in ignorance?[/quote]

You are quite right: I got over-excited, and not a little obsessed over the issue. I should not have called it a conjecture. Please excuse my naivete: I realize I am dabbling in things over my head; it is difficult to inhabit a nebulous (and dark) realm in which relevant techniques, information, forums or other resources are below or far far above my level.

That said, thank-you to all who responded: especially with the references to websites and literature. I have found it difficult to locate such resources myself, largely for not knowing where to look.

Soon after posting, I realized that the original question (for odd n, n=2^k+p) was naive to suppose. (Where I posed the question elsewhere ie other forums) I changed it to (n= 2^k +/- p) - a better question, as it doesn't restrict the set of possible k.

For what it's worth, I realized my question was naive for a couple of reasons:
1. It would be too powerful. That is, the ease of picking an arbitrarily large n and subtracting successive 2^k to find primes would fly in the face of the amount of effort currently & previously expended to find primes.

2. For a relatively simple expression to occur to me it must have occurred to others: and must have been dealt with. Lo and behold we have de Polignac numbers: Thanks again for pointing me towards them.

3. Intuitively, it seems to me, given an arbitrarily large prime gap between some Pn...Pm, all the small 2^k up to the size of the gap are eliminated from possibility in my original expression (2^k < Pm-Pn) - this leaves few elements in the set of possible 2^k. Very far from convincing but still suggestive to me that my original expression would be less likely to hold the larger the gap got.

Being all that as it may, thank-you all again for considering the query and for your time and trouble.

[QUOTE=fltdabbler;113082]You are quite right: I got over-excited, and not a little obsessed over the issue. I should not have called it a conjecture. Please excuse my naivete: [/QUOTE]

It isn't a matter of naivete. The first thing to do with ANY such conjecture
is to test it. A tiny bit of computing would have revealed that the conjecture
was false. It is also somewhat arrogant to name your own conjecture.
If others want to credit you, that is fine.

Testing n=2^k +- p:

n=12749 has no solution for k<=20000.

[quote=R.D. Silverman;113094]It isn't a matter of naivete. The first thing to do with ANY such conjecture
is to test it. A tiny bit of computing would have revealed that the conjecture
was false. It is also somewhat arrogant to name your own conjecture.
If others want to credit you, that is fine.[/quote]

1. Agreed; I don't have access to (or familiarity with) computing resources for such testing. I realize it must be annoying for such as myself to waltz in spouting ideas which a) are old hat and b) subject to approaches which to you are second nature and are a first line of attack. I'll be more careful & thorough in the future. I did test it by hand though obviously not up to 127. I am embarrassed that 127 is so small and was within my means to check; I didn't expect that.

2. I wasn't aware of the strength of the word conjecture: an ignorance of etiquette. I already know not to use "postulate" - what word(s) would have been appropriate? Supposition?

[QUOTE=fltdabbler;113115]1. Agreed; I don't have access to (or familiarity with) computing resources for such testing. I realize it must be annoying for such as myself to waltz in spouting ideas which a) are old hat and b) subject to approaches which to you are second nature and are a first line of attack. I'll be more careful & thorough in the future. I did test it by hand though obviously not up to 127. I am embarrassed that 127 is so small and was within my means to check; I didn't expect that.

2. I wasn't aware of the strength of the word conjecture: an ignorance of etiquette. I already know not to use "postulate" - what word(s) would have been appropriate? Supposition?[/QUOTE]

Given that you are posting here, you have the resources. We are not responsible for your lack of familiarity.

The fact that you "see" a false result as obvious is also troubling. Why are you pretending to do mathematics? What exactly is the point of creating a conjecture just to make a conjecture? Mathematicians don't sit around asking random questions just to get their name attached to something.

Do not come here to have your education handed to you. There are institutions in place for just that purpose. They are called "colleges" and "universities". They provide the structure to speed the process of giving you an effective foundation. If you don't have access, you should expect the process of building your foundation to be slow and frustrating. That's why colleges cost so much, they're worth it.

Now, this forum is a fantastic resource, [i]for those who have the initiative to do some work beforehand[/i]. You give no evidence for why the conjecture is true, or any sense that you have done any analysis on it for more than an hour or so. This belies a lack of initiative.

Go find books yourself. There are thousands to pick from. Read voraciously. Work the problems. Read the footnotes. When you find a book that touches on something that you think is interesting, go read the books it references. When you come to a dead-end, THEN you come here and ask for guidance. Do not use the expertise of the members of this forum to circumvent your own lack of initiative.

[quote=Orgasmic Troll;113119]Given that you are posting here, you have the resources. We are not responsible for your lack of familiarity.

The fact that you "see" a false result as obvious is also troubling. Why are you pretending to do mathematics? What exactly is the point of creating a conjecture just to make a conjecture? Mathematicians don't sit around asking random questions just to get their name attached to something.

Do not come here to have your education handed to you. There are institutions in place for just that purpose. They are called "colleges" and "universities". They provide the structure to speed the process of giving you an effective foundation. If you don't have access, you should expect the process of building your foundation to be slow and frustrating. That's why colleges cost so much, they're worth it.

Now, this forum is a fantastic resource, [I]for those who have the initiative to do some work beforehand[/I]. You give no evidence for why the conjecture is true, or any sense that you have done any analysis on it for more than an hour or so. This belies a lack of initiative.

Go find books yourself. There are thousands to pick from. Read voraciously. Work the problems. Read the footnotes. When you find a book that touches on something that you think is interesting, go read the books it references. When you come to a dead-end, THEN you come here and ask for guidance. Do not use the expertise of the members of this forum to circumvent your own lack of initiative.[/quote]

Points taken. I didn't intend to misuse the forum; indeed I was grateful for the time spent on my query & said so. Especially for the pointers toward literature which I asked for and received. This forum is a fantastic resource & I don't take it for granted. As to attaching my name, I misused the word 'conjecture' as I explained. Thanks once again for all the responses to the initial query: I rest a little wiser...

... and, yes, I'm off now... Though maybe a mod could rename the title of the thread?