Duncan's conjecture

[fltdabbler]

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, 16 + 41, 32 + 21

45 = 2+43, 4+41, 8+37, 16 + 29, 32 + 13

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

[wblipp]

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

[wblipp]

Simple Heuristic

There are about 500 odd numbers "n" between 1025 and 2047. Each of these has 10 numbers of form n-2^k - the conjecture says at least one of these will be prime. These are odd numbers of size about 2¹⁰, so we expect them to be prime on average about 2/ln(2¹⁰) = 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¹⁰ = 0.0332

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

[Jens K Andersen]

It's trivial to compute counter examples. A Google search on the smallest above 1: "127, 149, 251, 331, 337, 373"

[Fusion_power]

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

[R.D. Silverman]

Originally Posted by fltdabbler

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

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?

[philmoore]

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, On integers of the form 2^k + p and some related problems 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.

[Zeta-Flux]

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: http://arxiv.org/PS_cache/math/pdf/0507/0507374v3.pdf
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.)

[fltdabbler]

Originally Posted by R.D. Silverman

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?

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.

[R.D. Silverman]

Originally Posted by fltdabbler

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:

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.

[ATH]

Testing n=2^k +- p:

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