From rusin@shavano.math.niu.edu Thu Jun 17 23:41:04 CDT 1999 Article: 257402 of sci.math Path: news.math.niu.edu!rusin From: rusin@shavano.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Help with large numbers? Date: 16 Jun 1999 20:28:49 GMT Organization: Northern Illinois Univ., Dept. of Mathematical Sciences Lines: 195 Message-ID: <7k91e1$342$1@gannett.math.niu.edu> References: <7k87qg$s5t$1@starburst.uk.insnet.net> NNTP-Posting-Host: shavano.math.niu.edu X-Trace: gannett.math.niu.edu 929564929 3202 131.156.3.109 (16 Jun 1999 20:28:49 GMT) X-Complaints-To: news@math.niu.edu NNTP-Posting-Date: 16 Jun 1999 20:28:49 GMT Xref: news.math.niu.edu sci.math:257402 In article <7k87qg$s5t$1@starburst.uk.insnet.net>, Ben Hinton wrote: >Is it possible to find/make an algorithm to find out the best possible sum >to make a specified large number? > >Example: > >Here is a typical number I have to deal with - 169041087053108217. >I need to break this down into 3 or 4 separate numbers that will get me back >to the original number. > >eg: >n * x * y * z = largenumber or >x * x + z = largenumber or >x + y * z - n = largenumber > >you get the idea. I think so, but let's try to be more precise. Given an integer N you wish to find four integers x1, x2, x3, x4, three binary operations op1, op2, and op3 chosen from { +, *, -, / } (?), and a grouping of parentheses (there are five possible ones) so that one of these holds: N = x1 op1 (x2 op2 (x3 op3 x4)) N = x1 op1 ((x2 op2 x3) op3 x4) N = (x1 op1 (x2 op2 x3)) op3 x4 N = (x1 op1 x2) op2 (x3 op3 x4) N = ((x1 op1 x2) op2 x3) op3 x4 (You allowed for "three or four numbers" but we may subsume the 3-number case into the 4-number case by taking (3-number expression)+0. ) You give the extra stipulation that >Each of these smaller numbers pref needs to be 255 or less (but under 65535 >will do). (I'll bet you really mean "between 0 and 255 inclusive", right?) OK, well the first thing to observe is that you cannot do this in general, not if the x_i are to be under 256 and N is an arbitrary number as large as your 169041087053108217. The difficulty is that there are clearly at most 256^4 * 4^3 * 5 = 1374389534720 such expressions possible; you can also show that none of them will be larger than 255^4 = 4228250625, so your particular N is out. Of course if the x_i are allowed to be larger, you can get more N's, but even so, there will be a limit. And magnitude alone is not the only limiting factor; for example, with integers as large as L you can get L^4, but the next smaller integer will be 2*L^3. So you need to accept the fact that your problem may be insoluble. Now, to check whether it _is_ solvable for a particular N, "all" you need to do in principle is to do a case-by-case search: think of the formulas above as being at most 4^3*5 = 320 expressions in four variables x_i; set those expressions equal to N, and find the solution set. At worst, you need only search all 256^4 sets of possible solutions (x1,x2,x3,x4). Indeed, the problem isn't even as complicated as this suggests: using the commutative law and so on, we find that there are really only 176 distinct formulas, not 320. Moreover, if we allow permutions the variables, we see these 176 formulas reduce simply to these 93: x1+x2+x3+x4 x1+x2+x3-x4 x1+x2-x3-x4 x1-x2-x3-x4 x1*x2+x3+x4 x1*x2+x3-x4 x1*x2-x3-x4 x1+x2-x3*x4 x1-x2-x3*x4 x1*(x2+x3+x4) x1*(x2+x3-x4) x1*(x2-x3-x4) (x1+x2)*(x3+x4) (x1+x2)*(x3-x4) (x1-x2)*(x3-x4) x1*(x2*x3-x4) x1*(x2*x3+x4) x1*(x2-x3*x4) x1*x2+x3*x4 x1*x2-x3*x4 x1+x2*(x3+x4) x1+x2*(x3-x4) x1-x2*(x3+x4) x1*(x2+x3)-x4 x1*(x2-x3)-x4 x1*x2*(x3+x4) x1*x2*(x3-x4) x1*x2*x3+x4 x1*x2*x3-x4 x1-x2*x3*x4 x1*x2*x3*x4 x1*x2*x3/x4 and its reciprocal (x1+x2-x3)/x4 " " " (x1-x2-x3)/x4 " " " (x1+x2+x3)/x4 " " " (x1*x2-x3)/x4 " " " (x1-x2*x3)/x4 " " " (x1+x2*x3)/x4 " " " (x1+x2)*x3/x4 " " " (x1-x2)*x3/x4 " " " (x1/x2-x3)/x4 " " " (x1-x2/x3)/x4 " " " (x1+x2/x3)/x4 " " " (x1-x2)/(x3*x4) " " " (x1+x2)/(x3*x4) " " " (x1-x2)/(x3+x4) " " " (x1+x2)/(x3+x4) (it is its own reciprocal) (x1-x2)/(x3-x4) (") (x1*x2)/(x3*x4) (") x1+x2+x3/x4 x1+x2-x3/x4 x1-x2+x3/x4 x1-x2-x3/x4 x1/x2-(x3+x4) (x1*x2)+x3/x4 (x1*x2)-x3/x4 x1/x2-(x3*x4) (x1*x2)/x3+x4 (x1*x2)/x3-x4 x1-(x2*x3)/x4 (x1+x2)/x3+x4 (x1+x2)/x3-x4 (x1-x2)/x3+x4 (x1-x2)/x3-x4 x1-(x2+x3)/x4 (x1+x2/x3)*x4 (x1-x2/x3)*x4 (x1/x2-x3)*x4 x1+x2/x3/x4 x1-x2/x3/x4 x1/x2/x3-x4 x1/x2+x3/x4 x1/x2-x3/x4 x1+x2/(x3+x4) x1-x2/(x3+x4) x1/(x2+x3)-x4 x1+x2/(x3-x4) x1/(x2-x3)-x4 So now your question has become 93 questions: given an integer N, are there four integers x_i in {0, 1, ..., 255 (or 65535)} for which x1+x2+x3+x4 = N? x1+x2+x3-x4 = N? ... x1/(x2-x3)-x4 = N? Many of these problems are rather trivially dispensed with on the basis of magnitude: no expression without "*" can be larger than 4*255 (respectively 4*65535) in absolute value. With a little work you can convince yourself that with only one "*" you cannot exceed 4*65535^2, so you need two or three "*"'s (and three "*"'s simply asks for a factorization of N into three small factors, not possible for your particular N). Indeed, the two "*"'s must appear together, that is, formulas such as x1*x2 + x3*x4 will never give values larger than 2*65535^2. This leaves about a dozen remaining formulas to try. We can exclude a few more containing terms of the form (x-y) since we are allowed to choose values of our variables at will and so may replace these with simply x or -y. Likewise we may toss expressions of the form " + x/y " since we are trying to obtain integer values, which requires y divide x, and so we may simply take a smaller x and take y=1. We may exclude formulas such as x1 - x2*x3*x4 or x1*(x2 - x3*x4) whose only positive values are clearly at most 65525^2. So in the end, the only formulas which can give values larger than about 4*65525^2 are x1*x2*x3*x4 x1*x2*(x3+x4) x1*(x2*x3 - x4) x1*(x2*x3 + x4) x1*x2*x3 + x4 x1*x2*x3 - x4 Except for the first, all these formulas take on values no larger than 2*65535^3, and so do not apply to your particular value of N. The first doesn't apply either, as your N has the prime factor 905979719. For N between 4*65535^2 and 2*65535^3 there are as many as six formulas to check. Four of them insist that x1 be a small factor of N; the possible values of x1 (if any) are easily found, reducing this to a 3-variable problem. For the other two formulas I see no solution significantly better than testing the prime factorization of every candidate value N +- x4 (x4=0, 1, ..., 65535) in turn, looking for one which splits into three small factors. The algebra behind all these formulas is all very similar to that for a parlour game called "Krypto", which I undertook to analyze once; see http://www.math.niu.edu/~rusin/uses-math/games/krypto/analysis In Krypto we use 5-number expressions, not 4, and so must deal with 500 formulas, not 92. We are actually given the 5 numbers, rather than having to search for them, but that does not permit us to collapse e.g. x-y to x. All the numbers are significantly smaller than yours, which means we can't exclude formulas on the basis of maximum magnitude, but it does mean a brute-force loop would go much more quickly! dave