# Subsequence and integers as a sum of $\frac{1}{n}$

For all $M \in \mathbb{Z}$, is there a finite sequence of positive integers (not necessarily distinct) $(n_i)_{i \in I}$, s.t. $\sum_{i \in I} \frac{1}{n_i} = M$, and there is no subsequence $(n_i)_{i \in J}$ of $(n_i)_{i \in I}$ such that $\sum_{i \in J} \frac{1}{n_i}$ is an integer ?

• One solution may be found by finding, $\sum_i \frac{1}{p_i}+\frac{1}{\prod_i p_i}=1$ where each $p_i>M$. – pallab1234 Jun 23 '15 at 12:01
• Previously posted to m.se, math.stackexchange.com/questions/1328872/… – Gerry Myerson Jun 23 '15 at 13:02
• Such partitions of $2$ and $3$ are e.g. $2 = \frac{1}{2} + \frac{1}{3} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{5} + \frac{1}{7} + \frac{1}{25} + \frac{1}{2100}$ and $3 = \frac{1}{2} + \frac{1}{3} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{5} + \frac{1}{5} + \frac{1}{5} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{16} + \frac{1}{153} + \frac{1}{85680}$. – Stefan Kohl Jun 24 '15 at 10:14
• Let's take a finite sequence of mutually prime positive integers $(r_i)_{i \in I}$. Lets define $q_i=\prod_{j \neq i} r_i$. Determine $d_i<r_i$, by solving $d_i q_i+1=0$ mod $r_i$. Then $\sum \frac{d_i}{r_i}+\frac{1}{\prod r_i}=M$ is an integer. No other sub-sequence sums up to an integer. This way roughly one needs $2k$ mutually prime numbers to get a integer near $k$. E.g., taking $(r_i)$ as consecutive primes I can generate any $M$ between $1$ and $100$. – pallab1234 Jun 24 '15 at 19:20
• The question is also interesting (perhaps more so) if one insists that the $n_i$ actually be distinct. It's not clear to me whether it's true any longer, though I'm guessing the answer is yes. – Greg Martin Jul 2 '15 at 6:28

Suppose you have a sequence $n_1,n_2,\ldots,n_k$ of pairwise relatively prime numbers. Put $q=n_1n_2\ldots n_k$. You put $q_i={q\over n_i}$ and find $d_i<n_i$ such that $d_iq_i+1=0$ mod $n_i$. This implies that $d_1q_1+d_2q_2+\ldots+d_nq_n+1=0\mathop{\rm mod}n_i$ for $i=1,2,\ldots,k$ hence $\mathop{\rm mod}q$. Dividing by $q$ we get some integer $$M={d_1\over n_1}+{d_2\over n_2}+\ldots+{d_k\over n_k}+{1\over q}$$.

So far this was your argument.

Now pick any $n_{k+1}$, $1<n_{k+1}<q$, relatively prime to every $n_i$ for $i\leq k$. Find $n_{k+2}<q$ such that $n_{k+1}n_{k+2}=1\mathop{\rm mod}q$. The numbers $n_{k+1}$ and $n_{k+2}$ may have a common factor but you may prevent that by choosing $n_{k+1}$ to be a prime bigger than $q/2$ (Edit: and such that $n_{k+1}^2\neq 1\mathop{\rm mod} q$, for example of the form $5r\pm 2$ if $5|q$, see comments by pallab1234 below). Put $q'=qn_{k+1}n_{k+2}=n_1n_2\ldots n_{k+2}$. When you find $d_i<n_i$ such that $d_iq'_i+1=0$ mod $n_i$ for $i=1,2,\ldots,{k+2}$ you see that those for $i\leq k$ didn't change. You obtain another integer $$M'={d_1\over n_1}+\ldots+ {d_k\over n_k}+{d_{k+1}\over n_{k+1}}+{d_{k+2}\over n_{k+2}}+{1\over q'}= M+\Delta$$ where $$\Delta={d_{k+1}\over n_{k+1}}+{d_{k+2}\over n_{k+2}}+{1\over q'}-{1\over q}= {d_{k+1}\over n_{k+1}}+{d_{k+2}\over n_{k+2}}+ {1\over q}\left({1\over n_{k+1}n_{k+2}}-1\right)$$ must be an integer. Clearly $\Delta<2$. On the other hand $$\Delta>{1\over n_{k+1}}+{1\over n_{k+2}}-{1\over q}>{1\over n_{k+2}}-{1\over q}$$ which is positive since $n_{k+2}<q$. Being an integer $\Delta=1$ hence $M'=M+1$.

Edit: deleted.

Edit2: Thus you may start with $n_1=3$ and $n_2=5$ for which you get $\displaystyle M={1\over 3}+{3\over 5}+{1\over 3\cdot 5}=1$ and go up to any positive integer you want.

• A start from $M=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}$ possibly would not work. But we can always start with bigger $n_i$'s and then this method of reasoning would definitely work. Nice proof though, thanks ! – pallab1234 Jul 3 '15 at 3:15
• @pallab1234 - oops, thanks for noticing. I will correct this in a moment. – Adam Przeździecki Jul 3 '15 at 8:54
• We need to make sure that $n_{k+1}^2 \neq 1$ mod $q$. That would guarantee $n_{k+1} \neq n_{k+2}$. Can we always get such a $n_{k+1}$ ? I guess that would be always possible. – pallab1234 Jul 5 '15 at 4:45
• This could be done by taking $n_{k+1}=5 r + 3$, given that one already has $n_2=5$. – pallab1234 Jul 5 '15 at 6:30
• @pallab1234 - my mistake again, thanks. BTW - this line of reasoning is good for theoretical argument, that we can always find a solution. But the numbers $n_k$, chosen this way, will grow extremely fast. If you need it for practical computations you probably do better checking consecutive primes as candidates for $n_{k+1}$. In another direction you may choose some constant $0<C<1$ and drop those candidates for which $d_{k+1}<Cn_{k+1}$ or $d_{k+2}<Cn_{k+2}$ to get $k<M/C$. – Adam Przeździecki Jul 5 '15 at 12:26