Problem 611

[henrig]

Could someone please explain why F(5)=1 and not F(5)=3?

Is there not only two actions that Peter can take for N=5: (a) 1+4 and (b) 4. That would leave doors 1, 4 and 5 open.

I am also not sure how to deal with door zero. Is it closed for F(5) since it was opened it for 1+4 and then closed it for 4?

I would appreciate clarity on my questions.

Thank you

Henri

[LilStalker]

For F(5):
You only toggle the door after you do both steps (a) and (b) so (1 + 4) and you toggle the doors you are at - door number 5.
This is also the only posible action you can take. Since only door 5 is open it follows that F(5) = 1.

EDIT: (a) and (b) here have no connection with yours.
(a) move for x^2 steps
(b) move for another y^2 steps y>x

[henrig]

Does that not leave both doors 4 and 5 open (in which case F(5)=2)? Door 5 is open due to action (a) [1^2 + 2^2] and door 4 is open after (b) [2^2]?

[LilStalker]

But what happened with the step (a) in your second example? An action goes as follows:
(a) move for x^2 steps
(b) move for another y^2 steps y>x
(c) toogle the doors
(d) go back to 0

In your second example you do not do step (a).

[henrig]

Thank you LilStalker.

I did not realise that I need to consider two and only two steps.

[TheBonobo4]

I've just written out all the possible moves for 100 doors. In the question it says that F(100) = 27, but I get it as 29. Have I missed something (misunderstood the question), or is this a typo? I get it as he starts at door 0, moves a positive non-zero number of steps x, then a second, positive, number of steps y, where x<y. So for F(5)=1, this is because the only move is 1,4,5 and 0,1,1 and 0,4,4 are invalid moves. Here I've written in the form x, y, x+y, (that is, door after step 1, then how many more doors he moves to get to his final door). So for F(100) I have:

F(100)=27 as claimed in the question, yet I get 29 as follows:

1,4,5
1,9,10
1,16,17
1,25,26
1,36,37
1,49,50
1,64,65
1,81,82

4,9,13
4,16,20
4,25,29
4,36,40
4,49,53
4,64,68
4,81,85

9,16,25
9,25,34
9,36,45
9,49,58
9,64,73
9,81,90

16,25,41
16,36,52
16,49,65
16,64,80
16,81,97

25,36,61
25,49,74
25,64,89

36,49,85
36,64,100

leading to 31 possible moves, with doors 65 and 85 closed as they are opened then closed, and 29 total doors open.

Also apologies if this post violates forum rules in any way, I hope this doesn't count as spoilers, I'm just asking for clarity and confirmation.

[MuthuVeerappanR]

I think you should remove 65 and 85 twice... You are removing it only once and get 31 - 2 = 29..

However you should remove them completely.. 31 - 2 * 2 = 27

[TheBonobo4]

Good point, I'm an idiot.

[MuthuVeerappanR]

Good point, I'm an idiot.

IMO, everyone once was..

... or is this a typo? ...

Happens very very rarely in PE... I'm not saying it has never happened. But very rarely. So whenever I guess that the question might be wrong, I immediately conclude I'm doing something wrong. And just like you did, the best way is to clarify in this forum. Happy Solving..

[hexadoodle]

I've made some progress on this problem, found a useful theorem and tried many approaches, but I'm stuck. Is there anyone I can PM for a nudge in the right direction? I hope this is okay to ask, I've seen it done in earlier threads.

[traxex]

[deleted]

Personally I treat "If you can't solve it, then you can't solve it!" as the most important rule.

[hk]

@traxex
I saw hexadoodle's post almost the moment it was posted and (as one of the moderators of this forum) saw no reason for action.
The moderators are visiting this forum very frequently and don't hesitate to take action if needed.

[TexasRebel]

Argh!
What am I missing here...

I have 10^6 solving in 10.5s, but unfortunately that projects to about a year for 10^12...

Working on a 1.2 GHz CPU... Moving to a 3+ GHz rig would only get me down to 4 months, right?

EDIT: 6.5s on the 1.2 GHz CPU... ...but I think I have one more trick up my sleeve.

[gregzzz]

Omg I'm losing my mind. I built the Algorithm and it works.. After 10^9 I can't compute the solution under 5 min

This is the sequence for n <= 100

5, 10, 13, 17, 20, 25, 26, 29, 34, 37, 40, 41, 45, 50, 52, 53, 58, 61, 68, 73, 74, 80, 82, 89, 90, 97, 100

I found this sequence then here https://oeis.org/A025302

And after I build the algorithm to match this sequence A025302, It doesn't match for n <= 1000......

The Hallways algorithm gives me F(1000) = 233 (Which is correct)
The sequence gives me 226.. Extra numbers being ->

[0] 325 int
[1] 425 int
[2] 650 int
[3] 725 int
[4] 845 int
[5] 850 int
[6] 925 int

Please tell me. Isnt the "Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way" the correct sequence for the problem ?

Help..

[Animus]

Please tell me. Isnt the "Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way" the correct sequence for the problem ?

No, what happens when you find three different sums for one number?

[gregzzz]

I don't know, I haven't been paying attention if a number can be represented as the sum of 3 squares or no.. Is that the secret for this sequence ? I can't believe https://oeis.org/ doesnt have this sequence written down

[Animus]

No, I mean three different ways of representing a number as the sum of two squares, then the door with this number would be opened, closed and opened again, thus this number would have to be counted as well.

[gregzzz]

Thanks for your time, but I've given up already. I guess if https://oeis.org doesn't have it written down, its not me who's going to discover it with my lousy math skills.