//-------------------------------------------------------------------
// enigma1346.c (c) 2005 by Charles Petzold (www.charlespetzold.com)
//
// "Divide into Primes" from "New Scientist", 25 June 2005, page 56
//
// Eight coins with denominations 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p,
// are divided between two people. Each person has at least two coins, 
// and each person's monetary total is a prime.
//
// You ask one of the persons:
// "Do you have x number of coins?" and the answer is "No."
// You then ask:
// "Do you have the y pence coin?" and the answer is "Yes."
//
// For some x, y, those answers are sufficient for you to determine 
// the monetary value of that person's coins. What is it?
//
// Let's use the lower 8 bits of an integer to represent the coins
// a person has, where the least significant bit is the 1p coin.
// For example, the integer 13 is the bits 1101, which indicates
// possession of the 1p, 5p, and 10p coins. 
//
// In all these functions, the integer iBits will represent this
// number. The integer ~iBits represents the other person's coins,
// if only the bottom 8 bits are considered.

#include <stdio.h>

// This function counts the number of coins by counting the number
// of 1 bits in the bottom 8 bits of iBits.

int NumCoins(int iBits)
{
	int i, iSum = 0, iMask = 1;

	for (i = 0; i < 8; i++)
	{
		if ((iBits & iMask) != 0)
			iSum ++;

		iMask <<= 1;	
	}
	return iSum;
}

// This function is similar except that it returns the total
// monetary value of the coins.

int CoinSum(int iBits)
{
	int iPence[] = { 1, 2, 5, 10, 20, 50, 100, 200 };
	int i, iSum = 0, iMask = 1;

	for (i = 0; i < 8; i++)
	{
		if ((iBits & iMask) != 0)
			iSum += iPence[i];

		iMask <<= 1;	
	}
	return iSum;
}

// Also required is a function that indicates if a number
// is prime.

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;
}

// It is now possible to determine which distributions of the eight
// coins result in each person getting at least 2 coins, and each
// person's monetary value being prime.  The following code (which is
// commented out) prints just one person's monetary value. 
// The total of the two persons is always 388.

/*

int main(void)
{
	int iBits;

	for (iBits = 0; iBits < 256; iBits++)
	{
		if (NumCoins(iBits) > 1 && NumCoins(~iBits) > 1 &&
			IsPrime(CoinSum(iBits)) && IsPrime(CoinSum(~iBits)))
				printf("%i\n", CoinSum(iBits));
		
	}
	return 0;
}

*/

// If you uncomment, compile, and run that code -- you'll also need to 
// comment out the main function below -- you'll find 8 possibilities, 
// which are:
//
// 	71 = 1 + 20 + 50
// 	107 = 1 + 2 + 5
// 	131 = 1 + 10 + 20 + 100
//	137 = 2 + 5 + 10 + 20 + 100
//	251 = 1 + 50 + 200
//	257 = 2 + 5 + 20 + 200
//	281 = 1 + 10 + 20 + 50 + 200
//	317 = 2 + 5 + 10 + 100 + 200
//
// There are 3 possibilities where there are 3 coins,
// 2 possibilities where there are 4 coins, and 
// 3 possibilities where there are 5 coins.
//
// Your first question "Do you have x number of coins"
// eliminates either 2 or 3 of these possibilities, and
// the second question "Do you have the y pence coin?"
// gives you the conclusive information. 
//
// In other words, if you eliminate the 3-coin possibilities,
// you're looking for a coin that shows up in only one of 
// those that are left. If there is no unique coin, try
// considering only the 3-coin and 5-coin possibilities, 
// and then (if that doesn't work) try the 3-coin and
// 4-coin possibilities.
//
// Cutting to the chase:
//
// The solution comes about when the first question is
// "Do you have 5 number of coins?" (The answer, remember,
// is "No") and the second question is "Do you have the 
// 10p coin?" to which the answer is "Yes." The person has
// coins that total 131p.
//
// Or, we can write a program that does this work for us.

int main(void)
{
	int iNumSkip, iNum, iBits, iUnique, iNotUnique;

	// iNumSkip is x in the question "Do you have
	// x number of coins?"  It has to be between 2 and 6.

	for (iNumSkip = 2; iNumSkip < 7; iNumSkip++)
	{
		// The lowest 8 bits of the following two variables 
		// will keep track of the unique coins in all
		// the remaining possibilities.

		iUnique = iNotUnique = 0;

		// Loop through the number of coins.

		for (iNum = 2; iNum < 7; iNum++)
		{
			// But skip the one equal to iNumSkip.

			if (iNum == iNumSkip)
				continue;

			// Now loop through the possible distributions
			// of coins.

			for (iBits = 0; iBits < 256; iBits++)
			{
				// We're looking for a number of coins
				// that equals iNum, and both person's coins
				// adding up to a prime number.

				if (NumCoins(iBits) == iNum && 
					IsPrime(CoinSum(iBits)) && 
					IsPrime(CoinSum(~iBits)))
				{
					// If a bit in iBits is set, and a bit
					// in iUnique is set, that coin is 
					// actually not unique.

					iNotUnique |= iBits & iUnique;

					// Adjust iUnique for the actual coins,
					// but don't allow coins already flagged
					// as not unique.

					iUnique |= iBits;
					iUnique &= ~iNotUnique;
				}					
			}
		}

		// At this point, if iNumSkip is the number of coins
		// in the first question, then iUnique should have 
		// just 1 bit set, which is the value queried in the
		// second question.
		//
		// Let's first check that iUnique has only 1 bit set.

		if (NumCoins(iUnique) != 1)
			continue;

		// if that test is passed, we'll loop through again,
		// and now find the distribution where the iUnique bit is set.

		for (iNum = 2; iNum < 7; iNum++)
		{
			if (iNum == iNumSkip)
				continue;

			for (iBits = 0; iBits < 256; iBits++)
			{
				// Notice the first clause.

				if ((iUnique & iBits) && 
					NumCoins(iBits) == iNum &&
					IsPrime(CoinSum(iBits)) && 
					IsPrime(CoinSum(~iBits)))
				{
					printf("%ip", CoinSum(iBits));
				}
			
			}
		}
	}	
	return 0;
}