Mini-Challenges‎ > ‎

Mini-Challenge #1: Smallest number with 2013 divisors



What is the smallest number with exactly 2013 divisors?



If you think you've solved it, or if you're stuck, email pi3challenge@sheffield.ac.uk or tweet to @pi3challenge


The solution is now posted here ...



I don't really understand the question ...

Don't panic! It's supposed to be hard. Let's start from the beginning ...

What is a divisor? 

In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.

Let's try a simple example. 3 is a divisor of 6. Why? Because 6 divided by 3 is a whole number (i.e. 2). In other words, 6 can be divided by 3 without leaving a remainder.  On the other hand, 5 is not a divisor of 6, because 6 divided by 5 leaves a remainder of 1.

The number 6 can be divided by 1, 2, 3 and 6. So it has four divisors in total.  Note that both 1 and 6 are counted as divisors.

Here are the divisors of the first few numbers :

 ndivisors
total
 1 1 1
 2 1,2 2
 3 1,3 2
 4 1,2,4 3
 5 1,5 2
 6 1,2,3,6 4
 7 1,7 2
 8 1,2,4,8 4
 9 1,3,9 3
 10 1,2,5,10 4
 11 1,11 2
 12 1,2,3,4,6,12 6
 13 1,13 2
 14 1,2,7,14 4
 15 1,3,5,15 4

If a number n has exactly two divisors (i.e. 1 and n itself) we say that "n is prime". As you can see from the table, the first six prime numbers are 2,3,5,7,11 and 13. (Exercise: find the next six primes).

Can I write a Python code to find divisors?

Yes, you can find all the divisors of a number n with just a single line of Python code. For example, to find the divisors of 120, try entering:

>>> n = 120
>>> divisors = [i for i in range(1,n+1)
if n % i == 0]
>>> print divisors
>>> print len(divisors) 

I have added a similar code at the bottom of the page, ndivisors.py. The code find the number of divisors of the first 1000 numbers, and identifies the prime numbers.

This code is very inefficient. You could try to search all the numbers, 1,2,3, etc., until you find the first one with exactly 2013 divisors. But this is extremely inefficient. The answer is so large that you will not find it in this way ... unless you can devise a very clever algorithm. It will simply take the computer too long. Instead, you need to use your on-board personal computer (i.e. your brain!)


Can I have a hint?

Let's try some simpler questions first. The number 2013 has eight divisors -- can you find them all?  Three of its divisors are prime numbers -- can you find these?  In fact, any number which is the product of three distinct primes has 8 divisors. Do you see why? Can you find a way to generalize this statement?

How many divisors does 60 have? 60 can be written as 2 x 2 x 3 x 5, or as 22 x 3 x 5. Note that 2, 3 and 5 are prime numbers. This is an example of prime factorization.  There are many ways to factor the number 60, for example, 4 x 15, or 2 x 10 x 3. But its prime factorization is unique.

There is a simple relationship between a number's prime factorization, and its number of divisors. Can you find this relationship?

Once you have a general formula for the number of divisors in terms of the prime factorization,  you need to think about how to get the smallest-possible number.

If you need more hints, try pi3challenge@sheffield.ac.uk or @pi3challenge

ċ
ndivisors.py
(1k)
Sam Dolan,
18 Mar 2013, 01:53
Comments