## Problem 611

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

Don't post any spoilers
henrig
Posts: 6
Joined: Mon Nov 21, 2016 7:39 am

### Problem 611

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
Posts: 54
Joined: Thu Nov 03, 2016 4:32 pm

### Re: Problem 611

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
Last edited by LilStalker on Sun Oct 08, 2017 6:52 am, edited 1 time in total.

henrig
Posts: 6
Joined: Mon Nov 21, 2016 7:39 am

### Re: Problem 611

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
Posts: 54
Joined: Thu Nov 03, 2016 4:32 pm

### Re: Problem 611

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
Posts: 6
Joined: Mon Nov 21, 2016 7:39 am

### Re: Problem 611

Thank you LilStalker.

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

TheBonobo4
Posts: 4
Joined: Sun Jul 12, 2015 8:51 pm

### Re: Problem 611

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

### Re: Problem 611

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

It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

TheBonobo4
Posts: 4
Joined: Sun Jul 12, 2015 8:51 pm

### Re: Problem 611

Good point, I'm an idiot.

MuthuVeerappanR
Posts: 349
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

### Re: Problem 611

TheBonobo4 wrote:
Sun Oct 15, 2017 6:15 am
Good point, I'm an idiot.
IMO, everyone once was..
TheBonobo4 wrote:
Sun Oct 15, 2017 6:15 am
... 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..

It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

Posts: 10
Joined: Tue Jan 16, 2018 9:27 pm

### Re: Problem 611

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
Posts: 77
Joined: Thu Oct 19, 2017 12:30 pm

### Re: Problem 611

[deleted]

Personally I treat "If you can't solve it, then you can't solve it!" as the most important rule.
Last edited by traxex on Wed Jan 17, 2018 6:17 pm, edited 3 times in total.
Technically, everyone is full of himself.

hk
Posts: 10346
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

### Re: Problem 611

@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
Posts: 7
Joined: Sun Aug 02, 2015 7:14 pm

### Re: Problem 611

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
Posts: 3
Joined: Mon Jan 21, 2019 11:11 pm

### Re: Problem 611

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
Posts: 1553
Joined: Sat Aug 16, 2014 12:23 pm

### Re: Problem 611

gregzzz wrote:
Mon Jan 21, 2019 11:19 pm
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
Posts: 3
Joined: Mon Jan 21, 2019 11:11 pm

### Re: Problem 611

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
Posts: 1553
Joined: Sat Aug 16, 2014 12:23 pm

### Re: Problem 611

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
Posts: 3
Joined: Mon Jan 21, 2019 11:11 pm

### Re: Problem 611

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.