## The Vault: My favourite puzzle

Having spent nine days in Hamburg at a maths conference, I return to present what is to date my favourite ever maths problem. From the Tournament of the Towns:

Let n be a positive integer. Consider the largest odd factor of each of the numbers n+1, n+2, …, 2n. Prove that their sum is n2.

When I first saw this problem, I looked at it in disbelief. On the face of it, the result linking odd factors and square numbers is completely outrageous. I knew I had to try it immediately…

So we have n odd factors. After playing around with small cases, we get a sense of what’s really going on.

n = 2 :

3 is the largest odd factor of 3

1 is the largest odd factor of 4

3 + 1 = 4, which is 22.

n = 5:

3 is the largest odd factor of 6

7 is the largest odd factor of 7

1 is the largest odd factor of 8

9 is the largest odd factor of 9

5 is the largest odd factor of 10

3 + 7 + 1 + 9 + 5 = 25, which is 52.

We notice that for some reason, all the odd factors in our sum are different – there is never a repeat. Further, in fact it looks like the odd factors in our sum are just the first n odd numbers. How can we prove this claim?

Well, what can we say about two different numbers with the same largest odd factor? By looking at their prime factors, we realise that the only difference in their prime decompositions will be the power of 2 that appears; all the odd primes must be identical in both numbers. For example, 3 is the largest odd factor of 6, 12 and 48.

6 = 2 x 3

12 = 2 x 2 x 3

48 = 2 x 2 x 2 x 2 x 3.

So if two numbers have the same largest odd factor, then one is at least double the other. But in the list n+1, n+2, …, 2n, the largest number (2n) is less than double the smallest (n+1). So it is impossible for two numbers in the list to have the same largest odd factor. Hence every odd factor in our final sum is different.

Exactly which odd factors appear then? The largest that appears is always 2n-1. But the list of the first n odd numbers is precisely

1, 3, 5, …, 2n-1.

Our final sum contains n different odd factors, the largest of which is 2n-1. But this means that our sum must just contain every odd number in the list above precisely once.

It remains to calculate 1 + 3 + 5 + … + (2n-1). But this is an arithmetic series, an is easily calculated:

1 + 3 + 5 + … + (2n-1) = n2

and this astonishing result is proven.