Closed Bodigrim closed 5 years ago
Will submit a PR for this today.
@Bodigrim by the way, there was a small issue with markup in your first comment, some parts of it render as italic. Probably because of no spaces between the *
character.
@Bodigrim I'm not sure how to efficiently implement nFrees
for ALL prime factors, using an algorithm like to the one in smoothOver
but with primes
instead of a smooth basis doesn't work. I'll keep thinking, but this seems non-trivial.
Basically, one can reuse runFunctionOverBlock or - for the sake of performance - re-implement it, following the same approach.
@Bodigrim I see, however from what I can tell it won't directly help us with generating all n-free
numbers, unless that function is called in batches and then the resulting vectors are appended to the final result, iteratively.
@Bodigrim I didn't even consider filter (runFunction (isNFreeA n) x)
, although for good reason - not very efficient. I'll just push it as a first version.
A number is called n-free if its factorisation contains no prime powers larger or equal to n. For example, 30 = 2 3 5 is 2-free (square-free), 3-free (cube-free), etc.; 12 = 2 ^ 2 3 and 18 = 2 3 ^ 2 are not square-free, but are cube-free; 1000 is not even cube-free, but is 4-free.
It would be nice to implement two new functions:
Predicate
isNFree :: Word -> ArithmeticFunction a Bool
such thatrunFunction (isNFree n) x
check whetherx
is n-free.Function
nFrees :: Word -> [a]
, which lists all n-free numbers. I expect that an effective implementation ofnFrees
should avoid division (similar to Eratosthenes sieve).