Problem 5 (HMMT Nov 2018 Team)

This question from the HMMT contest will give us some practice in solving math problems using coding.

Question

Find the sum of all positive integers n such that \(1 + 2 + \ldots + n\) divides \( 15[(n + 1)^2 + (n + 2)^2 + \ldots + (2n)^2]\).

Solutions

Note that the following two solutions are not acceptable for the contest. They want mathematical solutions, not checking the answer using a computer program. That does not stop us from learning to code using this excellent example.

Solution A.

We first simplify both sums using the series rules.

The denominator simplifies to -

\(1 + 2 + \ldots + n = \frac{n (n+1)}{2}\)

To compute the numerator, we need to get the sum of squares from 1 to 2n and subtract sum of squares from 1 to n. Therefore, the numerator simplifies to -

\( 15[(n + 1)^2 + (n + 2)^2 + \ldots + (2n)^2]\)

\(= 15[ \frac{2n(2n+1)(4n+1)}{6} - \frac{n(n+1)(2n+1)}{6}]\)

\(= \frac{15n(2n+1)[2(4n+1)-(n+1)]}{6}\)

\(= \frac{15n(2n+1)(7n+1)}{6}\)

\(= \frac{5n(2n+1)(7n+1)}{2}\)

Their ratio is -

\(\frac{5(2n+1)(7n+1)}{(n+1)}\)

We need to find out for which values of N this ratio is an integer. We solve that using R, where we check for all values of N between 1 and 1000.

n=1:1000
ratio=(5*(2*n+1)*(7*n+1)) %% (n+1)
which(ratio==0)

## [1]  1  2  4  5  9 14 29

sum(which(ratio==0))

## [1] 64

We are creating a vector with integers 1 to 1000, computing the remainder for each value of the vector and then determining the values of N for which this remainder is 0.

Solution B.

This time we are not simplifying the expressions using sum rules. Instead we express the entire ratio as a function.

There is one problem however. We cannot pass the vector 1:1000 as an input to the function, because the function uses the sum function. Instead we have to run the function for each integer individually and then construct a vector out of the individual solutions. This is done using the sapply function in R.

r=function(N) {
    x= (N+1):(2*N)
    numer= (15*x^2) %>% sum
    denom= (1:N) %>% sum
    remainder = numer %% denom
}

num=1:1000
ratio=num %>% sapply(r) 
which(ratio==0)

## [1]  1  2  4  5  9 14 29

sum(which(ratio==0))

## [1] 64

The last two lines of the code are identical to solution A.