View Single Post
Old 10-23-2011, 09:02 PM   #55
stargroup100
behanjc & me are <3'ers
FFR Simfile AuthorFFR Music Producer
 
Join Date: Jul 2006
Posts: 2,051
Default Re: THE project euler thread

Thanks to lurker and LG I can fix up my method a bit.

Okay, here's my updated algorithm. It seems to be pretty tight for the most part, but it is still fairly brute force and assumes two conjectures:

- A term in a maximal sum subset can never have more than two unique prime factors.
- When optimizing the sum of a subset by choosing to multiply two powers of primes, the two primes are never both below sqrt(n).

Assuming these conjectures, we use the method:
- Separate primes into 3 categories: between 2 and sqrt(n), between sqrt(n) and n/2, and the others
- Add up all of the primes in the last category. These don't change.
- Each of the terms in the first category can either be left by itself or paired with a term from the second category. Consider and test every case.

The total number of possible subsets to test for is exactly 9507!/(9421)!.

Hopefully we can do a little bit better than that, as this number is in the order of about 10^(well over 200).
__________________
Rhythm Simulation Guide
Comments, criticism, suggestions, contributions, etc. are all welcome.

Piano Etude Demon Fire sheet music

Last edited by stargroup100; 10-23-2011 at 09:20 PM..
stargroup100 is offline   Reply With Quote