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>
- Re: Executing external notebook