Couple More Puzzle Solutions

Not much work got done yesterday....

You are an employer of a company and you are in the process of hiring a new employee. You must pay this employee in gold at a rate of 1 oz. per day. This employee will work for you for 7 days and must be paid every day, no more and no less then 1 oz. per day. You happen to have one 7 oz. bar of gold and may make two cuts on this piece of gold. What cuts would you make in order to successfully complete the task?

I had to think about this one for a while. I kept thinking "two cuts....I wonder if you need to make one cut, and then stack the pieces and make another cut somehow". Then it dawned on me that the only way this would work is if the employee gave back some of his earnings in exchange for the total sum that he was due up to that point in the week. This breaks down to be a binary number problem. The two cuts leave you with 1 oz, 2 oz, and 4 oz chunks (powers of two).

Day 1: Give employee 1 oz
Day 2: Employee gives you 1 oz, you give employee 2 oz
Day 3: Give employee 1 oz
Day 4: Employee gives you 1 oz and 2 oz, you give employee 4 oz
Day 5: Give employee 1 oz
Day 6: Employee gives you 1 oz, you give employee 2 oz
Day 7: Give employee 1 oz.

Please write a function that will determine if a number passed into it is a perfect number. How would you test this?

I'll admit, I had to look up what a perfect number was. I knew that it was related to Mersenne primes, but I did not remember all of the details. (Simple definition: A number whose factors sum up to the number itself. Example: 6 has factors of 1, 2, and 3 [don't use 6 as a factor for this purpose]. 1+2+3 = 6).

A theorem states: If 2^k-1 is prime, then 2^k-1(2^k-1) is perfect and every even perfect number has this form.

Nobody has found an odd perfect number thusfar, so chances are that they do not exist. So, I'll take advantage of this theorem while writing my code. Having a knowlege of binary arithmetic is extremely helpful here.

2^k-1 will be a string of 1's when represented in binary. For example, 2³-1 = 7, which is 111 in binary.

2^k-1 is simply a power of two, and when you multiply a binary number by a power of two, you're simply doing a bit shift (i.e., adding zeros to the right side of the number). For example, 2^3-1 = 2² = 4, which is 100 in binary. 111 * 100 = 11100, or 111 shifted two bits to the left.

So, the function to check if a given number is a perfect number would be as follows:

static bool IsPerfect(long number)
{
  string x=Convert.ToString(number, 2);

  // Check for form: 111110000

  int lastOne = x.LastIndexOf("1");   // 4  = k - 1
  int firstZero = x.IndexOf("0");     // 5  = k

  if (firstZero < lastOne)
     return false;   // There's a 1 after a 0

  if (lastOne + firstZero != x.Length)
     return false;   // Improper bit length

  // The number is now in the form of a perfect number, but that
  // is not sufficient.  We need to prove that 2^k - 1 is prime before this
  // can be a perfect number.  Luckily, there's a very small list of 
  // mersenne primes that fit our number's 64-bit length, so let's just
  // see if k is one of these.

  int[] mersenneExponents = new int[] {2,3,5,7,13,17,19,31,61};

  for (int i=0; i < mersenneExponents.Length; i++)
  {
      if (mersenneExponents[i] == firstZero)
          return true;
  }

  return false;
}

To test as I was building it, I came up with a list of known perfect numbers and known numbers that were in the form of perfect numbers but were not perfect numbers, and I ran them through the function to verify the appropriate results.

Probably took me 45 minutes to an hour to write the function and blog it here... That's probably way too long for an actual interview environment, which is why I live in Ohio and not Washington. :P

Also, it might have been easier since we have a finite list of possibilities to just calculate the known perfect number, and then check against the given candidate. Wouldn't have to dork around with strings that way....