Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site metheus.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxl!ihnp4!zehntel!hplabs!tektronix!ogcvax!metheus!howard
From: howard@metheus.UUCP (Howard A. Landman)
Newsgroups: net.math
Subject: Re: mathproof
Message-ID: <246@metheus.UUCP>
Date: Wed, 23-May-84 21:59:44 EDT
Article-I.D.: metheus.246
Posted: Wed May 23 21:59:44 1984
Date-Received: Thu, 31-May-84 19:47:54 EDT
References: <1115@ihuxl.UUCP>
Organization: Metheus, Portland Oregon
Lines: 130

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