Maths Olympiad Prep

Library / /745 of 860

Number theory Difficulty 5.5 AIME, harder Find the answer

Let mm be a positive integer. Let d(n)d(n) denote the number of divisors of nn, and define the function F(x)=n=1105md(n)nxF(x)=\sum_{n=1}^{105^{m}} \frac{d(n)}{n^{x}}. Define the numbers a(n)a(n) to be the positive integers for which F(x)2=n=11052ma(n)nxF(x)^{2}=\sum_{n=1}^{105^{2 m}} \frac{a(n)}{n^{x}} for all real xx. Express a(105m)a\left(105^{m}\right) in terms of mm.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The denominator of a term in the expansion of F(x)2F(x)^{2} is equal to nxn^{x} if and only if it is a product of two terms of FF of the form d(n/k)(n/k)x\frac{d(n / k)}{(n / k)^{x}} and d(k)kx\frac{d(k)}{k^{x}} for some divisor kk of nn. Thus a(105m)=k105md(k)d(105mk)a\left(105^{m}\right)=\sum_{k \mid 105^{m}} d(k) d\left(\frac{105^{m}}{k}\right). We can write k=3a5b7ck=3^{a} 5^{b} 7^{c} with a,b,cma, b, c \leq m for any divisor kk of 105m105^{m}, and in this case d(k)=(a+1)(b+1)(c+1)d(k)=(a+1)(b+1)(c+1). Thus the sum becomes 0a,b,cm(a+1)(b+1)(c+1)(ma+1)(mb+1)(mc+1)\sum_{0 \leq a, b, c \leq m}(a+1)(b+1)(c+1)(m-a+1)(m-b+1)(m-c+1). For a fixed bb and cc, we can factor out (b+1)(c+1)(mb+1)(mc+1)(b+1)(c+1)(m-b+1)(m-c+1) from the terms having this bb and cc and find that the sum is equal to a(105m)=0b,cm(b+1)(c+1)(mb+1)(mc+1)(a=1m+1a(ma+2))=0b,cm(b+1)(c+1)(mb+1)(mc+1)((m+2)(m+1)(m+2)2(m+1)(m+2)(2m+3)6)=0b,cm(b+1)(c+1)(mb+1)(mc+1)((3m+62m3)(m+1)(m+2)6)=0b,cm(b+1)(c+1)(mb+1)(mc+1)(m+33)a\left(105^{m}\right) =\sum_{0 \leq b, c \leq m}(b+1)(c+1)(m-b+1)(m-c+1)\left(\sum_{a=1}^{m+1} a(m-a+2)\right) =\sum_{0 \leq b, c \leq m}(b+1)(c+1)(m-b+1)(m-c+1)\left((m+2) \frac{(m+1)(m+2)}{2}-\frac{(m+1)(m+2)(2 m+3)}{6}\right) =\sum_{0 \leq b, c \leq m}(b+1)(c+1)(m-b+1)(m-c+1)\left(\frac{(3 m+6-2 m-3)(m+1)(m+2)}{6}\right) =\sum_{0 \leq b, c \leq m}(b+1)(c+1)(m-b+1)(m-c+1)\binom{m+3}{3}. Fixing cc and factoring out terms again, we find by a similar argument that a(105m)=(m+33)3a\left(105^{m}\right)=\binom{m+3}{3}^{3}.

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.