y = sum of subset of divisors of x

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

y = sum of subset of divisors of x

Postby LucasBrown » Fri Dec 13, 2013 8:11 am UTC

I'm implementing an algorithm to produce a denominator-minimal Egyptian fraction expansion. One of the steps described (step 4 of the factorial algorithm on page 22 of http://kevingong.com/Math/EgyptianFractions.pdf) involves identifying the sets of divisors of n! q that add up to n! p (where p and q are relatively prime).

My current, highly naïve implementation of this step is to check each element of the power set of the divisors of n! q to see if any of those subsets yield n! p. This is a horrendously inefficient approach, especially since n gets as high as q2-q+1. Is there a way to speed the search?

Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: y = sum of subset of divisors of x

Postby DavCrav » Fri Jan 24, 2014 9:40 am UTC

In essence, you just want to know which subsets of X can add together to make a number n.

I don't know the most efficient algorithm to do this, but I needed this to solve a problem about possible decompositions of modules for algebraic groups, and thought up the following easy recursive algorithm.

function RestrictedDistinctPartitions(X,n)

1) Put X={x_1,\...,x_m} into ascending order, and write X'=X\{x_m}.

2) Call RestrictedDistinctPartitions(X',n) // this assumes x_m isn't in the set.

3) Call RestrictedDistinctPartitions(X',n-x_m ) // this assumes x_m is in the set.

4) Return the outputs of 2) and 3).

end function;

It should be faster than your method, I believe, but is still pretty slow.

User avatar
PM 2Ring
Posts: 3700
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: y = sum of subset of divisors of x

Postby PM 2Ring » Sat Jan 25, 2014 10:35 am UTC

Is it possible to do something to simplify / optimize this using the wonderful Möbius transform?

Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 14 guests