Contagiously Composite!

Number Theory Level 4

Which is the greatest number of divisors that a positive integer number less than 1000 can have?

The answer is 32.

4 solutions

Seth Lovelace
Nov 29, 2014

To solve this, we want to first find the most primes we can multiply together that result in a number less than 1000. This can easily be found by:

2x3x5x7 = 210

To count the number of divisors of a number, we can take the exponent of each prime factor, add 1, and then multiply them together. As of current, we want to maximize this number.

It can be seen that by multiplying by 4, the # of factors will be maximized. Why?

${ a }^{ p }\ast { b }^{ q }\ast { c }^{ r }\ast { d }^{ t }...=Q\\ (p+1)(q+1)(r+1)(t+1)...\quad = \sigma (Q)$

Now, the maximum amount of distinct prime factors we can have is 4, and it can easily be seen that by making our p = 3 [ i.e. multiplying by 4 ] we will maximize this relation with respect to the distinct prime numbers given for the number of factors while remaining below our limit of 1000.

For this reason, $\sigma (Q)$ = $\boxed{32}$

Note: $\sigma (Q)$ = # of Factors of Q

Keil Cerbito
Dec 24, 2014

Hmm.. i use this method to solve this one..

$1000 > (a^b)*(c^d)*(e^f)...$

where a,c,e and so on were prime numbers and b,d,f and so on where the exponents that will determine the number of divisors

First thing I do is to determine the largest product of consecutive prime numbers that is less than 1000..

It is indeed 210 which a factors of 2,3,5 and 7. because multiplying again by 11 will result to 2310 which is higher than 1000

so.. $(2^b)*(3^d)*(5^f)*(7^h) < 1000$

I use first, the lowest prime number and raise it to the greatest possible value of the exponent, while the other prime numbers were raised to 1.

$(2^3)(3)(5)(7) = 840$ which is $< 1000$

$(2^4)(3)(5)(7) = 1680$ which is > $1000$

so b = 3

then I use the next prime number which is 3 to do the same thing..

$(2^3)(3^2)(5)(7) = 2520$ which is > $1000$

so d=1 , f=1 and h=1

therefore, the rest of the factors must only raised to one, and could also conclude that 840 is the integer number with the greatest number of divisors. But the question is to determine its number of divisors, not the number itself..

so ,we can get the number of divisors by using the DIVISOR FUNCTION by looking at the exponents of each prime numbers for the prime factorization of 840,

$(2^3)(3^1)(5^1)(7^1)$

number of divisors = $(3+1) * (1+1) * (1+1) * (1+1)$ = $\boxed{32}$ , which is the final answer =)

Drop TheProblem
Nov 27, 2014

The greatest number of divisors is 32 from the number $840=2^3*3*5*7$

You have not proven the fact that the other numbers less than $1000$ has less than $32$ distinct divisors.

Pi Han Goh - 6 years, 6 months ago

I will attempt to fill the gaps, to prove that there are no numbers less than 1000 with more than 32 divisors. Using the equation for the number of factors (i.e. the one in the middle of Seth's argument): the number of factors that a number has cannot be prime. This is because $2^{37}$ >1000. For a number N to have two prime-power factors, say $p^{a1}$ & $p^{a2}$ and have more than 32 factors in total, then the average of a1 and a2 must be more than $\sqrt{32}$ ~ 5.6. However, if we look at 5 X 7, we have $2^{6}$ X $3^{4}$ > 1000. Similarly, for 3 factors the cube root of 32 is ~ 3.1, so our first option is 36 (3 X 3 X 4) factors. However, $2^{3}$ X $3^{2}$ X $5^{2}$ >1000. Finally, with a product of 4 primes the number 2 must have the highest power. This leaves $2^{2}$ X $3^{2}$ X 5 X 7 >1000. In each case the first option represents the number with the lowest value, hence the proof is complete. Hope that helps :)

Curtis Clement - 6 years, 5 months ago

Aryan Gaikwad
Apr 4, 2015

public static void main(String args[]){
    int max = 0;
    for(int i = 1; i < 1000; i++)
        if(fact(i) > max) max = fact(i);
    System.out.println(max);
}

static int fact(int number){
    int num = 2;
    for(int i = 2; i <= number / 2; i++)
        if(number % i == 0) num++;
    return num;
}

Contagiously Composite!

The answer is 32.

4 solutions

0 pending reports