Problem 566

[heyRandal]

Problem 566 (View Problem)
Does an efficient solution to this problem achieve the goal of running in under 1 minute!? (or even under 10 min?)

I've worked long and hard on this problem and I've learned a lot, no-doubt. But in my simulation-type solution, some of the elements such as F(13,14,53) are running beyond 1 billion and are taking hours on a fast machine running Java in NetBeans. Many F() values are in the 10s or even 100s of millions. My solution quickly matches the samples provided including G(17), but I have my doubts because of the time involved in calculating the final answer for G(53). If it can be computed in under 10 min, I clearly need a new approach.

Thanks (first post, 25 problems solved so far).

[MuthuVeerappanR]

Hi heyRandal,
I still haven't solved the question yet but in my experience with PE, they won't post a question unless they have a solution that runs well within a minute. It wouldn't surprise me if PE can solve the problem in less than 10 secs. There have been some compute intensive questions in the past but still there will always be a solution that can comfortably pass the one minute rule.

If you can get the sample values right, keep working and you will eventually get to the right approach.

[v6ph1]

I doubt that "brute force" is the correct algorithm for this problem.
One value seams to be beyond 10^14. (compare to the ~2*10^11 clock cycles per minute of a up-to-date processor)

There must exist a number-theoretic function to solve this problem.

[heyRandal]

Thanks for two kindly answers. Your opinions make sense so I will think more and compute less.

[Vectorspace000]

I'm re-learning Java after about 15 years, and I'm using Project Euler to give me problems to solve in Java as a way of practice. My mathematics knowledge is not all that great, and some of these go over my head. I need clarification on something for problem 566.

Let G(n)=∑_{9≤a<b<c≤n} F(a,b,c), for integers a, b and c.

I understand that ≤a<b<c≤n are the bounds for the summation, but I've never seen one with multiple variables before so I'm not certain I understand how it works. Does it mean that for a particular value of n, I sum up F(a,b,c) for every possible value of a, b, and c that satisfies those bounds?

E.g. if n was 12, then these are all the possible combinations of a, b, and c:
9, 10, 11
9, 10, 12
9, 11, 12
10, 11, 12
So I would calculate F(a, b, c) for all four of these possibilities and then sum the results?

I'm going for brute force simulation too, I don't have the mathematics skill to derive a quicker method. I'll be happy if I can reproduce the sample values.

[jaap]

I understand that 9≤a<b<c≤n are the bounds for the summation, but I've never seen one with multiple variables before so I'm not certain I understand how it works. Does it mean that for a particular value of n, I sum up F(a,b,c) for every possible value of a, b, and c that satisfies those bounds?

E.g. if n was 12, then these are all the possible combinations of a, b, and c:
9, 10, 11
9, 10, 12
9, 11, 12
10, 11, 12
So I would calculate F(a, b, c) for all four of these possibilities and then sum the results?

Yes, that is correct.
9≤a<b<c≤n is essentially just a more compact way of writing the four inequalities 9≤a, a<b, b<c, c≤n, but I find that having them chained them together like that conveys more directly the idea that (a,b,c) form an ordered triplet of distinct numbers between 9 and n inclusive. The sum ranges over all such triplets.

[Vectorspace000]

Thought so, thanks jaap.

So far I have failed to manage this. I think I'm being let down by the precision of my simulation method.
One of the examples is G(17) = 1'269'260. G(17) would include F(11,14,15) so therefore F() should be less than 1'269'260. But mine is going over 1'300'000.

I may have to give up on this one and do another one.

[MuthuVeerappanR]

I did it!!! Yes!!! In your face Problem 566 (View Problem)!!!