2718 goofs…
"How many factors does 270 have?"
This question was on my combinatorics final. It was designed for kids to use a quick counting method based on prime factorization, but to allow my laggards to have a reasonable chance to make a complete list.
270 has 16 factors: 1, 2, 3, 5, 6, 9, 10, 15, 18, 27, 30, 45, 54, 90, 135, 270
| 2050 | 2150 | 2051 | 2151 | |
| 30 | 1 | 2 | 5 | 10 |
| 31 | 3 | 6 | 15 | 30 |
| 32 | 9 | 18 | 45 | 90 |
| 33 | 27 | 54 | 135 | 270 |
I hope you can clearly see the 2 by 2 by 4 calculation that is in play.
So the goof? Look at the prime factorization: 2*3*3*3*5.
I am looking at two papers where the kids knew to factor down to primes, but then added: 2+3+3+3+5= 16
Ouch. 3 point question. Award 1, or 0? I'm not going to say which I did.
But are there other numbers (I haven't given this much thought) where the sum of their prime factors equals their number of factors? Is there anything special about these numbers?
That’s really funny! I’ll think about it.
Okay, so I can say something about numbers divisible by 1 or 2 primes. If we have a number of the form p^n for prime p, then we need np = n + 1, which only has solutions for n = 1, p = 2.
For two primes, p^m*q^n, we need mp + nq = mn + m + n + 1. Now, here’s a cute little trick: bring everything over to the right and collect the ms and ns. We have
mn + (1 – p)m + (1 – q)n + 1 = 0. Now, pull a little completing-the-square-type trick, by adding and subtracting to both sides to get
mn + (1 – p)m + (1 – q)n + (1 – p)(1 – q) = pq – p – q. Now the LHS factors as
(m + 1 – q)(n + 1 – p) = pq – p – q.
So, if we have any factorization of the RHS, we can choose m and n to match that factorization on the LHS. For instance, take p = 3, q = 5, so pq – p – q = 15 – 5 – 3 = 7 which we can factor as 1*7. Then we have two possible systems, either
m + 1 – 5 = 1, n + 1 – 3 = 7 so m = 5, n = 9 or
m + 1 – 5 = 7, n + 1 – 3 = 1 so m = 11, n = 3. This gives us two numbers which work, 474609375 and 22143375. For any pair of primes, we’ll get some number of solutions, where the number depends on how many factorizations of pq – p – q there are.
How very Euler of you! Awesome…
Here’s a puzzle I came across that I thought you might like. I have a “decent” solution to it, but not a “beautiful” solution:
Find the unique positive integer n such that n^3 and n^4 together contain all of the digits 0, 1, …, 9 exactly once.
Looks cute. Immediately we have some bounds.
We need 10 digits, so n^3 and n^4 must be 4 and 6 digits respectively
(If n^3 is a 3 digit number, n is a 1 digit number and n^4 cannot be 7 digits. If n^3 is a five digit number, n is greater than 10 and n^4 must be more than 5 digits.)
SInce n^3 is between 1000 and 9999, n is between 10 and 22
Since n^4 is between 100,000 and 999,999, n is between 17 and 32
This leaves n between 17 and 22. 20 is no good (repeated 0’s) 21 is no good (each power ends in ‘1’).
The only remaining candidates are 18 and 19. Check those two.
I like this. I want to give it to freshmen next September as an early puzzle, and see how they conduct their searches.
Thank you.
Ah, that’s good — you were more efficient at eliminating possibilities than I was.
Numbers for which “number of factors” = “sum of prime factors” are A078511 in the On-Line Encyclopedia of Integer Sequences.
The smallest such number is 2, the smallest non-trivial example is 60 (3*2*2=2+2+3+5), and the smallest odd example is 10395 (4*2*2*2=3+3+3+5+7+11).
They got a sequence for everything!
Maybe.
I wonder if there is a sequence
of 
such that 1, 2, n does not appear in the On-Line Encyclopedia of Integer Sequences…