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
SUMMARY

The discussion focuses on the sum of the harmonic series for positive integers, specifically the expression $\displaystyle\sum_{m=1}^n \frac{1}{m}$ represented as $\dfrac{p_n}{q_n}$, where $p_n$ and $q_n$ are coprime integers. The main objective is to identify all integers $n$ for which 5 does not divide $q_n$. This problem is derived from Problem B-3 of the 1997 William Lowell Putnam Mathematical Competition and remains unsolved in the forum.

PREREQUISITES
  • Understanding of harmonic series and its properties
  • Knowledge of coprime integers and their significance in number theory
  • Familiarity with mathematical notation and summation
  • Basic principles of divisibility, particularly concerning prime numbers
NEXT STEPS
  • Research the properties of harmonic numbers and their representations
  • Study the concept of coprimality in number theory
  • Explore the implications of divisibility by prime numbers in fractions
  • Investigate solutions to similar problems from the William Lowell Putnam Mathematical Competition
USEFUL FOR

Mathematicians, students preparing for mathematical competitions, and anyone interested in advanced number theory and harmonic series analysis.

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 ·
Replies
1
Views
5K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
1
Views
2K
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K