MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

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.
>>
>>
>>
>
>




  • Prev by Date: Re: find two numbers a,b, such that a+b=5432 & LCM[a,b]=223020
  • Next by Date: Control 6 does nothing
  • Previous by thread: Re: find two numbers a,b, such that a+b=5432 & LCM[a,b]=223020
  • Next by thread: Re: find two numbers a,b, such that a+b=5432 & LCM[a,b]=223020