Generate a list of numbers with given prime divisors

[Bodigrim]

It would be nice to have a function, which lists numbers with prime divisors in a given set. Here is a very inefficient implementation:

foo :: Set Integer -> Integer -> Integer -> [Integer]
foo ps from to = filter (all (flip S.member ps . fst) . factorise) [from..to]

Of course, real implementation should avoid factorisation completely.

Side note: a paper on smooth numbers, especially Ch. 5.7.

[grandpascorpion]

I have something that can do that (from a Project Euler solution) Where should do you think it should be added? I don't know of a smart way using this sort of algorithm to generate all of the numbers below the lower bound in order to exclude them. There is an efficient internal routine to merge the lists of lists. Any culling would have to occur in there. Also, there's probably a better name than smooth. Open to suggestions :)

smooths :: (Integral a) => [a] -> [a]

smooths pl -- returns an infinite, lazily evaluated list

smoothRange :: (Integral a) => [a] -> a -> a -> [a]

smoothRange pl lo hi = takeWhile (<= hi) $ dropWhile(<= lo) $ smooths pl

Example:

*Main> take 50 $ smooths [2, 7, 17][1,2,4,7,8,14,16,17,28,32,34,49,56,64,68,98,112,119,128,136,196,224,238,256,272,289,343,392,448,476,512,544,578,686,784,833,896,952,1024,1088,1156,1372,1568,1666,1792,1904,2023,2048,2176,2312]

On Wed, Oct 18, 2017 at 6:57 PM, Bodigrim notifications@github.com wrote:

It would be nice to have a function, which lists numbers with prime divisors in a given set. Here is a very inefficient implementation:

foo :: Set Integer -> Integer -> Integer -> [Integer] foo ps from to = filter (all (flip S.member ps . fst) . factorise) [from..to]

Of course, real implementation should avoid factorisation completely.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/cartazio/arithmoi/issues/78, or mute the thread https://github.com/notifications/unsubscribe-auth/AJtWDafBBrKMkad0cjRH93hp8XeRkqh4ks5stoJWgaJpZM4P-eWZ .

[Bodigrim]

Wow, sounds nice. It is probably worth of a separate module Math.NumberTheory.SmoothNumbers. A function may be called smooth or smoothOverSet (following the term from wiki). You are welcome to prepare a PR.

[grandpascorpion]

Ooh, I like smoothOverSet. I guess we could do something similar with smoothOverList (which would need to sort the "nub"). I was thinking only primes would be allowable as input but the wiki page used values which are not always prime. If we were validating the input, I think we could reject a set/list that had any two members which were not relatively prime. So (4,3, 5) would be allowed but not (4, 3, 15). Otherwise,

I think smooth itself could take a single parameter.

So, smooth 23 would generate numbers that were 23-smooth which I think is intuitive. It would call the same underlying function.

On Thu, Oct 19, 2017 at 5:58 PM, Bodigrim notifications@github.com wrote:

Wow, sounds nice. It is probably worth of a separate module Math.NumberTheory.SmoothNumbers. A function may be called smooth or smoothOverSet (following the term from wiki https://en.wikipedia.org/wiki/Smooth_number#Smooth_over_a_set_A). You are welcome to prepare a PR.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/cartazio/arithmoi/issues/78#issuecomment-338049823, or mute the thread https://github.com/notifications/unsubscribe-auth/AJtWDRtIAergeyU_Zffxhxuz774CusNHks5st8YDgaJpZM4P-eWZ .

[Bodigrim]

Good, I agree with the proposed interface.

[grandpascorpion]

Sorry, I had one other thought.

Using the convention of the wiki page, would 16 be smooth over the set {4, 3} but not 8? 8 is still a multiple of 4 that doesn't use another prime factor. It seems like a bit of a gray area.

Thanks

On Sat, Oct 21, 2017 at 6:19 AM, Bodigrim notifications@github.com wrote:

Good, I agree with the proposed interface.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/cartazio/arithmoi/issues/78#issuecomment-338381170, or mute the thread https://github.com/notifications/unsubscribe-auth/AJtWDRmxLdZNHKYNtBh-Liznsd7v22JRks5sucU6gaJpZM4P-eWZ .

[Bodigrim]

It is sensible to stick to the convention on the cited wiki page, unless we have a good reason to do it in another way. Yes, wiki does not consider 16 to be smooth over {8, 3}.

[grandpascorpion]

Agreed, thanks

On Sun, Oct 22, 2017 at 7:01 PM, Bodigrim notifications@github.com wrote:

It is sensible to stick to the convention on the cited wiki page, unless we have a good reason to do it in another way. Yes, wiki does not consider 16 to be smooth over {8, 3}.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/cartazio/arithmoi/issues/78#issuecomment-338516196, or mute the thread https://github.com/notifications/unsubscribe-auth/AJtWDXaueBrqwBNKFfCmXs3oMe1bHvJHks5su8lmgaJpZM4P-eWZ .

[grandpascorpion]

Sorry, I let this drop on the floor. Should this script be part of the test-suite?

Best, Fred

On Sun, Oct 22, 2017 at 7:21 PM, Fred Schneider < frederick.schneider2011@gmail.com> wrote:

Agreed, thanks

On Sun, Oct 22, 2017 at 7:01 PM, Bodigrim notifications@github.com wrote:

It is sensible to stick to the convention on the cited wiki page, unless we have a good reason to do it in another way. Yes, wiki does not consider 16 to be smooth over {8, 3}.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/cartazio/arithmoi/issues/78#issuecomment-338516196, or mute the thread https://github.com/notifications/unsubscribe-auth/AJtWDXaueBrqwBNKFfCmXs3oMe1bHvJHks5su8lmgaJpZM4P-eWZ .

[Bodigrim]

Well, it is always nice to have tests. But we can start without them as well.

[Bodigrim]

@grandpascorpion any chance for pull request?

[grandpascorpion]

Done

Thanks

On Sun, Jan 21, 2018 at 6:06 PM, Bodigrim notifications@github.com wrote:

@grandpascorpion https://github.com/grandpascorpion any chance for pull request?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/cartazio/arithmoi/issues/78#issuecomment-359289831, or mute the thread https://github.com/notifications/unsubscribe-auth/AJtWDXxRehDsJcl-hMzXncn0VJW0SZ_Vks5tM8LbgaJpZM4P-eWZ .

[Bodigrim]

Done in #91