11
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – pallab1234 Jun 23 '15 at 12:01
  • 3
    $\begingroup$ Previously posted to m.se, math.stackexchange.com/questions/1328872/… $\endgroup$ – Gerry Myerson Jun 23 '15 at 13:02
  • $\begingroup$ 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}$. $\endgroup$ – Stefan Kohl Jun 24 '15 at 10:14
  • 1
    $\begingroup$ 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$. $\endgroup$ – pallab1234 Jun 24 '15 at 19:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Greg Martin Jul 2 '15 at 6:28
4
+50
$\begingroup$

You have answered your question in the comments, just construct your sequence inductively.

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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 ! $\endgroup$ – pallab1234 Jul 3 '15 at 3:15
  • $\begingroup$ @pallab1234 - oops, thanks for noticing. I will correct this in a moment. $\endgroup$ – Adam Przeździecki Jul 3 '15 at 8:54
  • 1
    $\begingroup$ 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. $\endgroup$ – pallab1234 Jul 5 '15 at 4:45
  • 1
    $\begingroup$ This could be done by taking $n_{k+1}=5 r + 3$, given that one already has $n_2=5$. $\endgroup$ – pallab1234 Jul 5 '15 at 6:30
  • $\begingroup$ @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$. $\endgroup$ – Adam Przeździecki Jul 5 '15 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.