Project Euler 501 Write-up

“The eight divisors of 24 are 1, 2, 3, 4, 6, 8, 12 and 24. The ten numbers not exceeding 100 having exactly eight divisors are 24, 30, 40, 42, 54, 56, 66, 70, 78 and 88. Let f(n) be the count of numbers not exceeding n with exactly eight divisors. You are given f(100) = 10, f(1000) = 180 and f(10^6) = 224427. Find f(10^12).”

The problem as initially stated looks to be very difficult, but by using elementary techniques and some of the basic tenets of Number Theory, we can iteratively rephrase the problem until it becomes trivial to solve. Also, because the problem description only has the positive divisors of positive numbers, we’re restricting our discussion to concern only the positive integers for the rest of this summary (e.g. there’s no 24 being evenly divided by -3 exactly -6 times).

Let’s start simplifying this problem by temporarily forgoing the “count of numbers” part in “count of numbers not exceeding n with exactly eight divisors.” In order to find the count of numbers in a range with exactly eight divisors, we must first determine if any specific number, N, in that range has exactly eight divisors.

We’re given 24 as an example, with its’ eight divisors being [1, 2, 3, 4, 6, 8, 12, 24]. It’s trivial that every number has 1 and itself as divisors, therefore we can reduce the problem to finding the pattern behind [2, 3, 4, 6, 8, 12]. Since all the divisors come in unique pairs ([2,12];[3,8];[4,6]) that when the two individual components are multiplied together, yield the number N, we can rewrite the formula for the list of eight divisors of N to be: [1, p, q, r, N/r, N/q, N/p, N].

Now that we have a general formula, we need to find values for p, q and r. In the example given, 24, the corresponding values for p, q and r are 2, 3, 4 respectively, which is a trivial case. The problem description also gives us other numbers with exactly eight divisors, so let’s apply our formula to those numbers as well to try and figure out a pattern:

30: [1, p=2, q=3, r=5, N/r, N/q, N/p, 30]

40: [1, p=2, q=4, r=5, N/r, N/q, N/p, 40]

42: [1, p=2, q=3, r=7, N/r, N/q, N/p, 42]

54: [1, p=2, q=3, r=9, N/r, N/q, N/p, 54]

If you notice the last number in each of the lists, N, is exactly a product of p times q times r, which are all the unique divisors of N, which means we can rewrite the problem again in three parts as:

∃ distinct p,q,r ∈ ℤ+ such that p|N, q|N and r|N; AND 1 < p,q,r < N

AND

∀ z ∈ ℤ+ | If z ≠ p, z ≠ q and z ≠ r ; then z∤N

AND

N = p*q*r

We have some triplets that work for p, q and r that are given in the problem description, so let’s see if this tentative solution holds true.

Since the triplet (2,3,4) fits the equation, and so does (2,3,5), let’s try (2,3,6):

2*3*6 = 48, which is a number with 10 divisors. Welp, that doesn’t quite fit.

What makes 24, 30, 40, 42 and 54, as the product of p, q and r, different from similar products of similarly distinct p, qand r?

My trick to ~half of the Project Euler problems is to apply the Unique Factorization Theorem to the numbers that fit the desired profile, and to those that don’t, and ascertain the difference between the two groups. By doing this, you’re really breaking up an integer into it’s individual multiplicative components, akin to seeing the individual jigsaw pieces that make up a finished puzzle.

UFT applied to 24 = 2*2*2*3
UFT applied to 30= 2*3*5
UFT applied to 40= 2*2*2*5
UFT applied to 42= 2*3*7
UFT applied to 54= 2*3*3*3
UFT applied to 56= 2*2*2*7
UFT applied to 66= 2*3*11
UFT applied to 70= 2*3*7
UFT applied to 78= 2*3*13
UFT applied to 88= 2*2*2*11

and let’s reorder this list into groupings based on the right side:

UFT applied to 30= 2*3*5
UFT applied to 42= 2*3*7
UFT applied to 66= 2*3*11
UFT applied to 78= 2*3*13

UFT applied to 70= 2*5*7

UFT applied to 24 = 2*2*2*3
UFT applied to 40= 2*2*2*5
UFT applied to 56= 2*2*2*7
UFT applied to 88= 2*2*2*11

UFT applied to 54= 2*3*3*3

The first two groups are obviously the product of three distinct primes. The last two are likewise obviously a prime cubed times a second, distinct from the first, prime.

Wait, what?! Is it really that formulaic? Are all the numbers that fit this profile either three distinct primes multiplied together, or a prime cubed times a different prime?

Our earlier guess of the numbers merely being distinct wasn’t restrictive enough, since the triplet (2,3,6) fits that profile, but it’s multiplicative result doesn’t have exactly eight divisors. Let’s see what the UFT tells us about 48:

UFT applied to 48 = 2*2*2*2*3

OH! 48 is a prime raised to the fourth times a second prime, that’s why it doesn’t work. What about 50?

UFT applied to 50= 2*5*5

It doesn’t follow one of the two formulas [where p,q,r are distinct primes]:
N = p*q*r or N = p^3*q, therefore it doesn’t have exactly eight divisors.

Let’s try the reverse, how many divisors does the product 29, 31, 37 have? Why eight of course! [1, 29, 31, 37, N/37, N/31, N/29, N]. It couldn’t have any others, since it’s the product of three primes.

Huzzah! Looks like we have a (better) possible solution! Let’s test it!

f(x) is the current working solution at this point in time, which is the count of numbers less than 100 (or 1000) that fit either the first or second pattern.

(***) f(100) = 10. Cool, looks like it this theory holds true.

f(1000) = 179. The problem statement says f(1000) = 180, so we’re obviously missing a number here.

Let’s take a look back on our two formulas, p*q*r and p^3*q. We’ve shown the first one always yields numbers with eight divisors when we focused on the product of 29, 31 and 37. Let’s focus on figuring out why the second one, p^3*q, works.

In the case of N = 24, its’ factors are: [1, 2, 3, 4, 6, 8, 12, 24], or rewritten in terms of p =2 and q = 3, [1, p, q, p^2, N/p^2, N/q, N/p, N].

If you set r = p^2 in the first formula, you get the second formula, so let’s try setting both the variables q and r in the formula N = p*q*r to powers of p.

N = p * p^a * p^b = p^(a+b+1)

Rewritten in list of divisors form: [1, p, p^a, p^b, N/p^b, N/p^a, N/p, N].

Since N = p^(a+b+1), there exists a number N, that has exactly eight divisors, that is equal to exactly a prime raised to the sum of a+b+1. Let’s fix p = 2 for illustration sake, therefore N must be a power of 2. Let’s iterate through the powers of two to see the first one that fits.

N = 2^(a+b+1) = 2^1 = 2 [Has two divisors; 1, 2]

N = 2^(a+b+1) = 2^2 = 4 [Has three divisors; 1, 2, 4].

N = 2^(a+b+1) = 2^3 = 8 [Has four divisors; 1, 2, 4, 8 (see a pattern?)].

N = 2^(a+b+1) = 2^4 = 16 [Has five divisors; 1, 2, 4, 8, 16].

N = 2^(a+b+1) = 2^5 = 32 [Has six divisors; 1, 2, 4, 8, 16, 32].

N = 2^(a+b+1) = 2^6 = 64 [Has seven divisors; 1, 2, 4, 8, 16, 32, 64].

N = 2^(a+b+1) = 2^7 = 128 [Has eight divisors (!!!!!!!!!!!!!!!!!!!!!!!!!)].

So, N = p^(a+b+1) = 128 = 2^(a+b+1) = 2^7; therefore a+b+1 = 7.
Knowing a+b = 6, let’s go back to this list of divisors for this case: [1, p, p^a, p^b, N/p^b, N/p^a, N/p, N]. The value for a in p^a cannot equal the value for b in p^b, because then they would not be distinct divisors, and neither a or b can equal one because then it would be repeating the second item in the list, p. We can infer from this the set of equations: a+b = 6, a ≠ 1, b ≠ 1, a ≠ b, yielding the single solution a = 2 and b = 4.

We can now reformulate the list to be:
[1, p, p^2, p^4, N/p^4, N/p^2, N/p, N]

Which only has one value, N = 128, that exists below 1000, therefore we’ve accounted for the one missing value in f(1000) = 180 from earlier. If we set p = 3, then we get 2187, which also only has eight divisors. This third way of calculating a number with exactly eight divisors occurs far less frequently than the first two, and isn’t explicitly listed in the given numbers that follow this pattern in the problem description, which makes this the hardest part of the problem to ascertain.

AND WE’RE DONE! Except….. remember when I said “Let’s start simplifying this problem by temporarily forgoing the ‘count of numbers’?” Let’s go back and solve the given problem, knowing that we’ve found the theory behind it.

See the (***) above? In that paragraph, I’m using the function f(x) without really defining what it is mathematically. We’ve figured out that all numbers with exactly eight divisors follow either one of three patterns, all consisting of multiplying prime numbers [with restrictions] together. Our first two solutions, p*q*r and p*q^3, can be written in pseudocode as:

def func(n):
for each prime p from 2 to n:
>>>>>for each prime q from nextPrime[p] to n:
>>>>>>>>>>for each prime r from nextPrime[q] to n:
>>>>>>>>>>>>>>>if(p*q*r < n && p != q && p != r && q !=r)
>>>>>>>>>>>>>>>>>>>>count++;
end def

def func2(n):
for each prime p from 2 to n:
>>>>>for each prime q from nextPrime[p] to cubedRootof(n):
>>>>>>>>>>if(p*q^3< n && p != q)
>>>>>>>>>>>>>>>count++;
end def

The sum of the result of both functions above gives us the tentative solution, that yields 10 for f(100) and 179 for f(1000). By adding the function below onto that sum…

def func3(n):
for each prime p from 2 to seventhRootOf(n):
>>>>>if(p^7< n)
>>>>>>>>>>count++;
end def

…we obtain f(1000) = 180 and also can check that this solution works for all given data in the problem by verifying that 224427 = f(10^6). Therefore:

f(x) = func(x) + func2(x) + func3(x)

Mathematica has this function called NextPrime(N) that returns the next prime strictly greater than N, which shouldn’t theoretically exist, but absolutely works for small values of N [One can’t quite call it on a 1024+ bit number, but it works on small numbers by cheating and using extensive memoization and heuristics] Using this, we can iterate through ONLY the set of prime numbers, which makes the above functions trivial to write in Mathematica and very few other languages, the major reason this language is best for this exact problem.

So, let’s finish this explanation by answering the question: Find f(10^12).

f(10^12) = func(10^12) + func2(10^12) + func3(10^12)

f(10^12) = 190,614,467,420 + 7,297,845,280 + 15

f(10^12) = 197,912,312,715. Huzzah!