# Tag Info

5

I can't complete with Artes's mathematical knowledge and approach, but simply as a point of reference, for formulating a brute-force approach it will be more memory efficient to use Sum, though it will still be very slow for large input. Sum[Boole @ PrimePowerQ @ i, {i, 5*^6}] // Timing MaxMemoryUsed[] {46.535, 348940} 15083688

6

Here's a fancy memoized solution: Clear[primePowerCount, primePowerCountcache, iPrimePowerCount] iPrimePowerCount[n1_, n2_] := Count[Range[n1, n2], _?PrimePowerQ] primePowerCountcache = {1}; primePowerCount[1] = 0; primePowerCount[n_?Positive] := Module[{n0, res}, n0 = First@Nearest[primePowerCount`cache, n]; If[n0 < n, res = ...

10

A naive approach would be this: primePower[n_] := Count[ Range @ n, _?PrimePowerQ] This function works well however it might be very inefficient for large n. It takes a bit to evaluate e.g. primePower[10^6] 78734 which is only a little bigger than PrimePi[10^6] 78498 The latter is much more efficient since it uses advanced algorithms for ...

3

SetAttributes[cubeFreeQ, Listable] cubeFreeQ[n_Integer] := Max@FactorInteger[n][[All, 2]] < 3 seems straightforward To find all the cube-free numbers in the first 1000 integers, do Select[Range[1000], cubeFreeQ]

1

cf[u_]:=And@@(#<3&/@FactorInteger[u][[All,2]]) yields True for cf[630], cf[64] False.

3

FreeQ[ Last @ Transpose @ FactorInteger[630], 3] True In general: cubeFreeQ[n_Integer] := FreeQ[ Last @ Transpose @ FactorInteger[n], _?(# >= 3 &)] It works like this: cubeFreeQ /@ {113, 125, 137, 256, 193839272} {True, False, True, False, False} And you can select cube free numbers this way: Cases[{15, 16, 24, 36, 48, 77, 125, ...

8

Number theory questions are always a huge accumulator for up votes. :) From my experience I can say that the builtin MangoldtLambda function is pretty slow. So let's define a Mangoldt function on our own. The Mangoldt function is defined by: $\Lambda(n) \equiv \left\{ \begin{array}{1 1} ln\ p & \quad \text{if n =$p^k\$ for p a prime}\\ 0 & \quad ...

Top 50 recent answers are included