Problem 370

[pinguin]

Problem 370 (View Problem)

Unfortunately my number for 10⁶ is much bigger than 861805. Maybe I don't understand the definition.

Is this true: (3,3,3),(2,4,8),(8,12,18) and (20,30,45) are geometric triangles

[hk]

(2,4,8) isn't a triangle as 8>2+4.

[pinguin]

thank you,

I forgot to check the triangle inequality - stupid

Now I can confirm the result

[EpicWisdom]

Can anybody confirm that under perimeter 10^5 there are 75243 such triangles and under 10^4 there are 6427?

[ericgorlin]

EpicWisdom, I can confirm those numbers.

My issue: while I'm getting the test value fine, I can't figure out how to work around the fact that 2.5*10^13 is a REALLY big number. So whatever tweaks I do always end up with (in python) MemoryError, error converting int to C long, or too big of a range.

Am I allowed to seek a hint?

[mdean]

Yeah, that bound is a killer. I've tried 3 variations on the same approach and the best I can do is a bound of about 10 billion or so. I haven't managed 100 billion yet without running out of memory.

[Waldovski]

Dear admins,

I have the answer for this problem (well, I'm pretty sure I do; it's the same sort of parametrisation that appeared in a bunch of other problems, and I get the correct result for 1e6) but my code runs in hours in MATLAB (the only thing I know how to code in). I don't want to enter my result before getting a sense of whether this long runtime has to do with MATLAB's notoriously slow loops, or is because I'm missing a key bit of optimisation. It seems that there's no escaping the gcd part, and it's really the only bottleneck in my code. Also, I have no memory issues; the square-root effect takes care of that just as was the case in the other similar problems.

Should I keep trying to get a faster algorithm before entering my solution? (Note: My code runs in about 7s for 2.5e9 and 360s for 2.5e11).

[Apologies if I've given away too much. I tried to be as discreet as I could.]

[mpiotte]

For this problem, if your time complexity is O(n) or worse then you still have significant improvement possible. If your time complexity is O(n^a) with a < 1 (a = 3/4 or 2/3 for example), then I think you should be satisfied. The high limit requested should tell you as much by itself.

[Kartownik_Magiczny]

Alright.

I believe I give up. Whatever I try, I seem to end up back with linear time algorithm. Even with hacky upgrades, that still turns into (estimated) roughly 19 days of computing time - absolutely unacceptable.
Just like mr. Waldovski, I don't see a way around the gcd thing and not even F**ey Se***n*e, nor S***n-B*o*o*-tree seem to help me in any significant way (If that is still too much spoiling, let me know).

Where should I be looking for speedups? Is there a particular PE problem/solution forum on PE that I should look into? Or something even more general?

Any help would be greatly appreciated, I have been puzzling over this problem for waaayy too long...

Thank you.

[neverforget]

This isn't really the place to ask for hints, but I want to say that it is always fine (and sometimes beneficial) to "give up" and take a break from a problem. I would even say that problem solving is as much knowing where to look as knowing when to stop. Anecdotally, I have lost count of how many times (more than a hundred for sure) I was initially unable to solve a problem, but after a few years I revisit with a fresh perspective and possibly new tools, and was able to solve it then.

[Kartownik_Magiczny]

This isn't really the place to ask for hints

I know it isn't.

but I want to say that it is always fine (and sometimes beneficial) to "give up" and take a break from a problem.

Thing is, I gave up on this problem once or twice already. And it's super frustrating, knowing that I am using some of the usual tricks used in PE, yet it still isn't good enough.

revisit with a fresh perspective and possibly new tools, and was able to solve it then.

I suppose I'm just gonna ask then, since finding out sublinear algorithms has been causing me difficulties on MANY other problems; how do you approach finding something like that? (in a more general setting)
Secondly, more concretely, should I completely scrap my "gcd" approach here or is there actually a way out with it?

Many thanks.

[DJohn]

how do you approach finding something like that?

You stop looking.

Many times I have worked on a problem long enough for it to seep into my brain, and given up because I'm not making further progress and have no idea what I'm looking for. Then much later (sometimes years), I will encounter some new technique in a completely unrelated context, and suddenly think "aha! problem xxx!" and go on to solve it.

It's healthy to temporarily give up on a problem. Keep solving others, keep reading the threads for them, keep yourself immersed in mathematics generally. Eventually you will find the thing you need. And if you never do, that's OK too. Life is short. We can't do all the things we want to.

I'm not saying give up as soon as you hit the smallest obstacle. Put in a decent effort. But when you reach the point (as you appear to have with this problem) where you've done all that you can and are still going nowhere, when you are no longer learning anything new from it, that's the time to put it aside. It'll still be there later, when you're better prepared.

[Kartownik_Magiczny]

I suppose I should just move on to other problems, yeah.
And I shall hope the aha-moment arrives sooner rather than later.
It's definitely healthier than what I did (was up until 3am just bashing at it with the above mentioned methods). Too eager and impatient, as usual, especially when feeling low.

Thanks for the wise words. To both of you, neverforget, DJohn!

[Oliver1012]

It's been a while, but could someone confirm 129...4312 for 10¹⁰?

Thank you

[edit]
Solved it.