[Date Index]
[Thread Index]
[Author Index]
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)
 Deliveredto: lmathgroup@mailarchive0.wolfram.com
 References: <j6e693$kef$1@smc.vnet.net> <201110050801.EAA07025@smc.vnet.net> <360851F3769047A6BC84E9521100E6F4@mimuw.edu.pl> <A0A54467528743729FA6F0FD865B77D2@mimuw.edu.pl> <84B4CB1DC8A74A5F83039FEC113F7D16@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
"bruteforce" solution to someone who specifically asks for something
other than a bruteforce solution.
Andrzej
On 16 Oct 2011, at 23:47, Harvey P. Dale wrote:
> Here's a simple bruteforce 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
> ProblemCentered 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^21984 x^348 x^4+304 x^532 x^68 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^21984 x^348 x^4+304 x^532 x^68
> 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^21984 #1^348 #1^4+304
> #1^532 #1^68 #1^7+#1^8&,7],x]
>> 1024+3584 x+640 x^21984 x^348 x^4+304 x^532 x^68 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
 