//--------------------------------------------------------------------------
// enigma1364.c (c) 2005 by Charles Petzold
//
// "Four All" by Adrian Somerfield, New Scientist, 29 October 2005, page 22
//
// Four numbers, each four different digits, each containing the digit 4.
// Each satisfies four conditions, and doesn't satisfy four others.
//--------------------------------------------------------------------------

#include <stdio.h>

int IsPrime(int i)
{
	int j = 2;

	if (i < 2)
		return 0;

	while (j * j <= i)
	{
		if (i % j == 0)
			return 0;
		j += 1;
	}
	return 1;
}

int digit(int num, int dig)
{
	int i;

	for (i = 0; i < dig; i++)
		num /= 10;

	return num % 10;	
}

int test(int num, int condition)
{
	switch (condition)
	{
	// Number is a 4th power. 
	// Only two 4-digit numbers are 4th powers & contain the digit 4.
	
	case 1: return num == 7 * 7 * 7 * 7 || num == 8 * 8 * 8 * 8;

	// Number is divisible by 4.

	case 2: return num % 4 == 0;

	// 2-digit square followed by smaller 2-digit square.
	// Only a few possibilities contain the digit 4.

	case 3: return num == 4916 || num == 4925 || num == 4936 ||
		       num == 6416 || num == 6425 || num == 6436 ||
		       num == 8149 || num == 8164;

	// Product of 4 digits exceeds 2 to the 4th (or 16).
	// This is always true unless the number contains a zero.

	case 4: return digit(num, 0) != 0 && digit(num, 1) != 0 && digit(num, 2) != 0;

	// The number does not have 2 or more different prime factors.
	// It's either a prime, or it's a power of 2 or 3 or 7 or 11 ...
	// Only a few of these contain the digit 4

	case 5: return IsPrime(num) ||
		       num == 1024 || num == 2048 || num == 4096 ||
		       num == 7 * 7 * 7 * 7 ||
		       num == 17 * 17 * 17 || 
		       num == 43 * 43;

	// Each of the 4 digits is a perfect square.
	// Not possible.

	case 6: return 0;

	// The digits form an arithmetical series

	case 7: return num == 1234 || num == 2345 || num == 3456 ||
		       num == 4567 || num == 2468 ||
                       num == 4321 || num == 5432 || num == 6543 ||
                       num == 7654 || num == 8642;

	// The sum of the digits is prime, or the sum of the
	// two digits of the sum is 4.

	case 8:
		{
			int sum = digit(num, 0) + digit(num, 1) + digit(num, 2) + digit(num, 3);

			if (IsPrime(sum))
				return 1;

			if (num > 9 && sum < 100)
				return digit(sum, 0) + digit(sum, 1) == 4;
		}
	}

	return 0;
}

int main(void)
{
	int num, i, digits[4], true;

	// Loop through the possible numbers

	for (num = 1234; num <= 9874; num++)
	{
		// Extract the four digits

		for (i = 0; i < 4; i++)
			digits[i] = digit(num, i);

		// Check that at least one is 4.

		if (digits[0] != 4 && digits[1] != 4 && digits[2] != 4 && digits[3] != 4)
			continue;

		// Check that they're unique.

		if (digits[0] == digits[1] || digits[0] == digits[2] || digits[0] == digits[3] ||
		    digits[1] == digits[2] || digits[1] == digits[3] || digits[2] == digits[3])
			continue;

		// Now perform the tests

		true = 0;

		for (i = 1; i <= 8; i++)
			true += test(num, i);

		if (true == 4)
		{
			printf("%i passes tests ", num);

			for (i = 1; i <= 8; i++)
				if (test(num, i))
					printf("%i ", i);

			printf("\n");

		}

	}
	return 0;
}