Problem 566

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
heyRandal
Posts: 2
Joined: Wed Jul 13, 2016 4:40 am

Problem 566

Post by heyRandal » Wed Jul 13, 2016 5:26 am

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
Posts: 337
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 566

Post by MuthuVeerappanR » Wed Jul 13, 2016 12:22 pm

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.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

v6ph1
Posts: 110
Joined: Mon Aug 25, 2014 6:14 pm

Re: Problem 566

Post by v6ph1 » Wed Jul 13, 2016 2:07 pm

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.
Image

heyRandal
Posts: 2
Joined: Wed Jul 13, 2016 4:40 am

Re: Problem 566

Post by heyRandal » Wed Jul 13, 2016 5:25 pm

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

Vectorspace000
Posts: 2
Joined: Thu Jul 28, 2016 7:10 pm

Re: Problem 566

Post by Vectorspace000 » Thu Jul 28, 2016 7:26 pm

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.

User avatar
jaap
Posts: 526
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 566

Post by jaap » Thu Jul 28, 2016 7:35 pm

Vectorspace000 wrote: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.
Last edited by jaap on Tue Jan 30, 2018 7:53 pm, edited 1 time in total.

Vectorspace000
Posts: 2
Joined: Thu Jul 28, 2016 7:10 pm

Re: Problem 566

Post by Vectorspace000 » Fri Jul 29, 2016 6:02 pm

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
Posts: 337
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 566

Post by MuthuVeerappanR » Mon Jan 29, 2018 5:26 pm

I did it!!! Yes!!! In your face Problem 566 (View Problem)!!!
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

Post Reply