15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think $n_{\max}=22$, and you can see math.stackexchange.com/questions/128371/… $\endgroup$ – math110 Sep 9 '13 at 7:36
  • $\begingroup$ @math110: Thank you, but I need a proof. $\endgroup$ – mathlove Sep 9 '13 at 7:39
  • $\begingroup$ 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. $\endgroup$ – Nikolaj-K Sep 9 '13 at 12:47
  • $\begingroup$ 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}}$. $\endgroup$ – Nikolaj-K Sep 9 '13 at 12:58
  • $\begingroup$ @NickKidman:Nice information! Thanks. $\endgroup$ – mathlove Sep 9 '13 at 15:10
16
+50
$\begingroup$

[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]
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Sep 16 '13 at 17:57
  • $\begingroup$ Wow! great work. Thank you very much. $\endgroup$ – mathlove Sep 17 '13 at 3:36
  • $\begingroup$ @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. $\endgroup$ – fedja Sep 18 '13 at 8:21
2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ @mathlove The answer to "Is this the max?" is "No" $\endgroup$ – Hagen von Eitzen Sep 9 '13 at 8:08
  • $\begingroup$ Now I updated. Your idea is a key, thanks! $\endgroup$ – mathlove Sep 9 '13 at 9:05

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.