| Newsgroups: net.math
Path: decwrl!decvax!mcnc!unc!ulysses!gamma!exodus!dhc
Subject: Re: Proof wanted (Spoiler)
Posted: Tue May 1 07:45:59 1984
The author of the previous note requests a proof for the conjecture
"Every positive odd integer >= 3 is the sum of a prime and a power of 2."
The conjecture is false. The first six counterexamples are
127, 149, 251, 331, 337, 373.
--
David H. Copp
|
| Newsgroups: net.math
Path: decwrl!decvax!mcnc!ncsu!uvacs!gmf
Subject: Proof wanted
Posted: Tue May 1 18:25:26 1984
Concerning x odd & >= 3 --> x = 2^k + p for some k and prime p .
This may be relevant:
"It can be proved that for every natural number k there are infinitely
many k-powers of natural numbers which are not of the form a^k + p,
where a is an integer and p a prime. (cf. Clement [2])."
W. Sierpinski
* Elementary Theory of Numbers *
(Warsaw, 1964), p. 113
"Clement, P. A. ...
[2] Representation of integers in the form: a k-th power plus a prime,
Amer. Math. Monthly 56 (1949), p. 561."
Ibid., p. 450
Gordon Fisher
|
|
Hmmm - I thought it a little suspicious, the density of powers of two falls
to zero very quickly, and primes aren't much better, so statistics sort of
implied the thing was wrong.
/Bevin
|
| From: ROLL::USENET "USENET Newsgroup Distributor" 26-MAY-1984 22:09
To: HARE::STAN
Subj: USENET net.math newsgroup articles
Newsgroups: net.math
Path: decwrl!decvax!ittvax!dcdwest!sdcsvax!sdcrdcf!hplabs!tektronix!ogcvax!metheus!howard
Subject: Re: mathproof
Posted: Wed May 23 15:59:44 1984
In cases like this, I always like to run through a few examples to see if
any obvious patterns develop. The only thing I could notice right off the
bat was that the prime would have to be odd, and the power of 2 NOT 2**0,
if the odd number was bigger than 3.
So I wrote a small program to generate all the primes less than 2048 using
the Sieve of Eratosthenes, and then use those to test all the odd numbers
less than 2048. The only thing to be careful of (for efficiency) is that the
inner loop loops on powers of 2, not primes, because (1) there are fewer of
them, and (2) they are somewhat easier to generate unless you do your data
structures cleverly (I was too lazy).
Surprise! The smallest number which cannot be expressed in this form appears
to be 127.
127 - 64 == 63, 63 % 3 == 0;
127 - 32 == 95, 95 % 5 == 0;
127 - 16 == 111, 111 % 3 == 0;
127 - 8 == 119, 119 % 7 == 0;
127 - 4 == 123, 123 % 3 == 0;
127 - 2 == 125, 125 % 5 == 0;
This was only a half-hour's work. You can use the program if you give me
credit (or blame). Here it is:
---------------------------------------------------------------------------
/************************************************************************/
/* conjecture.c -- copyright (c) 1984 by Howard A. Landman */
/* All rights reserved */
/************************************************************************/
#include <stdio.h>
/* MAX can of course be increased if you have the CPU time. */
#define MAX 2047
#define TRUE 1
#define FALSE 0
int prime[MAX]; /* prime[i] will be nonzero iff i is prime */
main()
{
/* figure out primes */
Sieve();
/* look for counterexamples */
Test();
}
Sieve()
/* Sieve of Eratosthenes */
{
register int *p,*end,*q;
register int i;
end = prime + MAX;
p = prime;
while (p < end)
{
/* Even numbers fail. Including 2 for these purposes. */
*p++ = FALSE;
/* All odd numbers are allowed for the moment. */
*p++ = TRUE;
}
/* Run the sieve. */
for (p = prime + 3; p < end; p += 2)
{
if (*p)
{
i = p - prime;
for (q = p + i; q < end; q += i)
*q = FALSE;
}
else
/* not a prime, don't sieve it */
continue;
}
fprintf(stderr,"Sieve done\n");
}
Test()
{
register int p2,i;
/* for all odd numbers */
for (i = 3; i < MAX; i += 2)
{
/* for all powers of 2 less than the number */
for (p2 = 1; p2 < i; p2 <<= 1)
if (prime[i-p2])
break;
if (p2 < i)
/* Succeeded with sum. */
/* If you want sums printed out, uncomment next line. */
/* Semicolon OUTSIDE gives null statement otherwise. */
/*
printf("%5d = %5d + %5d\n",i,i-p2,p2)
*/
;
else
{
/* Failed - THIS IS A COUNTEREXAMPLE! */
printf("%5d CANNOT BE EXPRESSED AS A SUM OF THE GIVEN FORM\n",i);
/* This break causes the program to stop at the */
/* very first counterexample when uncommented. */
/*
break;
*/
}
}
}
---------------------------------------------------------------------------
The output begins and ends:
---------------------------------------------------------------------------
127 CANNOT BE EXPRESSED AS A SUM OF THE GIVEN FORM
149 CANNOT BE EXPRESSED AS A SUM OF THE GIVEN FORM
251 CANNOT BE EXPRESSED AS A SUM OF THE GIVEN FORM
331 CANNOT BE EXPRESSED AS A SUM OF THE GIVEN FORM
...
1927 CANNOT BE EXPRESSED AS A SUM OF THE GIVEN FORM
1969 CANNOT BE EXPRESSED AS A SUM OF THE GIVEN FORM
1973 CANNOT BE EXPRESSED AS A SUM OF THE GIVEN FORM
1985 CANNOT BE EXPRESSED AS A SUM OF THE GIVEN FORM
---------------------------------------------------------------------------
Have fun!
Howard A. Landman
ogcvax!metheus!howard
|