Maths Olympiad Prep

Library / /747 of 860

Number theory Difficulty 5.5 AIME, harder Find the answer

For any integer nn, define n\lfloor n\rfloor as the greatest integer less than or equal to nn. For any positive integer nn, let f(n)=n+n2+n3++nn.f(n)=\lfloor n\rfloor+\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{n}{3}\right\rfloor+\cdots+\left\lfloor\frac{n}{n}\right\rfloor. For how many values of n,1n100n, 1 \leq n \leq 100, is f(n)f(n) odd?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

55 Notice that, for fixed a,n/aa,\lfloor n / a\rfloor counts the number of integers bb \in {1,2,,n}\{1,2, \ldots, n\} which are divisible by aa; hence, f(n)f(n) counts the number of pairs (a,b),a,b(a, b), a, b \in {1,2,,n}\{1,2, \ldots, n\} with bb divisible by aa. For any fixed bb, the number of such pairs is d(b)d(b) (the number of divisors of bb), so the total number of pairs f(n)f(n) equals d(1)+d(2)++d(n)d(1)+d(2)+\cdots+d(n). But d(b)d(b) is odd precisely when bb is a square, so f(n)f(n) is odd precisely when there are an odd number of squares in {1,2,,n}\{1,2, \ldots, n\}. This happens for 1n<4;9n<16;;81n<1001 \leq n<4 ; 9 \leq n<16 ; \ldots ; 81 \leq n<100. Adding these up gives 55 values of nn.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.