Posts tagged with: prime numbers

The number 6 has four different factors,1,2,3,6.What is one possible two digit integer that has exactly three different positive factors?

A number will only have an odd number of factors if it’s a perfect square. It it has only 3 factors, then it’s the square of a prime number. So pick a two-digit square of a prime number. 25 or 49 work: their factors are 1, 5, 25 and 1, 7, 49, respectively.

It’s exciting times around PWN HQ—lots of things going on. 2014 should be a fun year for SAT prep. That has nothing to do with this contest, of course. I just like to open these contest posts with a little friendly chatter. I bet nobody even reads this stuff. :/ ANYWAY, here’s a challenge question!

For all positive integers n, let ↭n equal the number of unique prime factors of n. For example, ↭12 = 2, because there are 2 unique prime factors of 12: 2 and 3. If a is a positive integer less than 500,000, what is the greatest possible value of ↭a?

Post your answer in the comments—the first correct answer from someone who hasn’t won a contest before wins a Math Guide! Comments are set to require moderation until tomorrow to add a little suspense into the contest.

All the usual contest rules apply. One recent addition to the contest rules I’d like to draw your attention to:

  • No answer changing. When you post a comment, I get an email with that comment, and that’s what I use to judge the contest. Edits applied to your comment later don’t count, even if the edit occurs before someone else wins. Don’t post your comment until you’re sure of your answer.
Good luck!

UPDATE: Wow—I thought this would be tougher for you guys! Congrats to everyone who got it right, especially to Nick, who got his answer in first. Explanation follows below the cut…

The key to getting this question right is recognizing that the smaller the prime factors you use, the more you’ll be able to fit in before your product exceeds 500,000. Therefore, all you need to do to solve this problem is test out the incremental products of the smallest prime numbers!

2 × 3 = 6
2 × 3 × 5 = 30
2 × 3 × 5 × 7 = 210
2 × 3 × 5 × 7 × 11 = 2,310
2 × 3 × 5 × 7 × 11 × 13 = 30,030
2 × 3 × 5 × 7 × 11 × 13 × 17 = 510,510 ← Oops, too big!

What we’ve just shown there is the smallest number that can have 2 unique prime factors is 6, the smallest number that can have 3 unique prime factors is 30, …, the smallest number that can have 7 unique prime factors is 510,510. Therefore, no positive integer less than 500,000 can have more than 6 unique prime factors.

So this isn’t a super important thing as far as how often it appears on the SAT, but it does pop up time and again, so if you’re shooting for perfection (or close to it) you might want to pay attention. Otherwise, you can get by just fine without this little nugget (but you might as well read it, since you’re here anyway).

Do you know what prime factorization is? Basically, the prime factorization of a number is the way you would build that number by multiplying together only prime numbers. To find the prime factorization of a number, divide by 2 if you can. Do that as many times as you can. Once you can’t do that anymore, try dividing by 3 as many times as you can. Then by 5. Then by 7. Then by 11. I think you get the idea.

Let’s try one together, like best friends

What is the prime factorization of 13728?

Whoa. Big number. Lots of people like to make trees when they do this. Let’s do that. Damn I wish you and I were in the same room with a chalkboard right now. This is going to take flippin’ forever.

See how, when I couldn’t divide by 2 anymore, I went to three, and then to 11? I knew I was done when I had two prime numbers, 11 and 13. If I multiplied all those numbers back together, I’d get 13728 again. For serious. Try it:

2 × 2 × 2 × 2 × 2 × 3 × 11 × 13 = 13728

So why do I need to know this?

Because sometimes the SAT asks hard questions (and if you took the October 2011 SAT, you can confirm) about the lowest multiple of two numbers that’s also perfect square. It just so happens that prime factorization is a great way to find a perfect square.

The prime factorization of a perfect square will contain even numbers of each prime number. Look back at the prime factorization of 13728. That’s not a perfect square. There are 5 2s, and one each of 3, 11, and 13. We can use this information to find the lowest multiple of 13728 that’s a perfect square. In order to make a prime number, we’re going to need another 2, another 3, another 11, and another 13. Yikes. That’s gonna be a big number.

2 × 2 × 2 × 2 × 2 × 2 × 3 × 3 × 11 × 11 × 13 × 13= 11778624

Peep the bold underlines. Those are the factors I’ve added. My new product is huge. It’s also a perfect square. Seriously.

11778624 = 3432

And there are no multiples of 13728 that are less than 11778624 that are perfect squares. Scout’s honor.

What would an SAT question about this look like?

Glad you asked. Try this (no multiple choice — it’s a grid-in):

  1. If p2 is a multiple of both 8 and 35, and p is a positive integer, what is the least possible value of p?

So…yeah. Start by doing a prime factorization of 8 and 35.

8 = 2 × 2 × 2
35 = 5 × 7

Note that you have odd numbers of all three used prime factors. You’re gonna need another 2, another 5, and another 7.

2 × 2 × 2 × 2 × 5 × 5 × 7 × 7 = 19600
p2 = 19600

Confirm that 19600 is a multiple of both 8 and 35 (of course it is):

19600 ÷ 8 = 2450
19600 ÷ 35 = 560

Yes, it worked. So what’s p? Just take the square root of 19600!

19600 = 140
p = 140

Note the tempting false shortcut: just multiply 8 by 35 and square the result. But if you do that, you get 78400 for p2 and 280 for p. That’s not the smallest possible p, as we just showed.

Like I said, you don’t see this often on the SAT, but if you’re shooting for perfection, you’ll want to know this relationship between prime factors and perfect squares.