What is the sum of a positive integer in fraction form?

[Ackbach]

Here is this week's POTW:

-----

For each positive integer $n$, write the sum $\displaystyle\sum_{m=1}^n \frac1m$ in the form $\dfrac{p_n}{q_n}$, where $p_n$ and $q_n$ are relatively prime positive integers. Determine all $n$ such that 5 does not divide $q_n$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 234 - Sep 21, 2016

This was Problem B-3 in the 1997 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

The only such $n$ are the numbers 1--4, 20--24, 100--104, and 120--124. For the proof let
\[H_n=\sum_{m=1}^n \frac{1}{m}\]
and introduce the auxiliary function
\[I_n=\sum_{1\leq m\leq n, (m,5)=1} \frac{1}{m}.\]
It is immediate (e.g., by induction) that $I_n\equiv 1,-1,1,0,0$ (mod $5$) for $n\equiv 1,2,3,4,5$ (mod 5) respectively, and moreover, we have the equality
\[\label{(*)}H_n= \sum_{m=0}^k \frac{1}{5^m} I_{\lfloor n/5^m \rfloor},\]
where $k=k(n)$ denotes the largest integer such that $5^k\leq n$. We wish to determine those $n$ such that the above sum has nonnegative 5--valuation. (By the 5--valuation of a number $a$ we mean the largest integer $v$ such that $a/5^v$ is an integer.)

If $\lfloor n/5^k \rfloor\leq 3$, then the last term in the above sum has 5--valuation $-k$, since $I_1$, $I_2$, $I_3$ each have valuation 0; on the other hand, all other terms must have 5--valuation strictly larger than $-k$. It follows that $H_n$ has 5--valuation exactly $-k$; in particular, $H_n$ has nonnegative 5--valuation in this case if and only if $k=0$, i.e., $n=1$, 2, or 3.

Suppose now that $\lfloor n/5^k \rfloor=4$. Then we must also have $20\leq \lfloor n/5^{k-1}\rfloor \leq 24$. The former condition implies that the last term of the above sum is $I_4/5^k=1/(12\cdot 5^{k-2})$, which has 5--valuation $-(k-2)$.

It is clear that $I_{20}\equiv I_{24}\equiv 0$ (mod 25); hence if $\lfloor n/5^{k-1}\rfloor$ equals 20 or 24, then the second--to--last term of the above sum (if it exists) has valuation at least $-(k-3)$. The third--to--last term (if it exists) is of the form $I_r/5^{k-2}$, so that the sum of the last term and the third to last term takes the form $(I_r+1/12)/5^{k-2}$. Since $I_r$ can be congruent only to 0,1, or -1 (mod 5), and $1/12\equiv 3$ (mod 5), we conclude that the sum of the last term and third--to--last term has valuation $-(k-2)$, while all other terms have valuation strictly higher. Hence $H_n$ has nonnegative 5--valuation in this case only when $k\leq 2$, leading to the values $n=4$ (arising from $k=0$), 20,24 (arising from $k=1$ and $\lfloor n/5^{k-1}\rfloor = 20$ and 24 resp.), 101, 102, 103, and 104 (arising from $k=2$, $\lfloor n/5^{k-1}\rfloor = 20$) and 120, 121, 122, 123, and 124 (arising from $k=2$, $\lfloor n/5^{k-1}\rfloor=24$).

Finally, suppose $\lfloor n/5^k \rfloor=4$ and $\lfloor n/5^{k-1} \rfloor=21$, 22, or 23. Then as before, the first condition implies that the last term of the sum in (*) has valuation $-(k-2)$, while the second condition implies that the second--to--last term in the same sum has valuation $-(k-1)$. Hence all terms in the sum (*) have 5--valuation strictly higher than $-(k-1)$, except for the second--to--last term, and therefore $H_n$ has 5--valuation $-(k-1)$ in this case. In particular, $H_n$ is integral (mod 5) in this case if and only if $k\leq 1$, which gives the additional values $n=21$, 22, and 23.