## 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

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

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

### Re: Problem 319

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

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

### Re: Problem 319

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

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

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

### Re: Problem 319

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

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

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

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

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?
Good luck!

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

### Re: Problem 319

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?
Good luck!

puzzle is a euphemism for lack of clarity

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

### Re: Problem 319

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?
Good luck!

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

### Re: Problem 319

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.

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

### Re: Problem 319

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

puzzle is a euphemism for lack of clarity

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

### Re: Problem 319

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

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

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

### Re: Problem 319

No, it isn't

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

### Re: Problem 319

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

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

### Re: Problem 319

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

Agreed

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

### Re: Problem 319

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

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

### Re: Problem 319

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.