Membership in http://oeis.org/A000975 is definitely the way to go. The description of the sequence makes it clear that it's just saying 170 is 10101010 in binary, but the comments section offers plenty of examples of cool things about those alternating-0s-and-1s numbers. --Michael On Wed, May 8, 2019 at 10:41 AM Mike Stay <metaweta@gmail.com> wrote:

http://oeis.org/search?q=170

On Wed, May 8, 2019 at 8:29 AM James Propp <jamespropp@gmail.com> wrote:

...

I’ve agreed to host Carnival of Mathematics #170 next month, and I’m wondering whether the number 170 has any especially nice properties that might deserve mention.

The number 170 has its own Wikipedia page, but none of the mathematical properties listed there appealed to me.

I might say a little about writing numbers as sums of two squares, but

I’d

...

prefer something a little more exciting.

Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Forewarned is worth an octopus in the bush.

Actually, now that I'm getting ready to write this up, I realize that I'm confused. If we've got a Hamiltonian circuit on the 8-cube coming from a Gray code of length 8, and we have a path of length 170 from 00000000 to 11111111, don't we also have a path of length 256-170=86 from 11111111 back to 00000000? Wouldn't traversing this path in reverse give us a path of length 86 from 00000000 to 11111111? So isn't there a solution for The Brain (aka "The Brain Puzzle") that takes only 86 moves? Jim Propp On Wed, May 8, 2019 at 11:50 AM James Propp <jamespropp@gmail.com> wrote:

That's perfect!

I see that in particular the Gray-code-based puzzle "The Brain Puzzler" takes 170 moves to solve:

https://everything2.com/title/The+Brain+Puzzler

Thanks, Michael!

Jim

On Wed, May 8, 2019 at 11:06 AM Michael Kleber <michael.kleber@gmail.com> wrote:

...

Membership in http://oeis.org/A000975 is definitely the way to go. The description of the sequence makes it clear that it's just saying 170 is 10101010 in binary, but the comments section offers plenty of examples of cool things about those alternating-0s-and-1s numbers.

--Michael

On Wed, May 8, 2019 at 10:41 AM Mike Stay <metaweta@gmail.com> wrote:

...

http://oeis.org/search?q=170

On Wed, May 8, 2019 at 8:29 AM James Propp <jamespropp@gmail.com> wrote:

...

I’ve agreed to host Carnival of Mathematics #170 next month, and I’m wondering whether the number 170 has any especially nice properties

that

...

might deserve mention.

The number 170 has its own Wikipedia page, but none of the mathematical properties listed there appealed to me.

I might say a little about writing numbers as sums of two squares, but I’d prefer something a little more exciting.

Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

Regarding The Brain Puzzler: If you continue the gray code pattern past the solution point, you don't return to 00000000 after the remaining 86 moves, but rather you end up with the move after 10000000, which would be 110000000 (9 bits) if you had a 9th peg. Consider the sequence for a 4-peg Brain Puzzler. Assume you start at 0000, and the goal is to reach 1111. A peg can be moved if and only if the one immediately below it (if any) is 1, and all of the pegs below that one are 0. There is a 10-move solition. Continuing the pattern, after 15 moves you reach 1000. After that the pattern breaks, because the next move would be the non-existent 5th peg: 0 0000 1 0001 2 0011 3 0010 4 0110 5 0111 6 0101 7 0100 8 1100 9 1101 10 1111 11 1110 12 1010 13 1011 14 1001 15 1000 If there were a 5th peg, the pattern would continue: 16 11000 17 11001 18 11011 19 11010 20 11110 21 11111 22 11101 23 11100 24 10100 25 10101 26 10111 27 10110 28 10010 29 10011 30 10001 31 10000 After a total of 31 moves, the low-order 4 bits would return to 0000 for the first time, but not before reaching 1111 a second time (at move 21, the 5-peg solution). A 32nd move would require 6 pegs, and would leave the low-order 4 bits 0000, and the sequence for those bits would repeat. Note that the solution lengths alternate between doubling the move count vs. doubling it and then adding one. I remember playing with The Brain Puzzler as a kid. I found it very satisfying. Once your fingers got used to the pattern, you could chug away at it really fast without any pauses. Tom James Propp writes:

Actually, now that I'm getting ready to write this up, I realize that I'm confused.

If we've got a Hamiltonian circuit on the 8-cube coming from a Gray code of length 8, and we have a path of length 170 from 00000000 to 11111111, don't we also have a path of length 256-170=86 from 11111111 back to 00000000? Wouldn't traversing this path in reverse give us a path of length 86 from 00000000 to 11111111? So isn't there a solution for The Brain (aka "The Brain Puzzle") that takes only 86 moves?

Jim Propp

On Wed, May 8, 2019 at 11:50 AM James Propp <jamespropp@gmail.com> wrote:

...

That's perfect!

I see that in particular the Gray-code-based puzzle "The Brain Puzzler" takes 170 moves to solve:

https://everything2.com/title/The+Brain+Puzzler

Thanks, Michael!

Jim

I think that's right. At the start, i.e. all zeros, there is only one possible move, which is to set the rightmost bit to 1. And if the position consists of all zeros except for the leftmost bit, e.g. 1000, then there is again a single move, which is to set the rightmost bit to 1 (there would only be a second move in this case if you added an additional bit). Otherwise there are two moves: Toggling the rightmost bit (which is always possible), and toggling the bit immediately to the left of the rightmost 1. So for a fixed number of bits, there is linear sequence of moves which begins with 0000 and ends with 1000. The only issue with solving the puzzle is keeping track of where you are and not accidentally going in reverse at some point. Tom James Propp writes:

Am I correct in thinking that for this puzzle, in any given state, there are only two actions you can take, except at the two extreme states, where there is only one action you can take?

That is, is the configuration space just a very tangled path?

Jim Propp

On Fri, May 31, 2019 at 5:05 PM Tom Karzes <karzes@sonic.net> wrote:

...

Regarding The Brain Puzzler:

If you continue the gray code pattern past the solution point, you don't return to 00000000 after the remaining 86 moves, but rather you end up with the move after 10000000, which would be 110000000 (9 bits) if you had a 9th peg.

Consider the sequence for a 4-peg Brain Puzzler. Assume you start at 0000, and the goal is to reach 1111. A peg can be moved if and only if the one immediately below it (if any) is 1, and all of the pegs below that one are 0. There is a 10-move solition. Continuing the pattern, after 15 moves you reach 1000. After that the pattern breaks, because the next move would be the non-existent 5th peg:

0 0000

1 0001 2 0011 3 0010 4 0110 5 0111 6 0101 7 0100 8 1100 9 1101 10 1111

11 1110 12 1010 13 1011 14 1001 15 1000

If there were a 5th peg, the pattern would continue:

16 11000 17 11001 18 11011 19 11010 20 11110 21 11111

22 11101 23 11100 24 10100 25 10101 26 10111 27 10110 28 10010 29 10011 30 10001 31 10000

After a total of 31 moves, the low-order 4 bits would return to 0000 for the first time, but not before reaching 1111 a second time (at move 21, the 5-peg solution). A 32nd move would require 6 pegs, and would leave the low-order 4 bits 0000, and the sequence for those bits would repeat.

Note that the solution lengths alternate between doubling the move count vs. doubling it and then adding one.

I remember playing with The Brain Puzzler as a kid. I found it very satisfying. Once your fingers got used to the pattern, you could chug away at it really fast without any pauses.

Tom

James Propp writes:

...

Actually, now that I'm getting ready to write this up, I realize that I'm confused.

If we've got a Hamiltonian circuit on the 8-cube coming from a Gray code of length 8, and we have a path of length 170 from 00000000 to 11111111, don't we also have a path of length 256-170=86 from 11111111 back to 00000000? Wouldn't traversing this path in reverse give us a path of length 86 from 00000000 to 11111111? So isn't there a solution for The Brain (aka "The Brain Puzzle") that takes only 86 moves?

Jim Propp

On Wed, May 8, 2019 at 11:50 AM James Propp <jamespropp@gmail.com> wrote:

...

That's perfect!

I see that in particular the Gray-code-based puzzle "The Brain Puzzler" takes 170 moves to solve:

https://everything2.com/title/The+Brain+Puzzler

Thanks, Michael!

Jim

I had the same thought about the Tower of Hanoi puzzle. Although with that one, I think you need to do a little bookkeeping to avoid transferring an intermediate sub-pile onto the wrong peg, which would lead you down a dead-end from which you'd have to backtrack to resume forward progress. Tom Fred Lunnon writes:

<< The only issue with solving the puzzle is keeping track of where you are and not accidentally going in reverse at some point. >>

Suspiciously similar to Towers of Hanoi/Brahma and Chinese rings ... WFL

On 6/1/19, Tom Karzes <karzes@sonic.net> wrote:

...

I think that's right. At the start, i.e. all zeros, there is only one possible move, which is to set the rightmost bit to 1. And if the position consists of all zeros except for the leftmost bit, e.g. 1000, then there is again a single move, which is to set the rightmost bit to 1 (there would only be a second move in this case if you added an additional bit).

Otherwise there are two moves: Toggling the rightmost bit (which is always possible), and toggling the bit immediately to the left of the rightmost 1.

So for a fixed number of bits, there is linear sequence of moves which begins with 0000 and ends with 1000. The only issue with solving the puzzle is keeping track of where you are and not accidentally going in reverse at some point.

Tom

James Propp writes:

...

Am I correct in thinking that for this puzzle, in any given state, there are only two actions you can take, except at the two extreme states, where there is only one action you can take?

That is, is the configuration space just a very tangled path?

Jim Propp

On Fri, May 31, 2019 at 5:05 PM Tom Karzes <karzes@sonic.net> wrote:

...

Regarding The Brain Puzzler:

If you continue the gray code pattern past the solution point, you don't return to 00000000 after the remaining 86 moves, but rather you end up with the move after 10000000, which would be 110000000 (9 bits) if you had a 9th peg.

Consider the sequence for a 4-peg Brain Puzzler. Assume you start at 0000, and the goal is to reach 1111. A peg can be moved if and only if the one immediately below it (if any) is 1, and all of the pegs below that one are 0. There is a 10-move solition. Continuing the pattern, after 15 moves you reach 1000. After that the pattern breaks, because the next move would be the non-existent 5th peg:

0 0000

1 0001 2 0011 3 0010 4 0110 5 0111 6 0101 7 0100 8 1100 9 1101 10 1111

11 1110 12 1010 13 1011 14 1001 15 1000

If there were a 5th peg, the pattern would continue:

16 11000 17 11001 18 11011 19 11010 20 11110 21 11111

22 11101 23 11100 24 10100 25 10101 26 10111 27 10110 28 10010 29 10011 30 10001 31 10000

After a total of 31 moves, the low-order 4 bits would return to 0000 for the first time, but not before reaching 1111 a second time (at move 21, the 5-peg solution). A 32nd move would require 6 pegs, and would leave the low-order 4 bits 0000, and the sequence for those bits would repeat.

Note that the solution lengths alternate between doubling the move count vs. doubling it and then adding one.

I remember playing with The Brain Puzzler as a kid. I found it very satisfying. Once your fingers got used to the pattern, you could chug away at it really fast without any pauses.

Tom

James Propp writes:

...

Actually, now that I'm getting ready to write this up, I realize that I'm confused.

If we've got a Hamiltonian circuit on the 8-cube coming from a Gray code of length 8, and we have a path of length 170 from 00000000 to 11111111, don't we also have a path of length 256-170=86 from 11111111 back to 00000000? Wouldn't traversing this path in reverse give us a path of length 86 from 00000000 to 11111111? So isn't there a solution for The Brain (aka "The Brain Puzzle") that takes only 86 moves?

Jim Propp

On Wed, May 8, 2019 at 11:50 AM James Propp <jamespropp@gmail.com> wrote:

...

That's perfect!

I see that in particular the Gray-code-based puzzle "The Brain Puzzler" takes 170 moves to solve:

https://everything2.com/title/The+Brain+Puzzler

Thanks, Michael!

Jim

That's correct; however, if discs and bases are coloured alternately black (odd diameter) and white (even), and an additional rule observed that no disc moves onto another of the same colour, then the ternary move tree becomes reduced to binary. WFL On 6/1/19, Allan Wechsler <acwacw@gmail.com> wrote:

The Tower of Hanoi "universe" is richer than that of (for instance) the Brain Puzzler. From many positions it is possible to make three different moves, so the state graph is not just a line. In fact the state graph resembles a Sierpinski triangle.

On Sat, Jun 1, 2019 at 2:18 AM Tom Karzes <karzes@sonic.net> wrote:

...

I had the same thought about the Tower of Hanoi puzzle. Although with that one, I think you need to do a little bookkeeping to avoid transferring an intermediate sub-pile onto the wrong peg, which would lead you down a dead-end from which you'd have to backtrack to resume forward progress.

Tom

Fred Lunnon writes:

...

<< The only issue with solving the puzzle is keeping track of where you are and not accidentally going in reverse at some point. >>

Suspiciously similar to Towers of Hanoi/Brahma and Chinese rings ... WFL

On 6/1/19, Tom Karzes <karzes@sonic.net> wrote:

...

I think that's right. At the start, i.e. all zeros, there is only one possible move, which is to set the rightmost bit to 1. And if the position consists of all zeros except for the leftmost bit, e.g. 1000, then there is again a single move, which is to set the rightmost bit to 1 (there would only be a second move in this case if you added an additional bit).

Otherwise there are two moves: Toggling the rightmost bit (which is always possible), and toggling the bit immediately to the left of the rightmost 1.

So for a fixed number of bits, there is linear sequence of moves which begins with 0000 and ends with 1000. The only issue with solving the puzzle is keeping track of where you are and not accidentally going in reverse at some point.

Tom

James Propp writes:

...

Am I correct in thinking that for this puzzle, in any given state, there are only two actions you can take, except at the two extreme states, where there is only one action you can take?

That is, is the configuration space just a very tangled path?

Jim Propp

On Fri, May 31, 2019 at 5:05 PM Tom Karzes <karzes@sonic.net> wrote:

...

Regarding The Brain Puzzler:

If you continue the gray code pattern past the solution point, you don't return to 00000000 after the remaining 86 moves, but rather you end up with the move after 10000000, which would be 110000000 (9 bits) if you had a 9th peg.

Consider the sequence for a 4-peg Brain Puzzler. Assume you start at 0000, and the goal is to reach 1111. A peg can be moved if and only if the one immediately below it (if any) is 1, and all of the pegs below that one are 0. There is a 10-move solition. Continuing the pattern, after 15 moves you reach 1000. After that the pattern breaks, because the next move would be the non-existent 5th peg:

0 0000

1 0001 2 0011 3 0010 4 0110 5 0111 6 0101 7 0100 8 1100 9 1101 10 1111

11 1110 12 1010 13 1011 14 1001 15 1000

If there were a 5th peg, the pattern would continue:

16 11000 17 11001 18 11011 19 11010 20 11110 21 11111

22 11101 23 11100 24 10100 25 10101 26 10111 27 10110 28 10010 29 10011 30 10001 31 10000

After a total of 31 moves, the low-order 4 bits would return to 0000 for the first time, but not before reaching 1111 a second time (at move 21, the 5-peg solution). A 32nd move would require 6 pegs, and would leave the low-order 4 bits 0000, and the sequence for those bits would repeat.

Note that the solution lengths alternate between doubling the move count vs. doubling it and then adding one.

I remember playing with The Brain Puzzler as a kid. I found it very satisfying. Once your fingers got used to the pattern, you could chug away at it really fast without any pauses.

Tom

James Propp writes: > Actually, now that I'm getting ready to write this up, I realize that I'm > confused. > > If we've got a Hamiltonian circuit on the 8-cube coming from a Gray code of > length 8, and we have a path of length 170 from 00000000 to 11111111, don't > we also have a path of length 256-170=86 from 11111111 back to 00000000? > Wouldn't traversing this path in reverse give us a path of length 86 from > 00000000 to 11111111? So isn't there a solution for The Brain (aka "The > Brain Puzzle") that takes only 86 moves? > > Jim Propp > > On Wed, May 8, 2019 at 11:50 AM James Propp < jamespropp@gmail.com> wrote: > > > That's perfect! > > > > I see that in particular the Gray-code-based puzzle "The Brain Puzzler" > > takes 170 moves to solve: > > > > https://everything2.com/title/The+Brain+Puzzler > > > > Thanks, Michael! > > > > Jim > >

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun