suemcm@ihuxl.UUCP (Sue McMullen) (05/16/84)
I need to do the following for my MTH230 Discrete Structures class at North Central College: Prove or disprove that: Every positive odd integer >=3 is the sum of a prime and a power of two. For example: 0 3 = 2 + 2 1 5 = 3 + 2 1 7 = 5 + 2 1 2 9 = 7 + 2 or 5 + 2 2 11 = 7 + 2 etc. The background for this problem that has been learned in the class is the various ways to prove problems, i.e. direct proof, proof by contradiction, proof by mathematical induction. As far as any information on the properties of the primes and the powers of two that is yet to be determined. ANY HELP AT ALL WILL BE GREATLY APPRECIATED!!!! Please send responses to the net, ihlpi!suemcm, ihuxl!suemcm or call me on x0935. Thanks again!!!
howard@metheus.UUCP (Howard A. Landman) (05/24/84)
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