S.A.Tricky

Here's an S.A.T. problem that stumped my students and me (for a little while).

Problem:

a - b = 10
a² - b² = 50

Find b.

Solution:

My instincts were to look for a connection between (a - b)² and a² - b², but it's really much simpler than that. Solve for a in terms of b in the first equation, and substitute into the second equation.

---

Edit: The original post contained a mistake. (10 + b)² = 100 + 20b + b², not 100 + 2b + b².

Solution...

Hide solution.

IDEAs

Here's another S.A.T. problem.

Problem:

In the correctly worked addition problem to the left, A, B, D, E, I, and S each represent a different digit. What is the smallest possible value of D?


Solution:

You don't need to know what every digit in the problem is. You only need to know which digits have to be assigned to which letters in order for the addition problem to work.

Starting in the one's column, E + A = A, or E + A = A + a carry digit. The most two one-digit numbers can add to is 18, so the carry digit would have to be 10. If E + A = 10 + A, then E = 10, but we know that E < 10 (all of the variables are single digits). Thus, E + A = A, and E = 0. Filling that value into the puzzle we get: The value of A doesn't matter. We can forget about the two right-most columns of the addition and look at two left columns. B + S = 10I + D. The most that B and S can add up to is 17 (with B and S equaling 9 and 8), and the least they can sum to is 3 (if B and S equal 1 and 2). However, if B + S < 10, I = 0. We can't have another 0, so B + S must be greater than 10. Therefore, I = 1. Since we've used up 0 and 1, smallest digit we have left for D is 2. We can use 4 for B and 8 for S to make B + S = 12. If we use these values to fill in the puzzle, it all adds up. The smallest number D can be is 2.

Solution...

Hide solution.

Prime Factorization

This problem comes form Project Euler. I solved it with a computer program written in C++.

Problem:

What is the largest prime factor of the number 600851475143?

Solution:

It is tempting to write a function to find the prime factorization of a given number. Why? Because it's cool. I wrote that function, too, but I'm only going to cover the process of solving the given problem.

When solving a programming problem, you should always start on paper to get an idea of what your algorithm needs to do. Suppose I wanted to find the largest prime factor of 90, or what if I wanted to find the largest prime factor of 260? I might do something like what I did in the diagram to the right. In words, our algorithm might look something like this:

Start with your number.
Keep dividing by its factors until you find the biggest prime.

How is the computer going to know which numbers to try? We'll be using a loop, so we can start at 2 and work our way up through the numbers. The computer's factorization of 260 would look more like this: 13/7 is less than 2, 13/8 is even smaller, and 13/9 is smaller still. We're not going to get any more numbers that go evenly into 13 once our divisor is greater than 13/2. We can stop dividing whenever the divisor is greater than half of the number we're dividing. Notice that 4 divides 260, but it did not come up in our list of factors. Instead, we divided 2 out twice. 2 is prime, and 4 is not. Our algorithm automatically sifts out composite numbers by dividing their prime factors out first. In words, our algorithm looks something like this:

Start with your number.
Divide it by 2.
If it divides evenly, keep dividing by 2, otherwise, try 3.
If it divides evenly, keep dividing by 3, otherwise, try 4.
Keep dividing this way until your divisor is greater than or equal to half the original number.

Now we're ready for pseudo-code:

from ( divisor = 2 until divisor >= number/2 )
{
  if ( number is divisible by divisor ) then
    number <- number/divisor
  else
    increment divisor
}
return number

We would like to save our selves some time by only using prime numbers, but we don't have a list of primes. However, we do know that 2 is the only even prime number, so after trying 2, we only have to try odd numbers, which cuts our list of divisors in half. This is my final code:

unsigned long long LargestPrimeFactor(unsigned long long number)
{
  int divisor = 2;
  while(divisor<=sqrt((float)number))
  {
    if(number%divisor==0)
    {
      number = number/divisor;
    }
    else if(divisor==2)
    {
      divisor++;
    }
    else
    {
      divisor+=2;
    }
  }
  return number;
}

The largest prime factor of 600851475143 is 6857.

Solution...

Hide solution.