1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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[#[[1]], fun[#[[2]]][[1]]], 
     fun[#[[2]]][[2]]} &, {{}, lt}, Length[#[[2]]] > 0 &]

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Geoffrey Critzer May 30 '15 at 12:17
  • $\begingroup$ @GeoffreyCritzer sent you an email $\endgroup$ – ubpdqn May 30 '15 at 13:46
  • $\begingroup$ @GeoffreyCritzer I was always curious about the criteria for publishing code snippets on OEIS ... $\endgroup$ – Dr. belisarius May 31 '15 at 4:08
  • $\begingroup$ @belisarius I referred Geoffrey to your updated code...he seems happy with a lot of the answers... $\endgroup$ – ubpdqn May 31 '15 at 4:10
  • 1
    $\begingroup$ @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! $\endgroup$ – Geoffrey Critzer May 31 '15 at 22:23
4
$\begingroup$
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} *)
$\endgroup$
  • $\begingroup$ 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}. $\endgroup$ – Geoffrey Critzer May 29 '15 at 23:17
  • 1
    $\begingroup$ 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! $\endgroup$ – Geoffrey Critzer May 29 '15 at 23:23
  • $\begingroup$ @GeoffreyCritzer I think I fixed it. Please recheck $\endgroup$ – Dr. belisarius May 30 '15 at 5:03
2
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ More compactly: rad[n_Integer?Positive] := Times @@ FactorInteger[n][[All, 1]]. You can use SplitBy[] instead in step 2. $\endgroup$ – J. M. will be back soon May 29 '15 at 21:57
  • $\begingroup$ 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? $\endgroup$ – Geoffrey Critzer May 29 '15 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.