# List of prime powers

I have a list of not necessarily distinct prime powers. For example: {2,3,4,25,2,3}. I want to combine (multiply) the highest prime powers for each prime. In this case 25*3*4 = 300 since 25 is the highest power of prime 5, 3 is the highest power of prime 3, and 4 is the highest power of prime 2. Now I want to delete these three elements from the list and repeat the process until the list is empty. In this case I want the list {300,6,2}. I would be happy to have a simple (easy to understand) code even at the expense of efficiency. The prime powers in my original list (input) can be limited to say the first 200 primes.

## 3 Answers

Not pretty,

fun[lst_] :=
Module[{int, num, res},
int = Sort /@ GatherBy[Join @@ (FactorInteger /@ lst), First];
num = Times @@ Power @@@ (Last@# & /@ int);
res = Flatten[Map[Power @@ # &, Most /@ int, {2}]];
{num, res}
]
rec[lt_] :=
First@NestWhile[{Append[#[], fun[#[]][]],
fun[#[]][]} &, {{}, lt}, Length[#[]] > 0 &]


so, rec[list] yields {300,6,2} and

rec[{2,2,2,3}] yields {6,2,2}.

• I would like to use your code as part of a code that will return the decomposition of the modulo multiplication group of integer n into a direct product of cyclic groups. I want to submit the sequence to Sloane's OEIS. If you would like, I will list you as co-author of the sequence... or ... give proper accreditation for the code ... or neither. Please advise, and thank you very much. – Geoffrey Critzer May 30 '15 at 12:17
• @GeoffreyCritzer sent you an email – ubpdqn May 30 '15 at 13:46
• @GeoffreyCritzer I was always curious about the criteria for publishing code snippets on OEIS ... – Dr. belisarius May 31 '15 at 4:08
• @belisarius I referred Geoffrey to your updated code...he seems happy with a lot of the answers... – ubpdqn May 31 '15 at 4:10
• @belisarius. In my experience the "criteria" for a code to be published in OEIS is only that it CORRECTLY returns a reasonable number of terms in a reasonable amount of time. Thanks very much for your help! – Geoffrey Critzer May 31 '15 at 22:23
mmg[l_List] := Module[{gb},
gb = GatherBy[First /@ FactorInteger@Sort[l, Greater], First];
Times @@@ (Power @@@ # & /@ Flatten[gb, {{2}, {1}}])
]

mmg[{2, 3, 4, 25, 2, 3}]
(* {300, 6, 2} *)

mmg[{2, 2, 2, 3}]
(* {6, 2, 2} *)

• If my list is {2,2,2,3} I want the code to return {6,2,2}. The code you are giving returns {6,2}. – Geoffrey Critzer May 29 '15 at 23:17
• By the way, If you are interested in number theory, what I want will be the group structure of the modulo multiplication group of an integer n. For example if n=72 then the group is isomorphic to C_2 X C_2 X C_6. Also thank you very much for your help! – Geoffrey Critzer May 29 '15 at 23:23
• @GeoffreyCritzer I think I fixed it. Please recheck – Dr. belisarius May 30 '15 at 5:03

This is the first step to get the 300, note that rad function is https://oeis.org/A007947

rad[n_]:=Times@@(First@#&/@FactorInteger@n)
(* rad is Largest squarefree number dividing n *)
mylist = {2, 3, 4, 25, 2, 3}


STEP-1: Sort the list

mylist = Sort[mylist]


STEP-2: Split the list in to distinct power of primes

mylist = Split[mylist, rad[#1]==rad[#2]&]


STEP-3: Take the last 3 elements

mylist = Map[Last, Take[mylist, -3]]


STEP-4: Multiply them

Times@@mylist

• More compactly: rad[n_Integer?Positive] := Times @@ FactorInteger[n][[All, 1]]. You can use SplitBy[] instead in step 2. – J. M.'s torpor May 29 '15 at 21:57
• Thanks, but I still don't how to make the process repeat. For example, how do I remove the elements { 3,4,25} from the original list {2,3,4,25,2,3}. I want to repeat this process with {2,2,3}. Also is step 1 necessary since we are going to split the list in step 2? – Geoffrey Critzer May 29 '15 at 23:48