Problem 127

[Smaug]

Would it be possible to post a ballpark figure for the number of c's please? I keep getting a string of wrong answers, all different!

[Jochen_P]

over 400 ...

[Smaug]

over 400 ...

Umm... thanks. I still think the problem description should state that the c values are not necessarily distinct, though!

[Dot]

Ok, I'm (apparently) having issues with this problem. I can very quickly verify the given answer for c < 1000, but my answer for c < 120,000 seems to be wrong. I calculated ~2.5782 x 10¹³ as the sum... is that even remotely close? Actually is there anyone who would be willing to look at my program to give me some tips?

Edit: Never mind. It seems as though rad(a*b*c) was overflowing for me, got the right answer now.

[ParadiceCity9]

Can someone verify this for me? For c < 10000 I get 41784307297 and for c < 5000 I get 3477742614.

[mdean]

Hmm... 120,000 didn't look that big to me, but apparently it was big enough to stop my recursive functions from working. Consider Plan A scrapped...

[fbarbuto]

Can someone verify this for me? For c < 10000 I get 41784307297 and for c < 5000 I get 3477742614.

These figures are not in agreement with the ones I've found: 150401 for c<5000 and 441085 for c<10000. Are you getting the correct answer for c<1000 (12523)? Check that.

My Python code seems to work fine, but still too slow despite the improvements I added to it: 1.45 minutes to calculate for c<5000 and 7.3 min for c<10000.

F.

[fbarbuto]

Well, I finally managed to get the correct answer with my Python/SAGE code, but it took 46.4 minutes to finish...

[saf_e]

I suppose it should be clearly stated that rad(1) = 1. I have spend some time in digging around this.

Mine points:
Statement from the task: The radical of n, rad(n), is the product of distinct prime factors of n.

1 can't be considered as prime factor, cause 1 isn't prime.
Wikipedia: A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

[stimmer]

1 has no prime factors, therefore the product of all distinct prime factors of 1 is the empty product, which by definition is equal to 1.

[thundre]

I suppose it should be clearly stated that rad(1) = 1.

I think rad(1) = 1, but I don't see why you would need to know that to solve Problem 127.

You need to calculate rad(a*b*c), where a, b, and c are distinct positive integers. Their product is always greater than 1.

[pieppiep]

I'm having problems solving this one.
My code gives the correct answers for 1000, 5000 and 10000 but it fails for 120000.
I'm sure I don't have any overflows because I use C#'s long (64bits) and all other things I can check are correct.
Can I PM my sourcecode to anyone who already solved this for review, or try some other ranges like 10000 < c < 50000 ?

[pieppiep]

I just found my error, it was in calculation the radicals.
Only one radical was wrong, close to 120000, so that's why my answers for 1000, 5000 and 10000 were correct.

[tv0r0g]

For the first time I am in strange situation: I got more abc-hits for c < 1000, then specified: 34 instead of 31. I checked them all manually, but they really seem to be abs-hits.

Yes, I know that there might be many abc-hits for the same c, and one must count these c's many times.

So I calculated my ∑c = 14392, found delta = 14392 - 12523 = 1869. Then I collected all my c's from abc-hits and got all their 3-element combinations, and fortunately only one of such triplets have sum of their c's equal to delta. So I must think, these 3 abc-hits are wrong, but here they are:

a = 1, b = 675, c = 676
a = 343, b = 625, c = 968
a = 1, b = 224, c = 225

(676 + 968 + 225 = delta = 1869)

I rechecked them manually, and they definitely are abc-hits. So I opened Russian translation of the problem, and there is a warning that problem wording was changed (I do not know, when).

Please check if there is an error in the answer or wording.

[mpiotte]

... So I must think, these 3 abc-hits are wrong, but here they are: ...
... and there is a warning that problem wording was changed (I do not now, when)...

There are 31 abc-hits with c < 1000, 3 of which are the correct examples you are giving. There are 28 other abc-hits to be found with c < 1000.
The problem statement was last updated in 2012.

[dawghaus4]

I hope this is fair. Here are my 31 abc-hits with c < 1000. (The sort in the output is on c.)

(snip)

[tv0r0g]

dawghaus4, thank you. I had these 3 triplets twice. The problem is clear now.

[hamsterofdeath]

Can someone verify this for me? For c < 10000 I get 41784307297 and for c < 5000 I get 3477742614.

These figures are not in agreement with the ones I've found: 150401 for c<5000 and 441085 for c<10000. Are you getting the correct answer for c<1000 (12523)? Check that.

My Python code seems to work fine, but still too slow despite the improvements I added to it: 1.45 minutes to calculate for c<5000 and 7.3 min for c<10000.

F.

i am getting the same numbers as paradicecity9
are those correct or wrong?
i get the correct number for 1000, but my solution for 120000 is rejected

[neverforget]

The answers in paradicecity9's post above are wrong.