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

Re: Easiest Mathematica algorhitm needed

• To: mathgroup at smc.vnet.net
• Subject: [mg92812] Re: [mg92793] Easiest Mathematica algorhitm needed
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Tue, 14 Oct 2008 04:55:40 -0400 (EDT)
• References: <gcq09i$c30$1@smc.vnet.net> <200810120835.EAA08892@smc.vnet.net> <200810131020.GAA14406@smc.vnet.net>

On 13 Oct 2008, at 19:20, Artur wrote:

> Dear Mathematica Gurus,
> Who know which Matrhematica function uses to separate square free part
> of number.
> e.g.
> In[1]: Table[Sqrt[n!], {n, 1, 10}]
> Out[1]: {1, Sqrt[2], Sqrt[6], 2 Sqrt[6], 2 Sqrt[30], 12 Sqrt[5], 12
> Sqrt[35],
> 24 Sqrt[70], 72 Sqrt[70], 720 Sqrt[7]}
> What to do to take squre-free parts:
> {1, 2, 6, 6, 30, 5, 35, 70, 70, 7}
> or square parts
> {1, 1, 1, 2, 2, 12, 12, 24, 72, 720}
> Best wishes
> Artur
>


It is a bit surprising that Sqrt does this since there is no  
polynomial time algorithm for factoring the square free part of an  
integer. In fact, we can implement the SquareFreePart algorithm using  
FactorInteger as follows:

SquareFreePart[n_Integer?Positive] := Times @@ Power @@@ ({#[[1]],  
Mod[#[[2]], 2]}& /@ FactorInteger[n])
and
SquarePart[n_Integer?Positive] := n/SquareFreePart[n]

  SquareFreePart /@ Table[n!, {n, 1, 10}]
{1, 2, 6, 6, 30, 5, 35, 70, 70, 7}
  SquarePart /@ Table[n!, {n, 1, 10}]
  {1, 1, 1, 4, 4, 144, 144, 576, 5184, 518400}

I don't think there is any much more efficient way of doing this.

Andrzej Kozlowski

• References:
  • Re: Executing external notebook
    • From: Peter Pein <petsie@dordos.net>
  • Easiest Mathematica algorhitm needed
    • From: Artur <grafix@csl.pl>