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$

3 Answers 3

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$
6
  • $\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$ May 30, 2015 at 12:17
  • $\begingroup$ @GeoffreyCritzer sent you an email $\endgroup$
    – ubpdqn
    May 30, 2015 at 13:46
  • $\begingroup$ @GeoffreyCritzer I was always curious about the criteria for publishing code snippets on OEIS ... $\endgroup$ May 31, 2015 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, 2015 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$ May 31, 2015 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$
3
  • $\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$ May 29, 2015 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$ May 29, 2015 at 23:23
  • $\begingroup$ @GeoffreyCritzer I think I fixed it. Please recheck $\endgroup$ May 30, 2015 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$
2
  • 1
    $\begingroup$ More compactly: rad[n_Integer?Positive] := Times @@ FactorInteger[n][[All, 1]]. You can use SplitBy[] instead in step 2. $\endgroup$ May 29, 2015 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$ May 29, 2015 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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