/*
 * bigprime.c
 * 3/30/84   (revised 12/15/88)
 * 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.
 * Takes 24.5 hours on IBM PC.
 * Takes 14.25 hours on the Z8001 (segmented).
 * Takes 3.24 hours on the hp 386.
 * Takes about 3 hours on stevesf (i386/20), about 4:15 on belmont.
 * Takes about 32 minutes on jsbach (i486/33).
 * Takes about 3 minutes on acer (PIII/500) 4/4/01.
 * Takes about 49 seconds on eMach1 (Celeron 2.3 GHz) 7/17/03.
 * Takes about 29 seconds on hppav2 (AMD Phenom II 830, 2.80 GHz) 10/03/10.
 * Takes about 40 seconds on macair (Intel Core 2 Duo 1.86 GHz) 8/29/12.
 * Takes about 24 seconds on macair2 (Intel Core I7 2.2 GHz) 6/05/20.
 * Takes about 20 seconds on macair3 (Intel QuadCore Core I5 1.1 GHz) 6/05/20.
 */

#include <stdio.h>

static	char n[39760L];		/* 2^i in decimal digits, low order in n[0] */

main () {
	register char *cp;	
	register char *cpmax;	/* pointer to highest digit thus far */
	register int c = 0;		/* carry */
	register long i;
	n[0] = 1;			/* 2^0 */
	cpmax = &n[0];
	for (i = 1; i <= 132049L; i++) {
		for (cp = &n[0]; cp <= cpmax; cp++) {
			*cp <<= 1;
			if (c) {
				(*cp)++;
				c--;
			}
			if (*cp > 9) {
				*cp -= 10;
				c++;
			}
		}
		if (c) {
			c--;
			*cp = 1;
			cpmax = cp;
		}
		if ((i & 0x3FF) == 0) {
			fprintf (stderr,"%ld\n", i);
		}
	}
	--n[0];
	print(cpmax);
}

print(cpm)
char *cpm;
{
	register char *cp;
	for (cp = cpm; cp >= &n[0]; cp--)
		putchar (*cp + '0');
	putchar ('\n');
}