Divisibility

Relevant wiki: Sum of n, n², or n³

Note that

$S = \displaystyle \sum_{i=1}^n i = \frac{n(n+1)}{2}$

Note that $n, n+1$ are relatively prime to each other. Let $d = p^k$ be a prime power that divides $S$ (which is true for all four options in the problem). Suppose $2d = ab$ , such that $a$ divides $n$ and $b$ divides $n+1$ . We divide into two cases:

• If $p$ is odd, then the factor of 2 is irrelevant. One of $n$ and $n+1$ is necessarily even, so $n(n+1)$ is divisible by 2. It remains to see whether it is divisible by $d$ or not. Since $d$ is a prime power, we cannot have $a, b > 2$ together, since that would imply $p$ divides both $a, b$ and thus $n, n+1$ , contradicting the fact that $n, n+1$ are both relatively prime. Thus only one of $a, b$ is greater than 2. WLOG $a > 2$ . Then $b$ is not divisible by $p$ , so $a$ is divisible by $d$ .
• If $p = 2$ , then we follow the similar approach as above, except now that the factor of 2 is absorbed into $d$ . We need $ab = 2^{k+1}$ . It cannot happen that both $a, b > 1$ , as that would mean 2 divide both $a, b$ and thus both $n, n+1$ . So one of $a, b$ is 1, and the other is thus necessarily $2^{k+1}$ .

The conclusion is that if $p$ is odd, then one of $n, n+1$ must be divisible by $d$ , while if $p$ is even, then one of $n, n+1$ must be divisible by $2d$ . It's easy to see that if these conditions are satisfied, then indeed $S$ is divisible by $d$ .

Since $n, n+1$ is relatively prime, if we pick $n$ uniformly at random, $n$ is divisible by $m$ with probability $\frac{1}{m}$ and $n+1$ is divisible by $m$ with probability $\frac{1}{m}$ , and the two cannot happen simultaneously. Thus $S$ is divisible by $m$ with probability $\frac{2}{m}$ . For odd $d$ , pick $m = d$ , while for even $d$ , pick $m = 2d$ , as above. Since we pick $n$ from the range $[1, 120]$ , we indeed have " $n$ is divisible by $d$ " being a uniformly random event for $d = 2, 3, 4, 5$ (since $2, 3, 4, 5$ divide 120). This gives the following:

• A: $d = 2$ , so $m = 4$ , so $S$ is divisible by 2 with probability $\frac{2}{4}$ .
• B: $d = 3$ , so $m = 3$ , so $S$ is divisible by 3 with probability $\frac{2}{3}$ .
• C: $d = 4$ , so $m = 8$ , so $S$ is divisible by 4 with probability $\frac{2}{8}$ .
• D: $d = 5$ , so $m = 5$ , so $S$ is divisible by 5 with probability $\frac{2}{5}$ .

Thus 4 has the smallest probability.

Relevant wiki: Sum of n, n², or n³

Theorem:

$S_{ jn, jn-1} \equiv 0 \pmod { m}$ for odd $n$

$S_{ 2jn, 2jn-1} \equiv 0 \pmod { n }$ for even $n$

for a range of $n$ in which $n, j \in \mathbb{Z^+}$

Proof:

• Odd $n$

Let $n=2k-1$ , $k \in \mathbb{Z^+}$ :

$\Rightarrow S_n = S_{2k-1} = \frac{(2k-1)2k}{2} = k(2k-1) \equiv 0 \pmod {2k-1}$

This congruence (i.e when $S_n \equiv 0 \pmod {2k-1}$ ) occurs every consecutive $2k-1$ . So, for every $j \cdot (2k-1)$ where $j \in \mathbb{Z^+}$ :

$S_j(2k-1) \equiv 0 \pmod {2k-1}$

or in terms of odd $n$ :

$S_jn \equiv 0 \pmod {n}$

• Even $n$

Let $n=2k$ , $k \in \mathbb{Z^+}$ :

$\Rightarrow S_n = S_{2k} = \frac{2k(2k+1)}{2} = k(2k+1) \equiv k \pmod {2k}$

Here, $S_{2k} \equiv 0 \pmod {2k}$ doesn't occur every consecutive $2k$ . Rather, it occurs every 2 consecutive $2k$ i.e every $4k$ ( This is in order to add another $k$ for obtaining $S_m \equiv 0 \pmod {2k}$ . Observing that $S_{4k} = 2k(4k+1) \equiv 0 \pmod {2k}$ ). So, for every $j \cdot 4k$ where $j \in \mathbb{Z^+}$ :

$S_{4kj} \equiv 0 \pmod {2k}$

or in terms of $n$ :

$S_{2jn} \equiv 0 \pmod {n}$

Now for both odd and even cases, there could be additional cases when any of the $n-i$ where $i \in \{1,2,3,...,n-1\}$ can actually yields $0 \pmod {n}$ . We will need to check for what values of $i$ will this happen.

We have $S_{n-i}$ is the sum that we will need to comment on (an integer $n \in [1,120]$ )

$S_{n-i} = \frac{(n-i)(n-i+1)}{2}$

If $n$ is even, then we have the case for even $n$ :

$\frac{(2k-i)(2k-i+1)}{2} \mod {2k} = -(\frac{i}{2})(1-i)$

We wanted to see when it is divisible by $m=2k$ so we set:

$-(\frac{i}{2})(1-i) = 0 \Rightarrow i= 0,1$

Doing this to the case when $n$ is odd gives the same result, hence, the conclusion is:

$S_{ jn, jn-1} \equiv 0 \pmod { n}$ for odd $n$

$S_{ 2jn, 2jn-1} \equiv 0 \pmod { n }$ for even $n$

We can use this to find probabilities of $S_n \equiv 0 \pmod n$ , by finding how much of $S_n$ is divisible by $n$ in the range $n \in [1,120]$ :

All numbers $n$ such that $S_n$ is divisible by 2 are: - $P(2) = \frac{S_{4j = 120} + S{4j-1=120}}{120} = \frac{30}{60} = \frac{1}{2}$

All numbers $n$ such that $S_n$ is divisible by 3 are: - $P(3) = \frac{S_{3j = 120} + S{3j-1=120}}{120} = \frac{80}{120} = \frac{2}{3}$

All numbers $n$ such that $S_n$ is divisible by 4 are: - $P(4) = \frac{S_{8j = 120} + S{8j-1=120}}{120} = \frac{1}{4}$

All numbers $n$ such that $S_n$ is divisible by 5 are: - $P(5) = \frac{S_{5j = 120} + S{5j-1=120}}{120} = \frac{24}{60} = \frac{2}{5}$

It can be seen that $P(4)$ is the lowest probability. Therefore, $\boxed{4}$ is least divisible by $S_n$ for $n \in [1,120]$

NOTE: This isn't an explanation, just a program.

Program written in Crystal to illustrate results:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def triangle(n)
  n * (n + 1) / 2
end

# Outputs the amount of triangle numbers between 1 and 120
# that are divisible by 2, 3, 4 and 5 respectively.
puts (1..120).select { |a| (triangle(a) % 2).zero? }.size # => 60
puts (1..120).select { |a| (triangle(a) % 3).zero? }.size # => 80
puts (1..120).select { |a| (triangle(a) % 4).zero? }.size # => 30
puts (1..120).select { |a| (triangle(a) % 5).zero? }.size # => 48

Is using python to bruteforce a legitimate way to solve this problem? If so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

A = []
B = [0,0,0,0]

for i in range(120): #creates an array A containing all triangle numbers from 1 to 120
    A = A + [((i+1)**2)/2+(i+1)/2]


for i in range(120): #checks each number to see if it is divisible by 2,3,4 or 5 and true increments the according value of B
    for j in range(4):
        if A[i] % (j+2) == 0:
            B[j] += 1

print ("B =",B)

1

B is [60, 80, 30, 48]

where B[n] is the amount of numbers diviseble by n+2:

1

B [div by 2, div by 3,div by 4,div by 5]

And yes! The idea was most likeley to solve the problem and show a mathematical proof, but writing a bit of code also solves the problem, be it in another way.