Re: find two numbers a,b, such that a+b=5432 & LCM[a,b]=223020
- To: mathgroup at smc.vnet.net
- Subject: [mg122162] Re: find two numbers a,b, such that a+b=5432 & LCM[a,b]=223020
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Mon, 17 Oct 2011 08:10:01 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- References: <j6e693$kef$1@smc.vnet.net> <201110050801.EAA07025@smc.vnet.net> <360851F3-7690-47A6-BC84-E9521100E6F4@mimuw.edu.pl> <A0A54467-5287-4372-9FA6-F0FD865B77D2@mimuw.edu.pl> <84B4CB1D-C8A7-4A5F-8303-9FEC113F7D16@mimuw.edu.pl> <1318773921.12784.YahooMailNeo@web43139.mail.sp1.yahoo.com> <201110162045.QAA19701@smc.vnet.net> <6371475F7C873A4CA2F9BBABC115837E0A5685CC@nycexch.local.atlanticphilanthropies.org>
Indeed, but there did not seem (to me) to be much point in sending a "brute-force" solution to someone who specifically asks for something other than a brute-force solution. Andrzej On 16 Oct 2011, at 23:47, Harvey P. Dale wrote: > Here's a simple brute-force method: > > Select[Range[5431],LCM[#,5432-#]==223020&] > > Best, > > Harvey > > -----Original Message----- > From: Andrzej Kozlowski [mailto:akoz at mimuw.edu.pl] > Sent: Sunday, October 16, 2011 4:46 PM > To: mathgroup at smc.vnet.net > Subject: [mg122155] Re: find two numbers a,b, such that a+b=5432 & > LCM[a,b]=223020 > > Well, I don't think Reduce can solve it "directly" but here is an easy > method that makes use of Reduce and a tiny bit of elementary number > theory to solve it. > > Let g denote the GCD of a and b. Then we know that a b = 223020 g > (from the well known relationship between GCD and LCM). Hence we need to > > solve the equation Reduce[{a + b == 5432, a b == 223020 g}, {a, > b}, Integers] for all possible GCD candidates of a and b. Since the GCD > of a and b is always a divisor of their sum a+b == 5432 we can > simply test all possible divisors (there are only 16). > > ls = Divisors[5432] > > {1,2,4,7,8,14,28,56,97,194,388,679,776,1358,2716,5432} > > (Reduce[{a + b == 5432, a*b == 223020*#1}, {a, b}, Integers] & ) > /@ ls > > {False, False, False, False, False, False, > (a == 1652 && b == 3780) || (a == 3780 && b == 1652), > False, > False, False, False, False, False, False, False, False} > > Thus we see that the only possibility is that one of the numbers is 1562 > > and the other 3780. > > Andrzej Kozlowski > > On 16 Oct 2011, at 16:05, dimitris anagnostou wrote: > >> Hello Mr Kozlowski . >> >> This is from a post of mine to MathGroup that it hasn't appeared yet. >> >> This is taken from the recent book (2010): " Mathematica: A > Problem-Centered Approach" by R. Hazrat. >> >> "The sum of two positive integers is 5432 and their least common > multiple is >> 223020. Find the numbers." >> >> A solution: >> >> Do[If[LCM[i, 5432 - i] == 223020, Print[i, " ", 5432 - i]], {i, > 1, 2718}] >> 1652 3780 >> >> I wonder if we can solve the system of equations: >> >> a+b==5432&&LCM[a,b]==223020 >> >> using codes that contain built in functions like Reduce. >> >> I guess this is not a trivial one because the so much powerful Reduce= > itself fails >> >> In[1]:= Reduce[{a + b == 5432, LCM[a, b] == 223020}, {a, = b}, > Integers] >> >> During evaluation of In[1]:= Reduce::nsmet:This system cannot be > solved with the methods available to Reduce. >> >> >> Out[1]= Reduce[{a + b == 5432, LCM[a, b] == 223020}, {a, = b}, > Integers] >> >> I would really appreciate your ideas. >> >> Best Regards >> >> Dimitris Anagnostou >> >> From: Andrzej Kozlowski <akoz at mimuw.edu.pl> >> To: dimitris anagnostou <dimmechan at yahoo.com> >> Cc: Bobby Treat <drBob at bigfoot.com>; Dr. Wolfgang Hintze > <weh at snafu.de>; "mathgroup at smc.vnet.net Steve" = <mathgroup at smc.vnet.net>; > > Peter Pein <petsie at dordos.net> >> Sent: Thursday, October 6, 2011 9:48 PM >> Subject: Re: Re: simplification >> >> >> On 6 Oct 2011, at 20:28, Andrzej Kozlowski wrote: >> >>> >>> On 6 Oct 2011, at 16:57, Andrzej Kozlowski wrote: >>> >>>> >>>> On 5 Oct 2011, at 10:01, Peter Pein wrote: >>>> >>>>> Am 04.10.2011 07:40, schrieb dimitris: >>>>>> Hello. >>>>>> >>>>>> Let >>>>>> >>>>>> o1 = 1 + Sqrt[15 + 2*Sqrt[35] + 2*Sqrt[6*(6 + Sqrt[35])]]; >>>>>> o2 = 1 + Sqrt[3] + Sqrt[5] + Sqrt[7]; >>>>>> >>>>>> o1 is equal to o2. >>>>>> >>>>>> o1 == o2 // FullSimplify >>>>>> True >>>>>> >>>>>> The question is how to make Mathematica to simplify o1 to o2. >>>>>> >>>>>> Thanks >>>>>> Dimitris >>>>>> >>>>> >>>>> With a lot of luck: >>>>> >>>>> In[1]:= o1 = 1 + Sqrt[15 + 2*Sqrt[35] + 2*Sqrt[6*(6 + > Sqrt[35])]]; >>>>> ext = Block[{x, poly = RootReduce[o1][[1]]}, >>>>> Sqrt[Cases[Union @@ Divisors[Abs[CoefficientList[poly[x], x]]], >>>>> 1 | _?PrimeQ, 1]]] >>>>> o2 = ((Rest[#1] / First[#1]) . ext & )[ >>>>> FindIntegerNullVector[Prepend[ext, -o1]]] >>>>> >>>>> Out[3]= {1, Sqrt[2], Sqrt[3], Sqrt[5], Sqrt[7], Sqrt[19], > Sqrt[31]} >>>>> >>>>> Out[4]= 1 + Sqrt[3] + Sqrt[5] + Sqrt[7] >>>>> >>>>> :-) >>>>> >>>> >>>> Neat, but from the Mathematical point of view the question was > posed "the wrong way round" in that o1 is mathematically "simpler" = than > 1 + Sqrt[3] + Sqrt[5] + Sqrt[7], since it is already expressed in = terms > of its minimal polynomial. Hence this is the "natural" or "easy" way = to > go: >>>> >>>> ToRadicals[RootReduce[1 + Sqrt[3] + Sqrt[5] + Sqrt[7]]] >>>> >>>> 1 + Sqrt[15 + 2*Sqrt[35] + 2*Sqrt[6*(6 + Sqrt[35])]] >>>> >>>> in other words, the algebraic "simplification" in this case is > exactly the opposite of, what might be called, the visual one. >>>> >>>> >>>> There is no natural or unique way to "decompose" algebraic numbers= > that are already reduced into sums etc, of "simpler" summands or = factors > > etc. Of course, if we already know an integer basis for an algebraic= > number field containing an algebraic number, than there are ways of > expressing it in terms of this basis - and this method is an example. >>>> >>>> Andrzej Kozlowski >>>> >>>> >>>> >>>> >>> >>> Let me correct myself here since I noticed that I did not write what > > I really meant ;-) >>> >>> What I mean was that the following is the simplest (algebraically)= > form of this algebraic number: >>> >>> In[80]:= RootReduce[1 + Sqrt[3] + Sqrt[5] + Sqrt[7]] >>> >>> Out[80]= Root[ >>> 1024 + 3584 #1 + 640 #1^2 - 1984 #1^3 - 48 #1^4 + 304 #1^5 - >>> 32 #1^6 - 8 #1^7 + #1^8 &, 8] >>> >>> (the same as above, but, of course, without the ToRadicals). > Mathematically equivalent statement is: >>> >>> MinimalPolynomial[RootReduce[1+Sqrt[3]+Sqrt[5]+Sqrt[7]],x] >>> 1024+3584 x+640 x^2-1984 x^3-48 x^4+304 x^5-32 x^6-8 x^7+x^8 >>> >>> The only simplification one can really make algorithmically with > algebraic numbers is what RootReduce does - essentially finding the > minimal polynomial. Mathematica also has an algorithm for converting= > some root objects to radicals but this is usually does not give the > visually simplest form. There is no algorithm that will discover the= > simples such form in general (indeed, most algebraic numbers can't be= > expressed in radicals at all). On the other hand, one can find the > minimal polynomial of any algebraic number: e.g. >>> >>> In[82]:= MinimalPolynomial[1 + Sqrt[3] + Sqrt[5] + Sqrt[7], x] >>> Out[82]= 1024 + 3584*x + 640*x^2 - 1984*x^3 - 48*x^4 + 304*x^5 -= > 32*x^6 - 8*x^7 + x^8 >>> >>> In[83]:= > MinimalPolynomial[1+Sqrt[15+2*Sqrt[35]+2*Sqrt[6*(6+Sqrt[35])]],x] >>> Out[83]= 1024+3584 x+640 x^2-1984 x^3-48 x^4+304 x^5-32 x^6-8 > x^7+x^8 >>> >>> You get the same answer which is how Mathematica knowns that these= > numbers are really equal - it does not attempt to transform one into = the > > other. When I wrote that >>> 1+Sqrt[15+2*Sqrt[35]+2*Sqrt[6*(6+Sqrt[35])] was "algebraically > simpler" than 1+Sqrt[3]+Sqrt[5]+Sqrt[7]] I meant only that the former = is > > Mathematica's radical representation of Root[1024 + 3584 #1 + 640 #1^2 = - > > 1984 #1^3 - 48 #1^4 + 304 #1^5 - 32 #1^6 - 8 #1^7 + #1^8 &, 8] - which= > is indeed the simplest way (algebraically) to express this algebraic= > number, which, of course, has infinitely many other representations in= > terms of radicals (which Mathematica will not be able, in general, to= > convert into one another but will always be able to find their minimal= > polynomial). >>> >>> This is not a limitation of Mathematica - it is a limitation of the= > radical representation of algebraic numbers. >>> >>> Andrzej Kozlowski >>> >>> >>> >> >> >> Even the above was still not quite accurate. MinimalPolynomial of an= > algebraic number, still does not determine it - obviously >> >> MinimalPolynomial[ >> Root[1024 + 3584 #1 + 640 #1^2 - 1984 #1^3 - 48 #1^4 + 304 #1^5 - >> 32 #1^6 - 8 #1^7 + #1^8 &, 8], x] >> >> 024 + 3584 x + 640 x^2 - 1984 x^3 - 48 x^4 + 304 x^5 - >> 32 x^6 - 8 x^7 + x^8 >> >> MinimalPolynomial[Root[1024+3584 #1+640 #1^2-1984 #1^3-48 #1^4+304 > #1^5-32 #1^6-8 #1^7+#1^8&,7],x] >> 1024+3584 x+640 x^2-1984 x^3-48 x^4+304 x^5-32 x^6-8 x^7+x^8 >> >> but of course these roots themselves are not the same. However, once= > you know the minimal polynomial of an algebraic number you only need = to > isolate it from the other roots to determine it uniquely - which is > something that Mathematica does automatically when it numbers the = roots. > > So, once you determine the minimal polynomials of two algebraic = numbers > we know that if the polynomials are different so are the numbers, if= > they are the same we use root isolation to distinguish or identify = them. > > In any case, the point it that no transformations are performed on > radicals when doing this sort of thing. >> >> >> > >
- Follow-Ups:
- Re: find two numbers a,b, such that a+b=5432 & LCM[a,b]=223020
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Re: find two numbers a,b, such that a+b=5432 & LCM[a,b]=223020
- References:
- Re: simplification
- From: Peter Pein <petsie@dordos.net>
- Re: find two numbers a,b, such that a+b=5432 & LCM[a,b]=223020
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Re: simplification