What's wrong with my implementation of SquareFreeQ?

Question

This was a question I had last month:

Part A: Looking at the exponent of each of the elements in the list, FactorInteger and using Select construct your own variant of SquareFreeQ. Call it squareFreeQ. (You want the list of powers in FactorInteger to be all be 1, equivalently no power should be greater than 1 . The right Select evaluated on FactorInteger should give {}. Notice we only have to find one power > 1 so you will speed things up by using Select with an option.

Part B: Test that your construction squareFreeQ and Mathematica's SquareFreeQ are identical. You can do this by selecting the integer for which SquareFreeQ[n] != squarefreeQ[n]. Do this on a list of $10^5$ random integers between $10^{13}$ and $10^{14}$. Tell me how long it takes to perform this test. Be prepared to wait a little while.

This is what I had for part A:

squareFreeQ := Select[Last /@ FactorInteger[#], # > 1 &] &

and for part B:

Timing[SquareFreeQ[#] & /@ RandomInteger[{10^13, 10^14}, 10^15]]
squareFreeQ := Select[Last /@ FactorInteger[#], # > 1 &] &

When I got my assignment back, it says incorrect with no explanation. What would be the correct answer? Please explain.

Answer 1

Assuming only integers will be input to squareFreeQ.

Your squareFreeQ as defined in the question does not return True or False as does the built-in SquareFreeQ. Rather your function returns a list of exponents, if any, which are greater than one. Hence, after selecting exponents exceeding 1, compare the list to {}, which occurs for squarefree numbers. The result is True or False.

squareFreeQ[n_Integer]:=Select[FactorInteger[n][[All,2]],#>1&]=={}

For Part B you could try the following, which took 27 s on my machine. Your code as written in the question here, requests 10^15 random integers, which might be another "incorrect" in the marker's eyes.

With[{r=RandomInteger[{10^13,10^14},10^5]}, 
   AbsoluteTiming[Select[r, squareFreeQ[#]=!=SquareFreeQ[#]&]]]

Answer 2

I'm not sure if this is what the prof was thinking, but your function is not the same as the built-in function. Here are four cases.

squareFreeQ := Select[Last /@ FactorInteger[#], # > 1 &] &;
{squareFreeQ[#], SquareFreeQ[#]} & /@ {10, 12, x^4 - 1, x^4 - 2 x^2 + 1}

They agree on the first two, but your function throws errors on the final two while SquareFreeQ says True and False respectively.

Answer 3

I think that @KennyColnago is right, you need to make sure you return True or False. Additionally, in the last sentence in part A your prof is pointing out that you should use an option to make sure Select quits the routine as soon as a power is found, thus you can (and possibly should) use the third argument (strictly speaking not an "option") of Select:

squareFreeQ := Select[Last /@ FactorInteger[#], # > 1 &, 1] == {} &

I am using FactorInteger here as your prof points out, knowing that this won't work for expressions like the ones mentioned in @bills answer.

Then for Part B, you could do either like in KennyColnago's idea:

With[{r=RandomInteger[{10^13,10^14},10^5]}, 
   AbsoluteTiming[Select[r, squareFreeQ[#]=!=SquareFreeQ[#]&,1]]]

(where we use again the 3rd argument in Select, to get the first exception only - but as we are confident, we don't really need it here. Just to illustrate the point.)

Alternatively:

rInts = RandomInteger[{10^13, 10^14}, 10^5];
(res1 = SquareFreeQ /@ rInts;) // AbsoluteTiming
(res2 = squareFreeQ /@ rInts;) // AbsoluteTiming

Both are just about the same speed, and:

res1 == res2

True

Answer 4

The function squareFreeQ returns the exponents of factorization where as the the function SquareFreeQ is boolean, returning true if there are no square factors, viz al exponents are 1. Although the following does not use Select it can perhaps be motivation for desired solution:

squarefreeq[u_] := And @@ (#[[2]] == 1 & /@ FactorInteger[u]);

Testing:

rand = RandomInteger[{10^13, 10^14}, 10^5];
{t0, sq} = Timing[squarefreeq /@ rand];
{t1, Sq} = Timing[SquareFreeQ /@ rand];

t0 13.48 seconds, t1 12.03 seconds.

sq==Sq

yields True

Answer 5

Maybe too late to join the party, but here's is my implementation for squareFreeQ.

We know that a number is square-free, if its prime decomposition contains no repeated factors. Also we've to take into account, that 1 is by convention squarefree.

We can list the first squarefree numbers using:

Select[Range[20], Max[Last /@ FactorInteger[#]] < 2 &]

and we could compare this with Sloanes sequence A005117

Having this, an implementation seems to be rather straight forward:

squareFreeQ[x_] := Max[Last /@ FactorInteger[x]] < 2

squareFreeQ[11] ==> True
squareFreeQ[12] ==> False

Timings are:

rInts = RandomInteger[{10^13, 10^14}, 10^5];
(res1 = SquareFreeQ /@ rInts;) // AbsoluteTiming
(res2 = squareFreeQ /@ rInts;) // AbsoluteTiming  

{34.255805, Null}
{39.001603, Null}

I'm loosing 5 seconds when compared to the internal implementation, but I'm sure that squareFreeQ could be tweaked...