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.
$\begingroup$
$\endgroup$
asked May 29, 2015 at 20:39
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
6
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}.
-
$\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 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$– ubpdqnMay 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
$\begingroup$
$\endgroup$
3
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} *)
answered May 29, 2015 at 21:21
-
$\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
$\begingroup$
$\endgroup$
2
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
answered May 29, 2015 at 21:44
-
1$\begingroup$ More compactly:
rad[n_Integer?Positive] := Times @@ FactorInteger[n][[All, 1]]. You can useSplitBy[]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