Equal Numbers of Factors

Number Theory Level 3

2013, 2014 and 2015 have an interesting property regarding their factors. They all have the same number of factors: 8. What is the smallest positive integer $N$ that has the same number of factors as $N+1$ and $N+2$ ?

Bonus : Can you write a program that finds all of the numbers less than $10^6$ that also have this property?

Source: 2013 Florida Fall Interschool

The answer is 33.

2 solutions

Mark Mottian
Jan 4, 2014

This is the Python programme that I wrote to find all numbers less than 10^6 that have the property:

def factors (n):
    count = 0

    for x in xrange(1, n+1):
        if n % x == 0:
        count = count + 1

    return count

a = 0

while a < 10**6:
    if factors(a) == factors(a + 1) == factors(a + 2):
        print a, a+1, a+2
        a = a + 1
    else:
        a = a + 1

It's certainly not the fastest algorithm, seeing that it takes more time for larger numbers. Can somebody suggest how I can optimise this? If you give it enough time, it will output all numbers (there's a lot of them) that satisfy the property.

To answer the question, the programme outputs "33, 34, 35" as the first set where N = 33.

I...I confused because, but this problem must solve or prove with mathematics thinking, not a program or math features, ^_^ 2013 = 3 x 11 x 61 ; 2014 = 2 x 19 x 53 ; 2015 = 5 x 403.

Budi Utomo - 7 years, 5 months ago

The second part of the question says you can write a program to find all numbers less than 10^6 that have this property. I interpreted this as a programming problem.

Mark Mottian - 7 years, 5 months ago

Instead of having to find the # of factors of each number 3 times, consider using a list to store the values. This is essentially "trading memory for time," which can be very helpful if you get a good deal on memory.

Also, you don't need to put the a = a + 1 command in both cases. Just neglect the "else" case and put it after the "if" statement.

Consider using a for loop instead.

There is a good way to shorten your factors method. Can you find it in my program below?

def numOfFactors(n):
    num = 0
    for i in range(1, int(n**0.5 + 1)):
        if n % i == 0:
            num += 2

    return num

factorDict = {1 : 1, 2 : 2}
for a in range(1, 10**6):
    if a + 2 not in factorDict:
        factorDict[a + 2] = numOfFactors(a+2)

    if factorDict[a] == factorDict[a + 1] and factorDict[a] == factorDict[a + 2]:
        print(a, a+1, a+2)

Michael Tang - 7 years, 5 months ago

@Michael Tang – WOW!

Mark Mottian - 7 years, 5 months ago

2015 = 5.403 = 5.13.31

Piyushkumar Palan - 7 years, 5 months ago

Sorry if I am wrong, but are you a relative of Vilashni Mottian?

A Former Brilliant Member - 6 years, 5 months ago

Finn Hulse
Feb 17, 2014

I went through and listed all numbers amount of factors. When I got to 33, it had 8 factors, and so did 34 and 35.

actually there are only 4 factors for 33, 34 and 35...

敬全钟 - 7 years, 3 months ago

Equal Numbers of Factors

Source: 2013 Florida Fall Interschool

The answer is 33.

2 solutions

0 pending reports