/*
 * Copyright (c) 2012 Daniel Hartmeier <daniel@benzedrine.ch>
 * All rights reserved.
 *
 * http://www.scoopshot.com/hiring-developer/
 *
 * Find the first 7-digit palindromic prime found in consecutive digits of pi
 *
 * See also
 *
 *   http://en.wikipedia.org/wiki/Pi#Spigot_algorithms
 *   http://www.mathpropress.com/stan/bibliography/spigot.pdf
 *   http://www.codecodex.com/wiki/Calculate_digits_of_pi#C
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DIGITS (20000 / 4 * 14)

int main()
{
	int arr[DIGITS + 1];
	char buf[DIGITS + 1], p[8];
	int i, off = 0, carry = 0, k = 0;

	for (i = 0; i <= DIGITS; ++i)
		arr[i] = 2000;
	p[7] = 0;
	for (i = DIGITS; i > 0; i -= 14) {
		int j, sum = 0;
		for (j = i; j > 0; --j) {
			sum = sum * j + 10000 * arr[j];
			arr[j] = sum % (j * 2 - 1);
			sum /= j * 2 - 1;
		}
		sprintf(buf + off, "%04d", carry + sum / 10000);
		off += 4;
		for (; k + 7 < off; ++k) {
			int n;
			memcpy(p, buf + k, 7);
			if (p[0] != p[6] || p[1] != p[5] || p[2] != p[4])
				continue;
			printf("palindrome @%d %s\n", k, p);
			if ((n = atoi(p)) < 2)
				continue;
			for (j = 2; j * j < n; ++j)
				if (n % j == 0)
					break;
			if (j * j > n) {
				printf("prime palindrome @%d %s\n", k, p);
				return 0;
			}
		}
		carry = sum % 10000;
	}
	return 0;
}