Problem 319

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.
raggie
Posts: 4
Joined: Tue Dec 28, 2010 9:55 pm

Problem 319

Post by raggie »

Problem 319 (View Problem)

Is it right that $x_i\in \mathbb{N}$ , cause it isn't stated in the problem.

Shouldn't it be

Let $x_1$, $x_2$,..., $x_n$ be a [integer] sequence

User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

Re: Problem 319

Post by Lord_Farin »

By monotonicity of the given constraints this must be true to satisfy that there are only five sequences of length 2.
Image

starblue
Posts: 2
Joined: Thu Jun 11, 2009 9:48 am
Location: Germany

Re: Problem 319

Post by starblue »

I don't see how {2, 6} satisfies the third condition:

$$2^6=64 \not< 49 = (6+1)^2$$
Image

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 319

Post by harryh »

starblue wrote:I don't see how {2, 6} satisfies the third condition:

$$2^6=64 \not< 49 = (6+1)^2$$
It does, if you look carefully at Problem 319 (View Problem): the exponents are i and j, not xi and xj.

So, 22<(6+1)1 and 61<(2+1)2, both of which are true.

Navakanth
Posts: 3
Joined: Sun Jan 09, 2011 8:16 am

Re: Problem 319

Post by Navakanth »

Can anyone please verify that the the #of such sequences for n=3 is 20?

umisef
Posts: 4
Joined: Thu Apr 01, 2010 1:25 pm

Re: Problem 319

Post by umisef »

Navakanth wrote:Can anyone please verify that the the #of such sequences for n=3 is 20?
No, it is not.

Navakanth
Posts: 3
Joined: Sun Jan 09, 2011 8:16 am

Re: Problem 319

Post by Navakanth »

Navakanth wrote:Can anyone please verify that the the #of such sequences for n=3 is 20?
My bad, I counted wrongly, sorry, is it 24 for n=3?

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 319

Post by harryh »

No, but you are close. Here is the complete list for n=3:

Code: Select all

2 4 8
2 4 9
2 4 10
2 4 11
2 5 11
2 5 12
2 5 13
2 5 14
2 6 14
2 6 15
2 6 16
2 6 17
2 6 18
2 7 18
2 7 19
2 7 20
2 7 21
2 7 22
2 8 22
2 8 23
2 8 24
2 8 25
2 8 26 
You can't ask for more, can you? 8-)
Good luck!

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 9:37 am
Location: California, USA
Contact:

Re: Problem 319

Post by sivakd »

harryh, you know how to give details without revealing anything :). I can compute accurately even for t(20). But I don't know how to scale for larger values. I am also having issues with precision.
harryh wrote:No, but you are close. Here is the complete list for n=3:

Code: Select all

2 4 8
2 4 9
2 4 10
2 4 11
2 5 11
2 5 12
2 5 13
2 5 14
2 6 14
2 6 15
2 6 16
2 6 17
2 6 18
2 7 18
2 7 19
2 7 20
2 7 21
2 7 22
2 8 22
2 8 23
2 8 24
2 8 25
2 8 26 
You can't ask for more, can you? 8-)
Good luck!
Image
puzzle is a euphemism for lack of clarity

Navakanth
Posts: 3
Joined: Sun Jan 09, 2011 8:16 am

Re: Problem 319

Post by Navakanth »

Thanks! Harry.... Now have to figure out the 'best' way to easily count them...

harryh wrote:No, but you are close. Here is the complete list for n=3:

Code: Select all

2 4 8
2 4 9
2 4 10
2 4 11
2 5 11
2 5 12
2 5 13
2 5 14
2 6 14
2 6 15
2 6 16
2 6 17
2 6 18
2 7 18
2 7 19
2 7 20
2 7 21
2 7 22
2 8 22
2 8 23
2 8 24
2 8 25
2 8 26 
You can't ask for more, can you? 8-)
Good luck!

starblue
Posts: 2
Joined: Thu Jun 11, 2009 9:48 am
Location: Germany

Re: Problem 319

Post by starblue »

harryh wrote:the exponents are i and j, not xi and xj.
Thanks.
Seems I had a severe case of blindness yesterday, I couldn't see that even after looking at the formula many times.
Image

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 9:37 am
Location: California, USA
Contact:

Re: Problem 319

Post by sivakd »

If only the problem was limited to finding it the best way. IMHO, it also requires some juggling to find it in reasonable time inspite of knowing the best way to compute. Most likely it wouldn't have made much difference if the limit was set only to 10^8 instead of 10^10 but I don't know why the admins some times give very high limits while sometimes much lower limits. I spent more time trying to make the program run fast and fit within the memory than on finding the best way to solve it. Even after all that, I am way off with the 1 minute rule.
Navakanth wrote:Thanks! Harry.... Now have to figure out the 'best' way to easily count them...
Image
puzzle is a euphemism for lack of clarity

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: Problem 319

Post by stijn263 »

Check the forum. Hans Klein briefly explained his algorithm that solves the problem in 6 seconds.

The limits are pushed for some problems to make sure that asymptotically-suboptimal algorithms take longer than a minute or require too much memory :)

0liver
Posts: 1
Joined: Mon Jan 10, 2011 7:00 pm

Re: Problem 319

Post by 0liver »

Hi. Can anybody check if the answer for 4 is 101, please?

User avatar
hk
Administrator
Posts: 10889
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 319

Post by hk »

No, it isn't
Image

sangupta
Posts: 2
Joined: Wed Jan 12, 2011 4:35 pm
Location: India
Contact:

Re: Problem 319

Post by sangupta »

Please verify if the answer for sequence length 4 is 83, for length 6 is 935, for length 7 is 2993.
Image

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: Problem 319

Post by stijn263 »

If your answer matches for n = 5, there should be no reason to assume it's incorrect for the other values right?

sangupta
Posts: 2
Joined: Wed Jan 12, 2011 4:35 pm
Location: India
Contact:

Re: Problem 319

Post by sangupta »

Agreed :)
Image

quintana
Posts: 11
Joined: Wed Jan 28, 2009 5:53 pm

Re: Problem 319

Post by quintana »

could t(30) possibly end up with ...9113247?
thanks!

quilan
Posts: 182
Joined: Fri Aug 03, 2007 11:08 pm

Re: Problem 319

Post by quilan »

quintana wrote:could t(30) possibly end up with ...9113247?
thanks!
This is incorrect -- you're very close though. ....3243.
ex ~100%'er... until the gf came along.
Image

Post Reply