Efficiently summing a multiplicative function via inclusion-exclusion

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
LucasBrown
Posts: 299
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

Efficiently summing a multiplicative function via inclusion-exclusion

Postby LucasBrown » Tue Apr 05, 2016 7:11 pm UTC

This might be better suited to the Coding or CS sections, but this seems mathy enough to belong here.

I'm working on a problem for a programming challenge (obfuscated to make googling this thread harder: it's # 222 in rot13(Cebwrpg Rhyre)). It devolves to computing the sum of a multiplicative function f(n) over a large interval (1 < nM). According to threads in other forums, this can be done via inclusion-exclusion in O(√M) time, using the primes < √M as the basis set for inclusion-exclusion. However, there's 4,157,407 in that basis, so in my (limited) understanding of inclusion-exclusion, there would be 24157407 terms to wrangle, which is clearly way too many. So there's got to be a way to exclude large swaths of the inclusion-exclusion terms, but I don't see a good way to do this.

If it helps, the function f(n) is 1 whenever n is squarefree, and on prime powers, we have f(pe) = pe if p divides e and f(pe) = pe-1 otherwise.

Can anyone help?

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Efficiently summing a multiplicative function via inclusion-exclusion

Postby Yakk » Wed Apr 06, 2016 12:48 pm UTC

Why don't you want it to be googleable?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
LucasBrown
Posts: 299
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

Re: Efficiently summing a multiplicative function via inclusion-exclusion

Postby LucasBrown » Wed Apr 06, 2016 6:42 pm UTC

Because the folks running the challenge discourage participants from posting full solutions on their blogs or finding the solutions by googling for people who do post their solutions like that. From their FAQ:

I solved it by using a search engine, does that matter?

Making use of the internet to research a problem is to be encouraged as there could be hidden treasures of mathematics to be discovered beneath the surface of many of these problems. However, there is a fine line between researching ideas and using the answer you found on another website. If you photocopy a crossword solution then what have you achieved?


I learned so much solving problem XXX so is it okay to publish my solution elsewhere?

It appears that you have answered your own question. There is nothing quite like that "Aha!" moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.


It can therefore be argued that seeking answers by posting here is a violation of the rules, but I feel that if the discussion is kept sufficiently abstract, then it's still allowable.

User avatar
chridd
Has a vermicelli title
Posts: 846
Joined: Tue Aug 19, 2008 10:07 am UTC
Location: ...Earth, I guess?
Contact:

Re: Efficiently summing a multiplicative function via inclusion-exclusion

Postby chridd » Thu Apr 07, 2016 12:48 am UTC

LucasBrown wrote:So there's got to be a way to exclude large swaths of the inclusion-exclusion terms, but I don't see a good way to do this.
There is. Think about what happens when you multiply large numbers of primes together, or when you multiply a medium sized number of large primes.
Also, it looks like you've maybe already noticed this, but notice that multiplying the input to the function by a prime only changes the value in some cases (which is why some primes don't need to be considered at all, regardless of the previous point).
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she · Forum game scores
mittfh wrote:I wish this post was very quotable...


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests