Thread
:
The Project Euler thread
View Single Post
10-23-2011, 09:02 PM
#
55
stargroup100
behanjc & me are <3'ers
Join Date: Jul 2006
Posts: 2,051
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
View Public Profile
Visit stargroup100's homepage!
Find More Posts by stargroup100