15

What is the max of $n$ such that $$\sum_{i=1}^n\frac{1}{a_i}=1$$ where $a_{i}\ (i=1,2,\cdots,n)$ are integers which satisfy $2\le a_1\lt a_2\lt\cdots\lt a_n\le 99$ ?

Also, I need how to prove that the $n$ you get is the maximum.

My approach:

I'm going to represent $\sum_{i=1}^n\frac{1}{a_i}$ as $(a_1,a_2,\cdots,a_n).$

$(2,3,6)\rightarrow(4,5,7,9, 12, 15,18,30,42,45,90)$ $\rightarrow(8,9,10, 12, 14, 15, 16, 18,22,27, 30, 35, 40, 42, 45, 48, 54, 56, 60, 72, 90, 99)$

(here I used $(3)=(4,12), (6)=(7,42)$ etc.)

This is the $n=22$ case.

Update: I've just got the following $n=42$ case. I don't know if this is the max.

$(8,9,10, 12, 14, 15, 16, 18,22,27, 30, 35, 40, 42, 45, 48, 54, 56, 60, 72, 90, 99)\rightarrow(15,17,20,21,22,26,27,30,32,33,34,35,36,38,39,40,42,44,45,48,50,52,54,55,56,60,63,66,70,75,76,77,78,80,84,85,88,90,91,95,96,99)$

Here I used $(10)=(17,34,85), (14)=(28,44,77)$ etc.

Update 2 : I've just got another $n=42$ case.

$(17,18,20,21,22,24,26,27,32,33,34,35,36,38,39,40,42,44,45,48,50,52,54,55,56,60,63,66,70,72,75,76,77,78,80,84,85,88,91,95,96,99)$

Here I used $(15,30,90)=(18,24,72)$.

Update 3 : I crossposted to MO.

https://mathoverflow.net/questions/142300/what-is-the-max-of-n-such-that-sum-i-1n-frac1a-i-1-where-2-le-a-1-l

Community
  • 1
mathlove
  • 139,939
  • I think $n_{\max}=22$, and you can see http://math.stackexchange.com/questions/128371/writing-1-in-form-of-frac1t-1-cdots-frac1t-n?lq=1 – math110 Sep 09 '13 at 07:36
  • @math110: Thank you, but I need a proof. – mathlove Sep 09 '13 at 07:39
  • I generated all transformation rules with up to 4 numbers $(a)=(b,c,d,e)$ and among these there are 35 which never pop up on the right hand side: 23,25,29,31,37,41,42,43,46,47,49,51,53,58,59,61,62,64,67,68,69,71,73,74,79,81,82,83,86,87,89,92,93,94,97,98. There is only one way to partition the 1 with 3 numbers (namely what you did $(1)=(2,3,6)$) but six with 4 numbers (e.g. $(1)=(2,4,5,20)$). The biggest number you can partition in two is 42, the biggest you can partition in three is 28 and the biggest number you can partition is 20 via $(20)=(70,78,84,91)$. None for your presented way up to 5. – Nikolaj-K Sep 09 '13 at 12:47
  • The last sentence was ment to say, even if you go up partitions into five different numbers, there are none left so that you can get a better result with your current string as an input. I could also add that up to partitions into 4 numbers, there are 954 such transformations in total. I did this brute force btw. In Mathematica, Subset[Range[2,99],{n}] gives you the subsets of $2,3,\dots,99$ with $n$ elements ${a_1,a_2,\dots,a_n}$ and then I just checked which map to an integer under $(a_i)\mapsto \frac{1}{\sum_i\frac{1}{a_i}}$. – Nikolaj-K Sep 09 '13 at 12:58
  • @NickKidman:Nice information! Thanks. – mathlove Sep 09 '13 at 15:10
  • Here is the list: http://pastebin.com/6sXEai7T. The code is a one-liner "{f,#}&/@Select[Subsets[Range[2,99],{n}],IntegerQ[f]&]" with n as you choose and f being "1/Plus@@(1/# &/@#)". – Nikolaj-K Sep 09 '13 at 16:05
  • @NickKidman: Thank you very much. – mathlove Sep 09 '13 at 16:51

2 Answers2

16

[EDITED to include other prime powers and give the list of 27 maximal solutions]

The maximum is $42$, attained in $27$ ways (listed below); there are $566$ runners-up with $41$, and then $6747$ with $40$, another $52078$ with $39$, "etc.".

The counts are obtained by dynamical programming. We simplify the computation by checking that the $a_i$ can include no multiple of a prime power greater than $27$, and if multiples of $11$, $13$, $16$, $17$, $19$, $25$, or $27$ appear then they must combine to remove that factor from the denominator, which can only be done in $46,\phantom. 9,\phantom. 7,\phantom., 1, \phantom. 2,\phantom. 1,\phantom. 1$ ways respectively (the last four are $(17,34,85)$, $(19,57,76)$ or $(38,76,95)$, $(50,75)$, and $(25,54)$ respectively; $23$ does not occur). That brings the denominator down to $D = 2^3 3^2 5 \phantom. 7 = 2520$, small enough to make a table of the number of times each pair of integers arises as $(n, D\sum_{i=1}^n 1/a_i)$ with $\sum_i 1/a_i \leq 1$, and at the end extract the counts for $(n,D)$.

This approach does not immediately give the list of $27$ maximal solutions, but it can be modified to compute this list instead: at each stage, instead of recording the number of representations of each fraction, keep track of the representation(s) with the largest number of terms. The list of $42$'s is follows, in lexicographical order; each uses the prime 17, and all use 99 except for two which have $\max_i a_i = 96$.

[12, 17, 21, 22, 24, 26, 27, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 48, 50, 52, 54, 55, 56, 60, 63, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[13, 17, 18, 21, 22, 24, 26, 27, 32, 33, 34, 35, 38, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 63, 65, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[13, 17, 18, 22, 24, 26, 27, 28, 32, 33, 34, 35, 36, 38, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 65, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[13, 17, 20, 21, 22, 24, 26, 27, 32, 33, 34, 35, 36, 38, 40, 42, 44, 48, 50, 52, 54, 55, 56, 60, 63, 65, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[13, 17, 20, 21, 22, 24, 26, 30, 32, 33, 34, 35, 36, 38, 40, 42, 44, 45, 48, 50, 52, 55, 56, 60, 63, 65, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[13, 17, 20, 21, 22, 26, 27, 30, 32, 33, 34, 35, 36, 38, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 63, 65, 66, 70, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[13, 17, 20, 21, 24, 26, 27, 30, 32, 33, 34, 35, 36, 38, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 63, 65, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96]
[13, 17, 20, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 38, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 65, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[14, 17, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 44, 48, 50, 52, 54, 55, 56, 60, 63, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[15, 17, 18, 21, 22, 24, 26, 27, 32, 33, 34, 35, 38, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 63, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[15, 17, 18, 22, 24, 26, 27, 28, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[15, 17, 20, 21, 22, 24, 26, 27, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 48, 50, 52, 54, 55, 56, 60, 63, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[15, 17, 20, 21, 22, 24, 26, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 48, 50, 52, 55, 56, 60, 63, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[15, 17, 20, 21, 22, 26, 27, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 63, 66, 70, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[15, 17, 20, 21, 24, 26, 27, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 63, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96]
[15, 17, 20, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 38, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[17, 18, 19, 21, 22, 24, 26, 27, 30, 32, 33, 34, 35, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 57, 60, 63, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 96, 99]
[17, 18, 19, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 57, 60, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 96, 99]
[17, 18, 20, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34, 38, 39, 40, 44, 45, 48, 50, 52, 54, 55, 56, 60, 63, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[17, 18, 20, 21, 22, 24, 26, 27, 30, 32, 33, 34, 35, 38, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 63, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[17, 18, 20, 21, 22, 24, 26, 27, 30, 32, 33, 34, 35, 38, 39, 40, 42, 44, 45, 48, 50, 54, 55, 56, 60, 63, 65, 66, 70, 72, 75, 76, 77, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[17, 18, 20, 21, 22, 24, 26, 27, 30, 32, 33, 34, 36, 38, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[17, 18, 20, 21, 22, 24, 26, 27, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 63, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 91, 95, 96, 99]
[17, 18, 20, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[17, 18, 20, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 48, 50, 54, 55, 56, 60, 65, 66, 70, 72, 75, 76, 77, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[17, 18, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 48, 50, 52, 54, 55, 56, 60, 66, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 95, 96, 99]
[17, 19, 20, 21, 22, 24, 26, 27, 30, 32, 33, 34, 35, 36, 39, 40, 42, 44, 48, 50, 52, 54, 55, 56, 57, 60, 63, 66, 70, 72, 75, 76, 77, 78, 80, 84, 85, 88, 90, 91, 96, 99]
Noam D. Elkies
  • 25,917
  • 1
  • 64
  • 82
  • Along the same lines, can't use $64$ or $81$, and if we use multiples of $32$ or $27$ then $32$ must go with $96$ and $27$ must go with $54$. This makes the computation even smaller. – Noam D. Elkies Sep 16 '13 at 17:57
  • Wow! great work. Thank you very much. – mathlove Sep 17 '13 at 03:36
  • @Noam D. Eikes One can also notice that if $27$ and $54$ are present, then at least one multiple of $9$ that is $36$ or higher must be missing, which makes the proof of the impossibility to get 43 or more numbers almost (but not quite yet) within the reach of a human equipped with nothing but pen, paper, and the knowledge of some 42 number example (allowing to tell various relevant things about long sums of inverses by comparison rather than by direct addition). However, what I still wonder most is if we can see it with almost no computation at all. Not that I have any good idea yet. – fedja Sep 18 '13 at 08:21
2

Your $22$ is not the max because $(12)=(19,57,95)$. And after that $(9)=(12,36)$.

Hagen von Eitzen
  • 374,180