Problem 127

[elr]

i wrote a program that successfuly compute sigma(c) for c < 1000
however i keep getting wrong answer for c < 110000 ...,here some abc triple's my program found :

(20077,89898,109975)
(24833,85145,109978)
(23367,86612,109979)
(45635,64346,109981)
(4446,105535,109981)
(21145,88838,109983)
(23133,86852,109985)
(17665,92321,109986)
(42737,67250,109987)
(19665,90323,109988)
(32197,77793,109990)
(39168,70823,109991)
(17879,92113,109992)
(50402,59591,109993)
(33233,76761,109994)
(41296,68699,109995)
(9628,100367,109995)
(27471,82525,109996)
(29263,80735,109998)
(42555,67444,109999)

i keep getting that the answer is 2573264393 however the site doesn't accept it

can someone verify sigma(c) for c < 10000
so i can see if i got a problem with c's that are higher than 1000

[Georg]

Review your check for "rad(abc) < c".

[elr]

thanks alot,i manage to fix & solve the problem

[shadowx360]

My code for problem 127 is way too slow, it gets caught on numbers like 2048 and stays there for hours at a time. I have tried to speed it up significantly using the 6k+-1 prime test and skipping when both c and a are even.

Below is problem 127 from the site:
The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 2^(3) × 3^(2) × 7, so rad(504) = 2 × 3 × 7 = 42.

We shall define the triplet of positive integers (a, b, c) to be an abc-hit if:

1. GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
2. a < b
3. a + b = c
4. rad(abc) < c

For example, (5, 27, 32) is an abc-hit, because:

1. GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1
2. 5 < 27
3. 5 + 27 = 32
4. rad(4320) = 30 < 32

It turns out that abc-hits are quite rare and there are only thirty-one abc-hits for c < 1000, with ∑c = 12523.

Find ∑c for c < 120000.

Note: This problem has been changed recently, please check that you are using the right parameters.

Here is my C++ code:

Code: Select all

### deleted by ed_r ###

I have no idea why it would get stuck on numbers like 2048, and even when it is not getting stuck, calculating the sum takes much longer than one minute with this code. Can anyone give me any pointers to making this code more efficient?

[ed_r]

Please don't post solution code.

If your code is slow, but still works, then there's no need to ask here: use the solvers' forum for problem 127.

[shadowx360]

Where is the solver's forum? I haven't been able to solve this yet, my code works, but you would have to wait about 2 weeks to get the answer (optimistically speaking). I can't enter the thread for 127 on projecteuler, since I haven't been able to obtain my answer. I believe there might have been a glitch in the code that causes it to freeze on certain numbers.

[daniel.is.fischer]

Then you can PM me your code. If I find a glitch, I might give you a useful hint.

[shadowx360]

Thanks, I found that rad(abc) is the same as rad(a)*rad(b)*rad(c) when they are coprime. This speed it up enough for me to get a solution. Thanks for your time and offer.

[zwuupeape]

I'm not sure if that would spoil it. I have a question about this problem, probably anyone who solved it will understand what I'm talking about. Does the special case count ?

[daniel.is.fischer]

I solved it, but I don't understand. Except, possibly you interpret positive as nonnegative. If that's the case, no, positive means > 0, not [ge] 0. Otherwise, I don't see a possibility for a special case.

[zwuupeape]

gcd(9,1) = gcd(8,1) = gcd(9,8) = 1

1 + 8 = 9

rad(1*8*9) = 1*2*3 = 6 < 9

[daniel.is.fischer]

Yes, but it's not special.
gcd(1,48) = gcd(1,49) = gcd(48,49) = 1
1 < 48
1 + 48 = 49
rad(1*48*49) = rad(2⁴*3*7²) = 2*3*7 = 42 < 49.

[zwuupeape]

I meant the general case when a = 1.

Damn, this problem is hard ...

[hk]

Less hard than 257 I think, so keep trying.

[zwuupeape]

I solved it, but I still think it's hard. The limit just allows more naive solutions.

Problem 257 is not so hard, in my opinion. It's not hard to understand what you should search for, and not very hard to find it once you do. There are many problems here solved by > 1000 people that I found more difficult. It's really weird that so few people have solved it by now ..

[daniel.is.fischer]

I solved it, but I still think it's hard. The limit just allows more naive solutions.

Problem 257 is not so hard, in my opinion. It's not hard to understand what you should search for, and not very hard to find it once you do. There are many problems here solved by > 1000 people that I found more difficult. It's really weird that so few people have solved it by now ..

Just shows that hardness is a very individual matter. We didn't expect 257 to have so few solutions either.

[zwuupeape]

I hope that means you're saving another really hard one for next time

[daniel.is.fischer]

We have one or two in the making that might turn out very hard indeed. We just don't know yet which that will actually be

[Smaug]

Would it be possible to add to the problem description:
Find sum(c) for not necessarily distinct c <= 120000.
That confused me a lot.

[Jochen_P]

Got it down to 5 minutes in python, trying hard not to try my solution as I violated the 1 minute rule a bit too often recently

It was sooo frustrating when I revisited the code once in a while for the past few months, not being able to get a result in below some days of runtime, when suddenly ... It fell like scales from my eyes

edit: posted my solution with a runtime of 20 secs ... Gawd. It took only half a year to solve this one (details for further amusement in problem forum)