### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 178,002 hits

Advertisements

Programming Enigma Puzzles

12 June 2015

Posted by on **From New Scientist #2382, 15th February 2003** [link]

George’s son has listed all the factors of the first few dozen numbers.

“Dad – the number 48 has exactly ten factors, 1, 2, 3, 4, 6, 8, 12, 16, 24 and 48. I reckon it is the smallest number with exactly ten factors.”

“Quite right, son. Now can you find the smallest number which has exactly one thousand factors, including itself and 1?”

“Er, yes, I think so. It is …”

“I won’t ask you to calculate the smallest number with exactly one million factors, but can you tell me how many different prime factors it has?”

“Hmm…”

Can you answer both of George’s questions?

[enigma1226]

Advertisements

%d bloggers like this:

Instead of a brute force approach (which will take a long time to reach the large numbers required in the solutions), we do a bit of analysis which gives some straightforward code, that can be used to find the smallest number with any specified number of divisors. This Python program runs in 134ms.

Solution:The smallest number with one thousand divisors is 810,810,000. The smallest number with one million divisors has 11 different prime factors.The smallest number with one million divisors is:

Using

int2words()from theenigma.pylibrary gives (using short scale notation):See OEIS A005179.

Without considering multiple factorisations of 1,000,000 we would arrive at a larger number with one million divisors, that has 12 prime factors:

Hi Jim

I get the same answer as you, using Mathematica 10 ;

1) FactorInteger [810810000] = {{2, 4}, {3, 4}, {5, 4}, {7, 1}, {11, 1}, {13, 1}}

This number has 6 different prime factors ie 2,3,5,7,11 and 13

Number of divisors (from exponents) = 5 * 5 * 5 * 2 * 2 * 2 = 1000 No.

But, are we correct on this part of the question – as the question says:

“Quite right, son. Now can you find the smallest number which has exactly one thousand factors, including itself and 1?” Should we be looking for 998 factors?

2) FactorInteger [173804636288811640432320000] = {{2, 9}, {3, 4}, {5, 4}, {7, 4},

{11, 4}, {13, 4}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {31, 1}}

– which shows this number has 11 different prime number factors, ie:

2,3,5,7,11,13,17,19,23,29 and 31

Number of divisors (from exponents) = 10 * 5^5 * 2^5 = 1000000 No.

PS

A minor point – a small typo in line 79 (ie divsors) gives 3 errors in the output

Counting the number of divisors by multiplying the successors of the exponents of the primes in the prime factorisation will include both 1 and the number itself. (1 when the exponents are all zero, and the number itself when all the exponents are at their maximum value).

If the question had asked for 1000 divisors

excluding1 and the number itself then we would be looking for a number with 1002 divisors (using my algorithm). The smallest such number is: