/*
 * bigprime2.c
 * 8/1/94
 * Prints the prime 2^132049-1;  cf. Sci Am 4/84, p. 26.
 * Prints i on stderr every 2^10 to prove it's alive.
 * More efficient version of bigprime.c.
 */

#include <stdio.h>

/*
 * Compute the result in an array of base BASE digits,
 * where 2 * BASE fits in a long without overflow.
 * Taking BASE as a power of 10 makes it easy to print a decimal result.
 * This choice of base assumes 32-bit longs.
 * Use printf() format FORMAT to print a base BASE digit (with leading 0s).
 * The result contains 39751 decimal digits, so SIZE here is 39751/9 + 1.
 */
#define	BASE	1000000000L
#define	FORMAT	"%09ld"
#define	SIZE	4417

long	n[SIZE];

main()
{
	register long	*lp;	
	register long	*lpmax;		/* pointer to highest digit thus far */
	register int	c;		/* carry */
	register long	i;		/* exponent */

	c = 0;
	n[0] = 1;			/* 2^0 */
	lpmax = &n[0];
	for (i = 1; i <= 132049L; i++) {
		for (lp = &n[0]; lp <= lpmax; lp++) {
			*lp <<= 1;
			if (c) {
				(*lp)++;
				c--;
			}
			if (*lp > BASE) {
				*lp -= BASE;
				c++;
			}
		}
		if (c) {
			c--;
			*lp = 1;
			lpmax = lp;
		}
		if ((i & 0x3FF) == 0)
			fprintf(stderr,"%ld\n", i);
	}
	--n[0];
	print(lpmax);
}

print(lp) long *lp;
{
	printf("%ld", *lp--);			/* no leading 0s */
	while (lp >= &n[0])
		printf(FORMAT, *lp--);		/* with leading 0s */
	putchar('\n');
}

/* end of bigprime2.c */