Problem 355

[Duality]

Anyone have any advice? No matter what I do to this problem, I'm always looking at disgustingly huge runtimes.

I understand some basic requirements of every element in the solution set, but getting the right numbers is eluding me. I could really use a push in the right direction as to how to shorten this thing down.

[eppie]

I was struggleing with some long ruetines, but I think I have an efficient one now. It gets the right results for 10, 30, and 100, but not for 200000. (runs about 7.5 sec) Could someone who answered this give a clue for some higher values of n= 1000 and 5000 maybe? I don't know where I'm going wrong.
Thanks for the clues.

[hk]

I'm having difficulty with people starting to ask for more clues than are given when the problem is less than 48 hours old and there are still less than 50 people who have solved it.
Please remember that the first 50 to solve the problem get rewarded points for the Eulerian table.
Please have the patience to wait until the first 50 are in; or if that takes a long time, have the patience to find a better algoritm.

[eppie]

Sorry If I jumped the gun here. I don't really play for points for anything, I just thought I had a good algorithm that didn't work. I'll wait a while. If I don't solve it before it's long in the history books, I'll see if someone has some tips then.

[tagdus]

Hi everybody!

This is my first post about Project Euler problems.

I was trying to verify Co(30) and Co(100) from the problem definition.

With pen and paper i came out with this for Co(30):

Co(30) = 1+16+27+25+7+11+13+17+19+23+29 = 188

They are all coprime, and between 1 and 30.

The sum should be 193 as stated in the problem.

What am I doing wrong? Where's the error? Any hint will be appreciated! Thanks.

SDV

[mynameisalreadytaken]

You are using a too simple approach - there is a Subset with sum 193.

[tagdus]

Ok, I'll try harder then.
Thank you.

[LarryBlake]

For 10000, I get 5972754. I don't know if this is correct, because my final answer isn't. If anyone would like to talk about my strategy offline, I'd appreciate it.

[guptavis]

Co(30) = 1+16+27+25+7+11+13+17+19+23+29 = 188

What am I doing wrong? Where's the error? Any hint will be appreciated! Thanks.

Co(30) = 1+27+25+11+13+17+19+23+29 +28= 193
replace 16+7 by 28. How to generalise this? I have no idea!

[Marcus_Andrews]

Co(30) = 1+16+27+25+7+11+13+17+19+23+29 = 188

What am I doing wrong? Where's the error? Any hint will be appreciated! Thanks.

Co(30) = 1+27+25+11+13+17+19+23+29 +28= 193
replace 16+7 by 28. How to generalise this? I have no idea!

I don't want to give anything away, but I'd just say that it would be a good idea to remember what it really means for numbers to be coprime. If every number in a solution set is coprime, then there is a certain fundamental requirement in place. Check some attributes of the solution set you've just made.

Based on that requirement, you can take a more bottom-up approach to this problem and more adequately assess which numbers are better candidates for placement in the solution list.

[ozturkfa]

Hi

What is the set for Co(100)?
This may help me to find my algorithms problem.

Thanks for your interest

[ozturkfa]

Hi

I find the set
co(100)={100, 99, 97, 91, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 1}

But the sum is 1310 "the problem states that it should be 1356".

What is wrong with this set?

[TripleM]

The only thing wrong with that set is that there is another set with a greater sum, and you're asked to find the maximal sum.

[ozturkfa]

The only thing i learned from TripleM's reply is nothing.
Thanks TripleM.

Is giving Co(100)'s set considered to be a kind of cheating?
Interesting...

Who cares!
I can find it anyway...

[hk]

If we had considered giving the set for C(100) a good idea we would have done so in the problem statement.
As we haven't done so we obviously did not think that a good idea.
So why should it be given here upon your request?

[ozturkfa]

OK
It is not that much important( and informative).
Thanks for your interest anyway.