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

  • Thread starter Thread starter Ackbach
  • Start date Start date
  • Tags Tags
    2016
Click For Summary
The discussion focuses on the sum of the harmonic series for positive integers, expressed as the fraction $\sum_{m=1}^n \frac{1}{m} = \frac{p_n}{q_n}$, where $p_n$ and $q_n$ are coprime integers. Participants are tasked with identifying values of $n$ for which 5 does not divide $q_n$. The problem is derived from the 1997 William Lowell Putnam Mathematical Competition, highlighting its mathematical significance. Despite the challenge, no solutions were provided by the forum members for this week's Problem of the Week. The solution is credited to Kiran Kedlaya and his team.
Ackbach
Gold Member
MHB
Messages
4,148
Reaction score
94
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!
 
Physics news on Phys.org
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:

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.
 

Similar threads

Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K