Project Euler Forum

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

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

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

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

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 x_i and x_j.

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

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

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

No, it is not.

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?

No, but you are close. Here is the complete list for n=3: You can't ask for more, can you?
Good luck!

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!

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!

harryh wrote:the exponents are i and j, not x_i and x_j.

Thanks.
Seems I had a severe case of blindness yesterday, I couldn't see that even after looking at the formula many times.

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

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

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

No, it isn't

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

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

Agreed

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

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

This is incorrect -- you're very close though. ....3243.