MathGroup Archive 2002

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

Search the Archive

Re: Some list questions

  • To: mathgroup at smc.vnet.net
  • Subject: [mg37156] Re: [mg37132] Some list questions
  • From: Andrzej Kozlowski <andrzej at platon.c.u-tokyo.ac.jp>
  • Date: Sun, 13 Oct 2002 05:56:58 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

I noticed a rather curious trick that can be used to avoid having to  
use FactorInteger in the code I sent earlier for minint and maxint.  
Here is the new version:

In[2]:=
list1 = {{2, 3}, {3, 4}, {5, 6}, {7, 2}, {17, 5}};

In[3]:=
list2 = {{2, 5}, {3, 2}, {5, 1}, {7, 3}};

In[4]:=
minint[list1_List, list2_List] :=
   ToExpression[PolynomialGCD[Times @@
       Apply[ToString[#1]^#2 & , list1, {1}],
      Times @@ Apply[ToString[#1]^#2 & , list2, {1}]] /.
     {Times -> List, Power -> List}]

In[5]:=
maxint[list1_List, list2_List] :=
   ToExpression[PolynomialLCM[Times @@
       Apply[ToString[#1]^#2 & , list1, {1}],
      Times @@ Apply[ToString[#1]^#2 & , list2, {1}]] /.
     {Times -> List, Power -> List}]

In[6]:=
minint[list1, list2]

Out[6]=
{{2, 3}, {3, 2}, 5, {7, 2}}

In[7]:=
maxint[list1, list2]

Out[7]=
{{17, 5}, {2, 5}, {3, 4}, {5, 6}, {7, 3}}


The idea is to do exactly the same thing as before but now we find the  
GCD and LCM of expressions like "2"^3 *"5"^4 and "2"^4*"5"^3 etc. Note  
that the "base" in "a"^b is a string  and not a number so we need to  
use PolynomialGCD and PoynomialLCM instead of GCD and LCM.  Using such  
algebraic functions will usually make the program slower, but on the  
other hand we need not use FactorInteger so when the numbers one gets  
are large enough the present version should be faster. In any case it  
seems a curious idea so I thought it worth posting (even though it is  
easy to write conventional programs to do the same thing that ought to  
be much more efficient).


On Saturday, October 12, 2002, at 08:53 PM, Andrzej Kozlowski wrote:

> Of course one can use standard "programming" techniques to answer this  
> and it will in fact be the most efficient method. But as you will  
> probably get lots of answers of this kind, I will do it in another  
> way: by exploiting a few standard built-in number theoretic functions  
> which are very closely connected with your problems.
>
> Question 1:
>
> In[1]:=
> funct1[l_List]:=Outer[Times,Sequence@@(Divisors/@Power@@@l)]//Flatten
>
> In[2]:=
> funct1[{{2,3},{3,1},{5,1}}]
>
> Out[2]=
> {1,5,3,15,2,10,6,30,4,20,12,60,8,40,24,120}
>
> Note what we did. We first converted your pairs {a,b}  back into  
> powers a^b then found all the divisors using the built in Divisors  
> function, then found all the products using Outer.
>
> Question 2.
>
> In[3]:=
> minint[list1_,list2_]:=GCD[
>     Times@@Power@@@list1,Times@@Power@@@list2]//FactorInteger
>
> In[4]:=
> maxint[list1list1_,list2_]:=LCM[Times@@Power@@@list1,Times@@Power@@@lis 
> t2]\
> //FactorInteger
>
> e.g.
>
> In[5]:=
> list1 = {{2, 3}, {3, 4}, {5, 6}, {7, 2}, {17, 5}};
>
>
> In[6]:=
> list2 = {{2, 5}, {3, 2}, {5, 1}, {7, 3}};
>
>
> In[7]:=
> minint[list1,list2]
>
> Out[7]=
> {{2,3},{3,2},{5,1},{7,2}}
>
> In[8]:=
> maxint[list1,list2]
>
> Out[8]=
> {{2,5},{3,4},{5,6},{7,3},{17,5}}
>
> Basically all we did was to use the built in functions GCD and LCM  
> after converting your lists of powers to numbers. Then we factored  
> them again.
>
> In this case to finally factor an integer, which guarantees the  
> programs to be inefficient for large numbers. However if your original  
> list of pairs were indeed the result of using FactorInteger,  then you  
> should of course use versions of the above programs that can be  
> applied to the original un-factored integers. Indeed, in that case  
> this is the only efficient way to proceed.
>
> Andrzej Kozlowski
> Yokohama, Japan
> http://www.mimuw.edu.pl/~akoz/
> http://platon.c.u-tokyo.ac.jp/andrzej/
>
>
> On Saturday, October 12, 2002, at 06:05 PM, flip wrote:
>
>> Hello (sorry for the long post),
>>
>> I have two seperate list questions that I was hoping to get help with.
>>
>> Question 1.
>>
>>  I have a variable length list similar to that generated by  
>> FactorInteger,
>> that is {number, exponent} pairs.  An example follows.
>>
>> lista =  {{2,3},{3,1},{5,1}}  ... this is the number 2^3 * 3^1 * 5^1
>>
>> I want to generate a list of "all" the products of numbers from this  
>> list.
>>
>> I can tell that I get a total (3+1)*(1+1)*(1+1) = 4*2*2 = 16,  
>> products and I
>> want a list showing all of those.
>>
>> These would be:
>>
>> 2^3 can generate {2^0, 2^1, 2^2, 2^3} = {1, 2, 4 ,8}
>> 3^1 can generate {3^0,  3^1} = {3} ... we dont care about the  
>> duplicate "1"
>> 5^1 can generate {5^0, 5^1} = {5} ... we dont care about the  
>> duplicate "1"
>>
>> Hence the 4*2*2 = 16 (the product of one more of the exponents) above.
>>
>> Next we should get 16 products (from these lists), namely (I left  
>> them as
>> products below to show what I am after):
>>
>> {1,  2,  4,  8,  1*3,  2*3,  4*3,  8*3, 1*5, 2 * 5, 4* 5, 8* 5, 1*3*5,
>> 2*3*5,  4*3*5,  8*3*5}
>>
>> If the list were lista = {{2,4}, {3,2}, {5, 3},{7^5}}, we would have
>> (4+1)(2+1)(3+1)(5+1) = 360 products, for example and the return values
>> should be a single list showing all of those.
>>
>> Question 2.
>>
>> I have two lists and want to generate two new lists from them.  These  
>> two
>> lists are {number, exponent} pairs.
>>
>> In the first list, I want the "minimum intersection" of {number,  
>> exponent}
>> pairs.
>>
>> In the second list, I want the "maximum union" of {number, exponent}  
>> pairs.
>>
>> Let me show an example:
>>
>> Input:
>>
>> list1 = {{2, 3}, {3, 4}, {5, 6}, {7, 2}, {17, 5}}
>>
>> list2 = {{2, 5}, {3, 2}, {5, 1}, {7, 3}}
>>
>> Output:
>>
>> minint = {{2, 3}, {3, 2}, {5, 1}, {7, 2}}
>>
>> Note: In this example we only kept those pairs where the intersection  
>> of the
>> number exists and also keep the min power of those.
>>
>> maxint =  {{2, 5}, {3, 4}, {5, 6}, {7, 3}, {17, 5}}
>>
>> Note: In this example we kept the union of lists and also keep the  
>> max power
>> of each.
>>
>> Thank you so much to this newsgroup for being so helpful.
>>
>> Flip
>>
>> Note: remove the "_alpha" from the email given to email me.
>>
>>
>>
>>
>>
>>
>
>
> Andrzej Kozlowski
> Yokohama, Japan
> http://www.mimuw.edu.pl/~akoz/
> http://platon.c.u-tokyo.ac.jp/andrzej/
>
>
Andrzej Kozlowski
Yokohama, Japan
http://www.mimuw.edu.pl/~akoz/
http://platon.c.u-tokyo.ac.jp/andrzej/



  • Prev by Date: Re: Some list questions
  • Next by Date: Plot problem
  • Previous by thread: Re: Some list questions
  • Next by thread: Plot problem