tag:blogger.com,1999:blog-3722233.post3911304736125799125..comments2023-01-30T06:53:58.825-06:00Comments on Computational Complexity: Solution to the reciprocals problemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-3722233.post-80517716653513703222011-12-27T15:44:35.539-06:002011-12-27T15:44:35.539-06:00My program reports 215067 solutions. It does math ...My program reports 215067 solutions. It does math on fractions, and solves the n=2 base case exactly.Lewnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26605447621998207082011-12-21T13:30:30.445-06:002011-12-21T13:30:30.445-06:00There cant be 10^40 solutions for 2011, obviously,...There cant be 10^40 solutions for 2011, obviously, 10s natural numbers smaller than 2011 is 2011^10 which is certainly smaller than 10^40.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24472302764609576652011-12-16T10:53:22.662-06:002011-12-16T10:53:22.662-06:00The number of solutions seems to be exponential in...The number of solutions seems to be exponential in n, and based on http://oeis.org/A051908, there are probably around 10^40 solutions for 2011.Sjoerd Visscherhttps://www.blogger.com/profile/10698430967044536619noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78455539331864014732011-12-14T19:36:27.534-06:002011-12-14T19:36:27.534-06:00http://oeis.org/A051882http://oeis.org/A051882Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33907842618380339182011-12-14T13:06:17.126-06:002011-12-14T13:06:17.126-06:00I dont know if my method, used for representing 20...I dont know if my method, used for representing 2008-2013 etc, can be used to generate the general theorem - the reduction method is more suited for that, however the reduction method is not of much use when one has to find solutions with fixed number of terms - the method I suggested has more flexibility here.<br /><br />Using reductions 20x+11, 2x+8 and 4x+6 can be used for 2011, but they do not work for 2013, 2015, 2017 etc, nor they seem to be enough to get the general theorem - none of the reductions can be applied. The HS student method also essentially uses reduction to 20x+11 but represents 100 then by hand, but for 2013 it would not work.<br /><br />How would you use your method to get 2013 in 10 steps? With the reductions you mention, you can get rid of power 2^k quickly, but to change from odd to even number you need more reductions (also note that to get different numbers, reduction 2x+9 is useless - so one cannot prove the Graham theorem with using reductions mentioned in the Claim - but some other will work). Also, once we get to the small numbers, we might get stuck, but with more reductions (those presumably used in proof of Graham thm) one might get this to always work, albeit with number of elements used left undetermined.<br /><br />On a more constructive note, the question how to find all solutions perhaps can be semi-efficiently answered on a computer (at least for representing numbers of order several thousands), by generating all sequences of given length that have sum of reciprocials equal to 1. <br /><br />So my question is the following: given k, how can one generate all k-typles of (not necessarily different) natural numbers whose reciprocials sum to 1? What is asymptotic of f(k) - number of such k-typles, also what is asymptotic of number of such k-typles that have distinct numbers? Let f(n,k) be number of k representations of n, what is asymptotic of f(n,k) - with non distinct numbers, and also with distinct numbers (it appears that distinct k-typles are far fewer, but how much so)? Are these things known in the literature? Seems to be a good introductory research project in say analytic number theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88235730303789045102011-12-14T09:30:29.415-06:002011-12-14T09:30:29.415-06:0023 is the smallest when allowing repeated numbers ...23 is the smallest when allowing repeated numbers it seems.<br /><br />I did not see solutions posted yet with very many numbers. Here's one with 19 numbers: 4,6,8,9,12,18,24,27,32,36,48,81,96,128,162,216,288,384,432Sjoerd Visscherhttps://www.blogger.com/profile/10698430967044536619noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50608005888738348572011-12-14T09:23:21.856-06:002011-12-14T09:23:21.856-06:00Looking at my solutions, I'd guessed that :-)....Looking at my solutions, I'd guessed that :-).stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17682213862581281192011-12-14T09:20:33.210-06:002011-12-14T09:20:33.210-06:00Stuart- After seeing your post I re-looked at Rona...Stuart- After seeing your post I re-looked at Ronald Graham's paper- he says all n \ge 78 BUT he insists<br />on DISTINCT numbers.<br /><br />Sorry for the confusion, and good luck with 2011!<br />(thats 2011 EXCITEMENT, not 2011 factorial.<br /><br />)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7016014692161984462011-12-14T09:07:01.991-06:002011-12-14T09:07:01.991-06:00Bill,
I've written some code, and while I hav...Bill,<br /><br />I've written some code, and while I haven't tackled 2011 with it yet, I have tackled 77. Here are my solutions for this "unsolvable" problem:<br /><br /><br />[2,9,12,12,12,12,18]<br />[2,10,10,10,15,15,15]<br />[3,4,4,11,22,33]<br />[3,4,4,12,18,36]<br />[3,4,5,5,60]<br />[3,4,6,16,16,16,16]<br />[3,4,8,8,18,18,18]<br />[3,5,5,10,18,18,18]<br />[3,5,5,12,12,20,20]<br />[3,6,6,6,14,21,21]<br />[3,6,6,6,16,16,24]<br />[3,10,10,10,10,10,12,12]<br />[4,4,4,15,15,15,20]<br />[4,4,5,8,12,20,24]<br />[4,4,5,10,12,12,30]<br />[4,5,5,6,12,15,30]<br />[4,6,6,6,6,21,28]<br />[4,6,6,10,12,12,12,15]<br />[4,6,8,8,9,12,12,18]<br />[4,6,8,9,9,9,16,16]<br />[4,6,9,9,9,10,10,20]<br />[5,5,5,5,9,18,30]<br />[5,5,6,6,6,14,35]<br />[5,5,6,9,10,12,12,18]<br />[5,6,6,6,12,12,15,15]<br />[5,6,6,8,8,12,12,20]<br />[6,6,6,7,7,12,12,21]<br />[6,6,6,8,9,9,9,24]stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1508353681137134402011-12-14T08:51:58.075-06:002011-12-14T08:51:58.075-06:00Anon who debates if my method was more `systematic...Anon who debates if my method was more `systematic' <br />GOOD POINT. What I really meant was that my way<br />(and ironically even more so with YOUR 2x+8, 2x+9 method)<br />can be used to show that EVERY sufficiently large number<br />can be written as a sum whose recip-sum is 1, while<br />the method you used I did not think could be used to prove that general theorem.<br /><br />Can your method be used to prove the general theorem?<br /><br />Anon who wants to know about how I got (a), (b), (c).<br />I had the notion of coolness and looked for a way<br />to get large numbers as quick as possible.<br />The observation that 1/2 + 1/4 + 1/5 = 19/20<br />was key for the 20x+11 one.<br /><br />Anon who wants to know about Sam Z's `divide by 20'<br />trick- realize that it did not have to work.<br />He GUESSED (common on math competitions) that if<br />the remaining 7 numbers were div by 20 then there<br />would be a solution, and it reduced the search<br />space so much that he was able to find a solution.<br />On a diff problem he would have been wrong- there might<br />not have been such a solution.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71399872648271168242011-12-14T08:27:58.047-06:002011-12-14T08:27:58.047-06:00A brute force solution, using only numbers with a ...A brute force solution, using only numbers with a maximum prime factor of 11, found plenty of solutions with distinct numbers. The first one was 2,3,7,70,324,360,405,840.Sjoerd Visscherhttps://www.blogger.com/profile/10698430967044536619noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74162571403842343752011-12-14T07:33:05.741-06:002011-12-14T07:33:05.741-06:00I have two questions to your solutions paper.
1. ...I have two questions to your solutions paper.<br /><br />1. Could you elaborate how you found parts (a), (b), and (c) in your "coolness-lemma"?<br /><br />2. How does "If all are divisible by 20 ..." in Sam Zbarsky's solution come about? (Does it follow from the preceding assumption or is it just a guess?)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71173875772610399372011-12-14T07:32:56.430-06:002011-12-14T07:32:56.430-06:00As an anon who send you solution, I expected my fu...As an anon who send you solution, I expected my full comment would be unblocked on wednesday; though half of my comment is in the solution, the other half, that shows a method that can be used to quickly solve such problem for other numbers and gives solution for years 2008-2013, is missing (as the end of the comment is present, I suppose the whole comment did get to you; btw I am the same anon who suggested 2x+8 2x+9 etc reductions, O(log(n)) terms are enough to represent n for n sufficiently large, 2297 and 2009 examples, 7 representation of 2011 - which you somewhat dismiss as "different problem" as it were not clear that it wasn't the solution to what was asked.)<br /><br />I fail to see how your method is systematic - it uses reductions like 2x+8, but since you posed the problem, you had number of terms at your choice, so it is easier to do it whan you can choose the number of terms - for instance, when I tried to do reductions, I obtained 21 (and then said we were stuck), which can be 5 represented (21=3+6+6+6+6) and gives 13 or so representation of 2011. It's almost like posing an instance of NP complete problem starting from the solution, and than claiming that it was found systematically.<br /><br />Also, Eppstein's use of "advanced math" consists of using Sylvester sequence, but one can try to start with any of the many similar sequences and tinker with it (like the one that sums to 1957 or some other I used - there is nothing special in Sylvester sequence except that is fastest growing and that was pointed out by another commenter; its hardly advanced math plus it won't help for some other nearby "years"). Eppstein pretty much tinkers with it in the similar way I did, and this tinkering has some method in it (sadly, part in which I illustrate how this can be quickly done is missing/witheld).<br /><br />The HS solution is ingenious and uses a somewhat different idea, so I disagree with your assessment of the similarity/difference in the methods used.<br /><br />As for my "method" (which is closest to the one used by Eppstein, but more general, as it does not need to start with Sylvester sequence), it consists in the following:<br />* Find a short "base" sequence of reciprocials summing to one, that adds to something less than 2000. This does not need to be Sylvester sequence, but can be constructed in similar, albeit more general way - one gets it by extending a known sequence of reciprocials summing to one, say a1..ak, by replacing ak by (c+a_k), (c+ak)a_k/c, where c is divisor of a_k (this was used in my method to get what I call "base" sequences, several of which I use, though it was not explained in my blocked comment)<br />*starting from the "base" sequence, we then see how much we miss to get to our target number, and how many extra numbers have to be used. Then we combine two of the smaller terms in the "base sequence" and replace them with two short sequences of reciprocials adding to 1 - say if we have 3 and 7 as members of "base" sequence, and 4 extra numbers to spend, we look for 3 representations of numbers a and b, which give sum of 3a+7b instead of 3+7 (or 4 and 2 representations) - we know that 3 representable numbers are 9, 10, 11, only 2 representable is 4, and 4 representable include 17, 18, 29 etc - and tinker with it, using congruences. If this can't be done, use different "base" sequence. To show that this method is systematic, I produced solutions for 2008-2013 in the time I was typing i.e relatively quickly (though it took some time to think up the method, as I had fun with this problem for a few hours total during which I also commented).<br /><br />Perhaps I am wrong and you have a better systematic way, using theorems as you say, to get solutions. How would your method then produce a 10 representation for 2013 or 2018, for instance? Can you do it quickly, as you say your method "required very little hand calculation"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9077973615530398972011-12-14T03:19:03.041-06:002011-12-14T03:19:03.041-06:002, 3, 16, 24, 40, 72, 90, 180, 288, 432, 864
2, 4,...2, 3, 16, 24, 40, 72, 90, 180, 288, 432, 864<br />2, 4, 9, 16, 24, 72, 120, 180, 288, 432, 864<br />2, 3, 16, 24, 50, 60, 72, 200, 288, 432, 864Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63538912530625047382011-12-14T02:34:39.883-06:002011-12-14T02:34:39.883-06:00There are a lot of solutions with all terms distin...There are a lot of solutions with all terms distinct. Here are just the ones a quick program I hacked together (no hand calculation this time!) found with lcm(solution)=960:<br /><br />1/2 + 1/3 + 1/16 + 1/24 + 1/30 + 1/80 + 1/96 + 1/320 + 1/480 + 1/960<br />1/2 + 1/4 + 1/8 + 1/15 + 1/30 + 1/80 + 1/192 + 1/240 + 1/480 + 1/960<br />1/3 + 1/4 + 1/5 + 1/8 + 1/15 + 1/96 + 1/120 + 1/320 + 1/480 + 1/960D. Eppsteinhttps://www.blogger.com/profile/11923501729858669855noreply@blogger.com