The Project Euler thread

[Reincarnate]

Re: THE project euler thread

It's not adding just the largest possible number -- here, it's adding all possible numbers from 2 to (N-1) and checking how it affects the total after removing non-coprimes

[LongGone]

Re: THE project euler thread

For 100, we have 25 odd primes (including 1), and one even 2. The sum of 25 odd primes (raised to any power) sum up to odd, adding the power of 2 still makes it odd

However, since we can group primes, we most likely will be grouping the smallest primes. There are 4 primes <sqrt100, 2 3 5 7. By grouping, we have 22 odd numbers and 2. 2 can be combined with an odd number leaving 21 odd numbers and one even number. The sum of that is odd. 1356 is even (?????????)

Possible explanation would be that the solution for 1356 involves -not- grouping one of 3, 5 or 7 and leaving it as its natural power. The most plausible is 3^4=81. Alternatively, there may be a case where there is a coprime which is the product of 3 primes

[stargroup100]

Re: THE project euler thread

FFFF YOU ARE RIGHT

im dumb

[Reincarnate]

Re: THE project euler thread

.ok apparently my problem is that it risks getting caught in local optima. when it detects a better sum, it may be adding a number (and keeping it) that winds up not being a part of the final solution (or prevents another number from doing the same). Going from 1 to n gives me a diff number from n to 1.

[stargroup100]

Re: THE project euler thread

that's what I was trying to say lol

[Reincarnate]

Re: THE project euler thread

ah ok misunderstood what you meant

[stargroup100]

Re: THE project euler thread

what the hell I went back to look at the problems I already solved in project euler and I cannot for the life of me remember how I did these LOL

all I remember is that I did most of these with pencil/paper

[stargroup100]

Re: THE project euler thread

Maybe something like this (building off SG's idea)

stuff

not quite

0 <= x < sqrt(n) list: [(1), 2, 3, 5]
sqrt(n) <= x < n/2 list: [7, 11, 13]
n/2 <= x list: [17, 19, 23, 29]

however, but my idea doesn't take into account longgone's new input, the fact that some of the primes from the first group might stand by themselves. however, if you combine your method with mine it should account for both cases pretty well.

[FFR4EVA_00]

Re: THE project euler thread

psst

{1, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 81, 83, 88, 89, 91, 95, 97}
i went off the fact that 81 is the largest number less than 100 of the form a^b

[stargroup100]

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).

[Reincarnate]

Re: THE project euler thread

I'm trying to find something that doesn't require bruteforce (most of the problems I've solved don't require it) -- this problem is bugging the hell out of me because I can't figure out anything more elegant

[cry4eternity]

Re: THE project euler thread

I just found this on Friday. Solved 1-22 as well as 67 now :p. This is actually pretty fun.

[stargroup100]

Re: THE project euler thread

I'm trying to find something that doesn't require bruteforce (most of the problems I've solved don't require it) -- this problem is bugging the hell out of me because I can't figure out anything more elegant

feelin ya bro

but it's possible this is along the lines of what they want. after all, they ARE programming problems.

[FFR4EVA_00]

Re: THE project euler thread

i'm gonna go ahead and drop a gigantic hint for 354 since the upper bound is so insane i have no chance of programming it correctly:

2L^2/3 = 2*3^(any non-negative integer)*n^2*(6p+1)^4*(6q+1)^4*(6r+1)^2
n must only be a multiple of 2 and any primes of the form 6k-1
6p+1, 6q+1 and 6r+1 are distinct prime numbers; p, q and r are integers

[stargroup100]

Re: THE project euler thread

Right now I'm trying to figure out methods to significantly reduce the number of calculations needed to solve this, whether it's skipping possible subsets or finding a totally new method.

However, it's getting late and I'm getting sleepy, difficult to focus. I'll work more on this tomorrow.