electro-music.com   Dedicated to experimental electro-acoustic
and electronic music
 
    Front Page  |  Articles  |  Radio
 |  Media  |  Forum  |  Wiki  |  Links  |  Store
Forum with support of Syndicator RSS
 FAQFAQ   CalendarCalendar   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   LinksLinks
 RegisterRegister   ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in  Chat RoomChat Room 
Live streaming at radio.electro-music.com

  host / artist show at your time
  Muied Lumens Frequencies
Please visit the chat
 Forum index » DIY Hardware and Software
Tower of Hanoi
Post new topic   Reply to topic Moderators: jksuperstar, Scott Stites, Uncle Krunkus
Page 1 of 2 [38 Posts]
View unread posts
View new posts in the last week
Mark the topic unread :: View previous topic :: View next topic
Goto page: 1, 2 Next
Author Message
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Sat Aug 03, 2019 4:11 pm    Post subject: Tower of Hanoi
Subject description: puzzle sequence experiments
Reply with quote  Mark this post and the followings unread

something inspired by this video*: https://www.youtube.com/watch?v=2SUvWfNJSsM

Quote:

Posted Image, might have been reduced in size. Click Image to view fullscreen.

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower[1] and sometimes pluralized as Towers) is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
No larger disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.

- wikipedia


The solution is actually a nice recursive pattern, as is explained in the video.
To solve it you count in binary and the position of the bit that changes from 0 to 1 is the number of the disc (0 being the smallest) to move.
0001 move disc 0
0010 move disc 1
0011 move disc 0
0100 move disc 2
0101 move disc 0
0110 move disc 1
etc,

A disc is moved to the rod next to it (move all discs in the same direction), unless there is a smaller disc on it then
it is moved one rod further. Also after the 3rd rod you move back to the first one.

What isn't mentioned in the video is that there is a pattern behind moving it to the next rod or one further.
Something that becomes more clear if you place them in a circle. The value of each disc in bits is the amount of places
for it to move around this circle. What I mean by that is that if you count and bit 0 changes from 0 to 1, disc 0 is moved 2⁰ = 1 place
if bit 1 changes from 0 to 1 it is moved 2¹ = 2 places, disc 2 is moved 2² = 4 places, disc 3 is moved 2³ = 8 places, etc..
Because there are only 3 rods the result is that the discs actually move one place in alternating directions depending on the disc.
Disc 0 moves 1 place = 1 place CW
Disc 1 moves 2 places = 1 place CCW
Disc 2 moves 4 places = 1 place CW
Disc 3 moves 8 places = 1 place CCW
etc,


Ok, on to the music.
I like patterns and am always curious if/how they can be used for a musical sequence. To test this one I used an arduino controlling
a Proteus2000 through midi (shouldn't be too hard to do something with CMOS I think). I assigned each disc to a note and the rods
to 3 octaves. Whenever a disc is moved the note of the disc is played in the octave of the rod it is moved to. For this first take I used
12 discs/notes in the order of the circle of fifths: disc 0 = C, disc 1 = G, disc 2 = D, etc. The resulting sequence is 4095 steps looong
and quite musical and of course also very recursive. Depending on the note they move up or down the octaves and the note assigned
to a small disc is played more often than that of a larger disc.

up next: Blue Hell makes another wren module Laughing


* There is a follow up video which adds another rule and links it to a sierpinski triangle so I'll probably experiment with that later.


PHOBoS - Tower of Hanoi - Take 1 (Aug 03, 2019).mp3
 Description:
PHOBoS - Tower of Hanoi - Take 1 (Aug 03, 2019)

12 discs in the order of the circle of fifths

Download
 Filename:  PHOBoS - Tower of Hanoi - Take 1 (Aug 03, 2019).mp3
 Filesize:  14.1 MB
 Downloaded:  278 Time(s)


_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider

Last edited by PHOBoS on Wed Aug 07, 2019 6:00 am; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Sun Aug 04, 2019 12:47 pm    Post subject: Re: PHOBoS - Tower of Hanoi
Subject description: puzzle sequence experiments
Reply with quote  Mark this post and the followings unread

PHOBoS wrote:


up next: Blue Hell makes another wren module Laughing


Laughing

was thinking about that indeed .. for the new sieve module I made a couple of weeks ago .. 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 is a nice recuresive endless sequence .. so that could fit nicely into the concept.

Ok .. now listen Smile

_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Sun Aug 04, 2019 1:03 pm    Post subject: Reply with quote  Mark this post and the followings unread

BTW, the Hanoi towers are also related to Gray codes, for which there is an XOR trick (and dedicated chips too) ... so could do it with a handful of CMOS chips probably.

Also BTW .. the number sequence site linked in the previous post has the possebility to play a sequence as notes .. might be interesting.

This a surprisingly nice sequence to listen to too Smile

Ah and, indeed, a nice Sierpinsky relation - cool Smile

Nice one!

_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Mon Aug 05, 2019 1:47 pm    Post subject: Reply with quote  Mark this post and the followings unread

Hmm .. okay .. just a little more thread hijacking then ..

Thing is ... I need an ever upgoing sequence to fit the Sieve model ... now https://oeis.org/A101925 (1,2,4,5,8,9,11,12,16,17,19,20,23,...) happens to be such a sequence where the difference of the elements seems to form the Hanoi sequence ... aand .. the Sieve module does have a difference output Shocked

A101925 can be found as F0 (following one of the links on that sequence page) .. which is the first in a sequence F0, F1, F2 .. of sequences that are described as "meta fibonacci" ( http://webhome.cs.uvic.ca/~ruskey/Publications/MetaFib/MetaFib.html ) .. so must now try to understand the PDF from the last link .. and then could maybe make all the metafib( n) sequences.

BTW, my rationale for having a diff output was to get note lengths .. but it seems useful for generating other sequences too now Cool

_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Tue Aug 06, 2019 12:26 pm    Post subject: Reply with quote  Mark this post and the followings unread

feel free to hijack this thread as much as you want Very Happy
I wasn't really sure if I should post it in online music* or somewhere else as it is more about the idea than the music and it's nice
to see you can do something with it.
*moved it to DIY Hardware and Software

I actually hadn't read the wikipedia article just watched the video(s) and thought there might be a useful pattern in there.

I do like this part:
Quote:
There is a story about an Indian temple in Kashi Vishwanath which contains a large room with three time-worn posts in it, surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks in accordance with the immutable rules of Brahma since that time. The puzzle is therefore also known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle is completed, the world will end.

If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest number of moves it would take them 2⁶⁴ − 1 seconds or roughly 585 billion years to finish, which is about 42 times the current age of the Universe.


Interesting to see how the gray code and binary solutions are related and result in the same pattern. Not sure if I knew about the
XOR trick, if I did I must have forgotten. Makes me want to build a simple gray code counter, but you can have different gray codes.
They probably don't work as a solution for Hanoi but are still interesting. There is actually a whole rabbit hole to go down to and I
just came across the knights tour again. Oh and De Bruijn sequence which I looked up not so long ago.

Nice find with A101925. I had a quick look at that meta fibonacci pdf but I got lost in the forest of binary trees. I guess my neural
network needs more training to take it all in.

_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Wed Aug 07, 2019 7:15 am    Post subject: Reply with quote  Mark this post and the followings unread

I designed and tested a simple circuit that creates a (0), 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 sequence, and it can easily be extended.
I don't really like the (0) in there but it shouldn't be very hard to change that to another 4 (or whatever the highest number is).

However that is only part of it, there is also the sequence of the pegs/rods which for 4 discs is B, C, C, B, A, B, B, C, C, A, A, C, B, C, C.
I have been staring at it and trying to group things together by looking at the actual movement but haven't been able to find much logic behind it.


Ruler Sequence Generator.gif
 Description:
ruler sequence generator for 8 'discs'
 Filesize:  57.66 KB
 Viewed:  161 Time(s)
This image has been reduced to fit the page. Click on it to enlarge.

Ruler Sequence Generator.gif



_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Wed Aug 07, 2019 7:46 am    Post subject: Reply with quote  Mark this post and the followings unread

a bit of an explanation for the circuit above which relies on the fact that for the CD4043 (which has 4 flip-flops) SET is dominant.
This means that if both SET and RESET are high at the same time the flip/flop will be SET.

As mentioned before:
Quote:
To solve it you count in binary and the position of the bit that changes from 0 to 1 is the number of the disc (0 being the smallest) to move.
0001 move disc 0
0010 move disc 1
0011 move disc 0
0100 move disc 2
0101 move disc 0
0110 move disc 1
etc,

And that's what it does. Everytime one of the outputs of the CD4520 changes from 0 to 1 (and that is only ever 1 output at a time)
it sends a pulse to the corresponding flip-flop to SET it. At the same time all the other flip-flops are RESET by the CLK signal.
For reliability I used a smaller capacitor for the RESET inputs although I am not sure if that is even needed.
You could also use the same capacitor values and a smaller pulldown resistor.

Because only one of the outputs is high at a time you could connect them to a priority encoder (CD4532). (useful if you want to control a mux)

_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Wed Aug 07, 2019 10:03 am    Post subject: Reply with quote  Mark this post and the followings unread

Ah ok, so not even Gray codes need .. that probaly just is then to assure only one output changes on each count ... aand .. yup .. ruler function Cool .. I stumbled over something to determine the peg to move to too the other day but forgot where that was ... skimmed trough tens of pages and papers .. it seemed simple then .. but didnt really pay attention.

The priority encoder would complete the ruler, yes.

Another thing I stumbled over was the Hofstadter Q sequence .. that one is quasi random at times .. but as it is not non-decreasing (as in that the values can go both up and down) it is less suitable for what I have as a framework (but did still implement it, and it will still generate the correct numbers, but the order of them is lost in the underlying set of bits that I use (not in the sequence itself, but using the set of bits to speed up the playback algorithm)).

A function that results in the ruler function when taking the differences of the elements is pretty simple in code BTW ...

Code:

Out[ 0] = 0; // or 1 when 0 is annoying ;-)
Out[ 1] = 1;
Out[ n] = Out[ floor( 0.5 * n)] + n; // for n > 1

_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Wed Aug 07, 2019 11:59 am    Post subject: Reply with quote  Mark this post and the followings unread

Yeah the difference between plain binary and gray code is just that with binary you only check which bit has changed from 0 to 1,
while with gray code you check which bit has changed (can be 0 to 1 or 1 to 0). Checking only the 0 to 1 transition is a bit easier
to do in hardware. Could use an XOR with an RC filter (frequency doubler) to check both but would also need to create the gray code
first so that would just end up with more chips.

hmm, those Hofstadter sequences do look somewhat similar. Also look like a nightmare to implement in hardware.
I am actually considering writing it all in an EPROM Laughing

Code:

Out[ 0] = 0; // or 1 when 0 is annoying ;-)
Out[ 1] = 1;
Out[ n] = Out[ floor( 0.5 * n)] + n; // for n > 1

I wasn't familiar with 'floor', might come in useful someday. Doesn't really seem to do much special though except for negative numbers.
But you might be interested in those, otherwise a bit shift would have the same result, right ?. so Out[n] = Out[(n>>1)] + n;

ok let's see,..
out[0] = 0
out[1] = 1
out[2] = out[1] + 2 = 3
out[3] = out[1] + 3 = 4
out[4] = out[2] + 4 = 7
out[5] = out[2] + 5 = 8
out[6] = out[3] + 6 = 10
out[7] = out[3] + 7 = 11

ah neat, that's indeed pretty simple to do. I'd probably would have done that way to complicated. Embarassed

_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Wed Aug 07, 2019 12:31 pm    Post subject: Reply with quote  Mark this post and the followings unread

ok I see something. although I am not sure if it is going to help me any further.
The whole thing is probably (not surprisingly) recursive.

for 5 discs the sequence is: B C C B A B B C C A A C B C C B A B B A C A B B C C B A B B

or: B C C [B] A B B [C] C A A [C] B C C [B] A B B [A] C A A [B] B C C [B] A B B

or:
B C C [B]
A B B [C]
C A A [C]
B C C [B]
A B B [A]
C A A [B]
B C C [B]
A B B

and the letters between brackets are also in the order:
B C C [B]
A B B

_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Wed Aug 07, 2019 4:07 pm    Post subject: Reply with quote  Mark this post and the followings unread

ok that actually makes sense. I had already written it out as:
Code:
5 discs
------------------------------
00001: 0               B
00010: 1            C
00011: 0               C
00100: 2         B
00101: 0               A
00110: 1            B
00111: 0               B
01000: 3      C
01001: 0               C
01010: 1            A
01011: 0               A
01100: 2         C
01101: 0               B
01110: 1            C
01111: 0               C
10000: 4   B
10001: 0               A
10010: 1            B
10011: 0               B
10100: 2         A
10101: 0               C
10110: 1            A
10111: 0               A
11000: 3      B
11001: 0               B
11010: 1            C
11011: 0               C
11100: 2         B
11101: 0               A
11110: 1            B
11111: 0               B
------------------------------

which shows the movement of each disc and also makes it clear they move in a repeating pattern but in alternating directions.

The only thing I did different is grouping 2 discs together and that pattern of course also repeats but without the alternating.
Code:
6 discs
-----------------------
000001: 0         B
000010: 1         C
000011: 0         C
000100: 2      B
000101: 0         A
000110: 1         B
000111: 0         B
001000: 3      C
001001: 0         C
001010: 1         A
001011: 0         A
001100: 2      C
001101: 0         B
001110: 1         C
001111: 0         C
010000: 4   B
010001: 0         A
010010: 1         B
010011: 0         B
010100: 2      A
010101: 0         C
010110: 1         A
010111: 0         A
011000: 3      B
011001: 0         B
011010: 1         C
011011: 0         C
011100: 2      B
011101: 0         A
011110: 1         B
011111: 0         B
100000: 5   C
100001: 0         C
100010: 1         A
100011: 0         A
100100: 2      C
100101: 0         B
100110: 1         C
100111: 0         C
101000: 3      A
101001: 0         A
101010: 1         B
101011: 0         B
101100: 2      A
101101: 0         C
101110: 1         A
101111: 0         A
110000: 4   C
110001: 0         B
110010: 1         C
110011: 0         C
110100: 2      B
110101: 0         A
110110: 1         B
110111: 0         B
111000: 3      C
111001: 0         C
111010: 1         A
111011: 0         A
111100: 2      C
111101: 0         B
111110: 1         C
111111: 0         C
-----------------------

_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Wed Aug 07, 2019 6:24 pm    Post subject: Reply with quote  Mark this post and the followings unread

This shows even better how it is a simple repeating (and recursive) pattern, which is the same for all pegs just shifted.
For every extra 'level' (2 discs more) the same pattern repeats but a factor 4 slower.


Hanoi peg timing.gif
 Description:
 Filesize:  34.27 KB
 Viewed:  144 Time(s)
This image has been reduced to fit the page. Click on it to enlarge.

Hanoi peg timing.gif



_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Thu Aug 08, 2019 10:08 am    Post subject: Reply with quote  Mark this post and the followings unread

PHOBoS wrote:

But you might be interested in those, otherwise a bit shift would have the same result, right ?. so Out[n] = Out[(n>>1)] + n;


Yes .. Embarassed .. didnt even think of that .. but a bit shift will do exactly the right thing (for n >= 0).

Now to study your peg sequence ... Cool

_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Thu Aug 08, 2019 11:12 am    Post subject: Reply with quote  Mark this post and the followings unread

Blue Hell wrote:
Yes .. Embarassed .. didnt even think of that .. but a bit shift will do exactly the right thing (for n >= 0).

heh, shoudn't that be (for n>0) ? otherwise it will use out[0] which doesn't have a value assigned yet, unless it's 0 by default.


here's a more complete timing diagram for a game of 6 discs. (I am very tempted to do it in a spreadsheet with some colors colors )


Hanoi timing.gif
 Description:
 Filesize:  68.82 KB
 Viewed:  143 Time(s)
This image has been reduced to fit the page. Click on it to enlarge.

Hanoi timing.gif



_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Thu Aug 08, 2019 11:21 am    Post subject: Reply with quote  Mark this post and the followings unread

Blue Hell wrote:
I stumbled over something to determine the peg to move to too the other day but forgot where that was ... skimmed trough tens of pages and papers .. it seemed simple then .. but didnt really pay attention.


Its on wikipedia .. wikip-idea ... hmm : https://en.wikipedia.org/wiki/Tower_of_Hanoi#Binary_solution and also https://en.wikipedia.org/wiki/Tower_of_Hanoi#Gray-code_solution

But still seems to complicated for logic .. nice for puters tho.

_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Thu Aug 08, 2019 11:36 am    Post subject: Reply with quote  Mark this post and the followings unread

PHOBoS wrote:
heh, shoudn't that be (for n>0) ? otherwise it will use out[0] which doesn't have a value assigned yet, unless it's 0 by default.


Oh, I was referring the floor operation only.

The sequence needs two pre-initialized elements BTW.

_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Thu Aug 08, 2019 12:52 pm    Post subject: Reply with quote  Mark this post and the followings unread

Ok, I think I've got them meta fibonacci sequence tree thingies nailed ...

We have:

Code:
a[ n] = a[ n - s - a[ n - 1]] + a[ n - s - 1 - a[ n - 2]]; // for n > s + 1
a[ n] = 1; // for n <= s + 1


as the starting sequences, s is the 'order' in this. Then the sequence of differences is obtained as :

Code:
d[ n] = a[ n + 1] - a[ n];


And those sequences have only zeros and ones - or so it seems. Now from d[ n] we construct p[ n] by looking at the positions of the 1's in d[ n] while skipping the zeros, going from left to right first one having index 0. The index of the next '1' then is the next number to be added to p[ n].

For s = 0 we get as the first few terms:

Code:
a = { 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10 ...}
d = { 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1,  0 ...}
p = { 1, 3, 4, 7, 8, 10, 11, 15, 16 ...}


And then the diffrences of p will give the ruler function again, the one this whole thing started with ...

Code:
{ 2, 1, 3, 1, 2, 1, 4, 1 ...}


And .. we can now use s to get other sequences with similar properties.

s = 1 yields:

Code:
a = { 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 9, 10, 10, 11 ...}
d = { 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1 ...}
p = { 2, 5, 6, 10, 11, 13, 14, 17, 18, 20 ...}


with diffrences :

Code:
{ 3, 1, 4, 1, 2, 1, 3, 1, 2 ...}


Which just seems to be a shifted ruler Shocked

Anyways .. this was computed manually .. will now write a program for it to see how boring it gets for larger s. For s = 0 there is the simpler algorithm as mentioned earlier in this thread:

Code:
p[ n] = p[ n >> 1] + n;

_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Thu Aug 08, 2019 2:30 pm    Post subject: Reply with quote  Mark this post and the followings unread

Here are some values for s = 0 .. 9, r is the resulting ruler, d is not listed as I'm not computing that sequence.

Code:

s = 0

  a = '{ 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 33, 34, 34, 35, 36, 36, 36, 37, 38, 38, 39, 40, 40, 40, 40, 41, 42, 42, 43, 44, 44, 44, 45, 46, 46, 47, 48, 48, 48, 48, 48, 49, 50, 50, 51, 52, 52, 52, 53}'
  p = '{ 1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19, 22, 23, 25, 26, 31, 32, 34, 35, 38, 39, 41, 42, 46, 47, 49, 50, 53, 54, 56, 57, 63, 64, 66, 67, 70, 71, 73, 74, 78, 79, 81, 82, 85, 86, 88, 89, 94, 95, 97, 98}'
  r = '{ 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3}'



Code:

s = 1

  a = '{ 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 32, 33, 34, 34, 35, 36, 36, 36, 37, 38, 38, 39, 40, 40, 40, 40, 41, 42, 42, 43, 44, 44, 44, 45, 46, 46, 47, 48, 48, 48, 48, 48, 49}'
  p = '{ 2, 5, 6, 10, 11, 13, 14, 19, 20, 22, 23, 26, 27, 29, 30, 36, 37, 39, 40, 43, 44, 46, 47, 51, 52, 54, 55, 58, 59, 61, 62, 69, 70, 72, 73, 76, 77, 79, 80, 84, 85, 87, 88, 91, 92, 94, 95}'
  r = '{ 3, 1, 4, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7}'



Code:

s = 2

  a = '{ 1, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 33, 34, 34, 35, 36, 36, 36, 37, 38, 38, 39, 40, 40, 40, 40, 41, 42, 42, 43, 44, 44, 44, 45, 46, 46, 47}'
  p = '{ 3, 7, 8, 13, 14, 16, 17, 23, 24, 26, 27, 30, 31, 33, 34, 41, 42, 44, 45, 48, 49, 51, 52, 56, 57, 59, 60, 63, 64, 66, 67, 75, 76, 78, 79, 82, 83, 85, 86, 90, 91, 93, 94, 97, 98}'
  r = '{ 4, 1, 5, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 5}'



Code:

s = 3

  a = '{ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 34, 34, 35, 36, 36, 36, 37, 38, 38, 39, 40, 40, 40, 40, 41, 42, 42, 43, 44}'
  p = '{ 4, 9, 10, 16, 17, 19, 20, 27, 28, 30, 31, 34, 35, 37, 38, 46, 47, 49, 50, 53, 54, 56, 57, 61, 62, 64, 65, 68, 69, 71, 72, 81, 82, 84, 85, 88, 89, 91, 92, 96, 97, 99}'
  r = '{ 5, 1, 6, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 9, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 5}'



Code:

s = 4

  a = '{ 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 34, 34, 35, 36, 36, 36, 37, 38, 38, 39, 40, 40, 40, 40, 41}'
  p = '{ 5, 11, 12, 19, 20, 22, 23, 31, 32, 34, 35, 38, 39, 41, 42, 51, 52, 54, 55, 58, 59, 61, 62, 66, 67, 69, 70, 73, 74, 76, 77, 87, 88, 90, 91, 94, 95, 97, 98}'
  r = '{ 6, 1, 7, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 9, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 10, 1, 2, 1, 3, 1, 2, 1, 7}'



Code:

s = 5

  a = '{ 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 34, 34, 35, 36, 36, 36, 37}'
  p = '{ 6, 13, 14, 22, 23, 25, 26, 35, 36, 38, 39, 42, 43, 45, 46, 56, 57, 59, 60, 63, 64, 66, 67, 71, 72, 74, 75, 78, 79, 81, 82, 93, 94, 96, 97}'
  r = '{ 7, 1, 8, 1, 2, 1, 9, 1, 2, 1, 3, 1, 2, 1, 10, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 11, 1, 2, 1, 9}'



Code:

s = 6

  a = '{ 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 34}'
  p = '{ 7, 15, 16, 25, 26, 28, 29, 39, 40, 42, 43, 46, 47, 49, 50, 61, 62, 64, 65, 68, 69, 71, 72, 76, 77, 79, 80, 83, 84, 86, 87, 99}'
  r = '{ 8, 1, 9, 1, 2, 1, 10, 1, 2, 1, 3, 1, 2, 1, 11, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 12, 8}'



Code:

s = 7

  a = '{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33}'
  p = '{ 8, 17, 18, 28, 29, 31, 32, 43, 44, 46, 47, 50, 51, 53, 54, 66, 67, 69, 70, 73, 74, 76, 77, 81, 82, 84, 85, 88, 89, 91, 92}'
  r = '{ 9, 1, 10, 1, 2, 1, 11, 1, 2, 1, 3, 1, 2, 1, 12, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 16}'



Code:

s = 8

  a = '{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33}'
  p = '{ 9, 19, 20, 31, 32, 34, 35, 47, 48, 50, 51, 54, 55, 57, 58, 71, 72, 74, 75, 78, 79, 81, 82, 86, 87, 89, 90, 93, 94, 96, 97}'
  r = '{ 10, 1, 11, 1, 2, 1, 12, 1, 2, 1, 3, 1, 2, 1, 13, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 12}'



Code:

s = 9

  a = '{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31}'
  p = '{ 10, 21, 22, 34, 35, 37, 38, 51, 52, 54, 55, 58, 59, 61, 62, 76, 77, 79, 80, 83, 84, 86, 87, 91, 92, 94, 95, 98, 99}'
  r = '{ 11, 1, 12, 1, 2, 1, 13, 1, 2, 1, 3, 1, 2, 1, 14, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 11}'



And some code snippets for it:

Code:

  TSieveMetaFibonacci = class( TSievePreExtendable)
  private
    FOrder : Integer;
    FAN    : TSieveSequence;
  private
    procedure   AddAN( aValue: Integer);
  protected
    function    CreateNextElement: Integer;                                                                    override;
    procedure   Initialize;                                                                                    override;
  public
    constructor Create( anOrder: Integer);
    function    Dump: string;                                                                                  override;
    function    DumpAN: string;
  public
    property    Order: Integer read FOrder;
  end;


    procedure   TSieveMetaFibonacci.AddAN( aValue: Integer);
    begin
      SetLength( FAN, Length( FAN) + 1);
      FAN[ Length( FAN) - 1] := aValue;
    end;


    function    TSieveMetaFibonacci.CreateNextElement: Integer; // override;
    var
      Found : Boolean;
      Delta : Integer;
    begin
      Found  := False;
      Result := 1;

      while not Found
      do begin
        AddAN( FAN[ Length( FAN) - Order - FAN[ Length( FAN) - 1]] + FAN[ Length( FAN) - Order - 1 - FAN[ Length( FAN) - 2]]); // Next a[ n]
        Delta := FAN[ Length( FAN) - 1] - FAN[ Length( FAN) - 2];                                                              // Next d[ n]

        if   Delta = 1
        then begin
          Result := Length( FAN) - 2; // Next element for p[ n]
          Found  := True;
        end;
      end;
    end;


    procedure   TSieveMetaFibonacci.Initialize; // override;
    var
      i : Integer;
    begin
      for i := 0 to Order + 1
      do  AddAN( 1);

      FLastElement := 0;
      SetLength( FData, Order + 1);
    end;

_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Thu Aug 08, 2019 2:34 pm    Post subject: Reply with quote  Mark this post and the followings unread

And now to find an expression for the peg sequence Laughing
_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Thu Aug 08, 2019 3:17 pm    Post subject: Reply with quote  Mark this post and the followings unread

Quote:

s = 1 yields:

Code:
a = { 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 9, 10, 10, 11 ...}
d = { 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1 ...}
p = { 2, 5, 6, 10, 11, 13, 14, 17, 18, 20 ...}


with diffrences :

Code:
{ 3, 1, 4, 1, 2, 1, 3, 1, 2 ...}



Which just seems to be a shifted ruler Shocked

isn't math fun
looks like it does a bit more than shifting though, well it does shift something.



I came up with a different circuit for the ruler sequence. It's not an improvement but I might as well post it anyway.
note: U2a isn't really needed


Ruler Sequence Generator V2.gif
 Description:
 Filesize:  83.15 KB
 Viewed:  150 Time(s)
This image has been reduced to fit the page. Click on it to enlarge.

Ruler Sequence Generator V2.gif



_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Fri Aug 09, 2019 11:17 am    Post subject: Reply with quote  Mark this post and the followings unread

I've spent today looking for an easy way to generate the, or rather a - as there are different possebilities, peg sequence, but ended up just implementing the recursive Tower function.

This won't be of any help for a hardware implementation, but it will do for code ... except that also I did not find a solution for not having to recalculate earlier elements when a longer sequence gets requested .. all other sequences I have do have this property of extensibility .. would be cool to have that for the peg sequence too.

Code snippets :

Code:

    procedure   TSieveHanoiPegs.StorePeg( aPeg: Integer);
    begin
      AddAN( aPeg);
      AddPN( FPN[ Length( FPN) - 1] + aPeg);
    end;


    procedure   TSieveHanoiPegs.Tower( aDepth, zero, one, two: Integer);
    begin
      if   aDepth > 0
      then begin
        if   aDepth = 1
        then StorePeg( two)
        else begin
          Tower( aDepth - 1, zero, two, one);
          StorePeg( two);
          Tower( aDepth - 1, one, zero, two);
        end;
      end;
    end;


To get nicer sequeences it should be called with swapped argument for values of aDepth, as in:

Code:

    procedure   TSieveHanoiPegs.StartTower( aDepth: Integer);
    begin
      if aDepth > FLatestDepth
      then begin
        SetLength( FAN, 0);
        SetLength( FPN, 0);
        AddPN( 0);

        if   FOddSwap                   // Every sequence will be a prefix of the following one {1}, [1,2,2],{1,2,2,1,0,1,1} etc.
        then begin
          if   Odd( aDepth)
          then Tower( aDepth, 0, 2, 1)  // When odd  peg 1 is the destination and 2 is the spare
          else Tower( aDepth, 0, 1, 2); // When even peg 2 is the destination and 1 is the spare
        end
        else   Tower( aDepth, 0, 1, 2); // Alternating prefixes {2}, [1,2,2], [2,1,1,2,,0,2,2] etc

        FLatestDepth := aDepth;
      end;
    end;


Sequence snippets (I currently have them up to d = 9, but they tend to get very long) :

With proper prefixes (swapping)

Code:

d = 1
a = { 1}
p = { 0, 1}


Code:

d = 2
a = { 1, 2, 2}
p = { 0, 1, 3, 5}


Code:

d = 3
a = ( 1, 2, 2, 1, 0, 1, 1)
p = ( 0, 1, 3, 5, 6, 6, 7, 8)


Code:

d = 4
a = ( 1, 2, 2, 1, 0, 1, 1, 2, 2, 0, 0, 2, 1, 2, 2)
p = ( 0, 1, 3, 5, 6, 6, 7, 8, 10, 12, 12, 12, 14, 15, 17, 19)


Code:

d = 5
a = ( 1, 2, 2, 1, 0, 1, 1, 2, 2, 0, 0, 2, 1, 2, 2, 1, 0, 1, 1, 0, 2, 0, 0, 1, 1, 2, 2, 1, 0, 1, 1)
p = ( 0, 1, 3, 5, 6, 6, 7, 8, 10, 12, 12, 12, 14, 15, 17, 19, 20, 20, 21, 22, 22, 24, 24, 24, 25, 26, 28, 30, 31, 31, 32, 33)



And non-swapped

Code:

d = 1
a = { 2}
p = { 0, 2}


Code:

d = 2
a = { 1, 2, 2}
p = { 0, 1, 3, 5}


Code:

d = 3
a = ( 2, 1, 1, 2, 0, 2, 2)
p = ( 0, 2, 3, 4, 6, 6, 8, 10)


Code:

d = 4
a = ( 1, 2, 2, 1, 0, 1, 1, 2, 2, 0, 0, 2, 1, 2, 2)
p = ( 0, 1, 3, 5, 6, 6, 7, 8, 10, 12, 12, 12, 14, 15, 17, 19)


Code:

d = 5
a = ( 2, 1, 1, 2, 0, 2, 2, 1, 1, 0, 0, 1, 2, 1, 1, 2, 0, 2, 2, 0, 1, 0, 0, 2, 2, 1, 1, 2, 0, 2, 2)
p = ( 0, 2, 3, 4, 6, 6, 8, 10, 11, 12, 12, 12, 13, 15, 16, 17, 19, 19, 21, 23, 23, 24, 24, 24, 26, 28, 29, 30, 32, 32, 34, 36)

_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Fri Aug 09, 2019 1:12 pm    Post subject: Reply with quote  Mark this post and the followings unread

dwarf ~Time for a tale from the Enchanted Forest of (binary) 3's ~ dwarf

Once upon a time De La Soul taught us that * 3 is a magic number *. love Peace flower

- Every disc moves in a 3 step sequence across the 3 pegs, either CW (B,C,A) or CCW (C,B,A) at a different rate (/1, /2, /4, /8 etc).

One of my initial ideas for a circuit was to add a 3-step counter to each disc output, counting up or down depending on the disc, and processing
it further to get the 3 peg sequences. This is similar to how I did it in code. The location of each disc is stored in an array and it's value changed
depending on its position. I didn't really like the idea of needing so many counters though and thought that there must be an easier solution.
So I tried to find another pattern. Which led me to the recursive B C C [x] A B B [x] C A A [x] sequence.
I did have some ideas on how to do it with chained muxes and/or shiftregisters but it still seemed to get quite complex. Writing down the timing
diagrams didn't bring me much closer either, although it did make it easier to see what's happening and I did get the other Sequence Generator
circuit from it.

Something else I do once in a while to find a solution is to simulate a circuit with Digital Works. It's not the greatest software out there
and it definitely has some flaws but it's fairly easy to work with. One advantage is that it's easy to see the status (low/high) of all the connections
so you can see what's exactly happening in the circuit at any given time. I started with the simulation of the Ruler Sequence Generator (V2, as the
other one isn't possible in Digital Works).

I wanted to go back to my initial 3-step counter idea to see if I could do something similar but easier, maybe using only 1 or 2 counters and derive
the other (slower) 3-step sequences from it. So I added a 3-step counter with its clock input connected to the Disc 0 output which resulted in the
peg position sequence for Disc 0 as expected. The first thing I noticed was that I didn't have to use the Disc 0 output but could connect the clock input
of the 3-step counter directly to the divider output*. The Ruler Sequence Generator (RSG) creates seperate pulses for each low to high transition
of the divider outputs, but the counter only reacts to transitions anyway. (* I later connected it to the clk signal instead)

This gave me the position of Disc 0 but what I need is the movement. In other words I don't need to know which peg it is on at all times, I only need
to know which peg it is moved to when it is moved. Well, the RSG tells me exactly when the Disc is moved and the counter gives me which peg it is on
so I just need to combine them. And indeed, using 3 AND gates, one for each output of the 3-step counter, connected to the Disc 0 output gave me the
movement of Disc 0. The idea was to do this for each disc which results in 3 outputs per disc (1 for each peg) and then use 3 OR gates to combine the
outputs for each peg to get the final 3 peg outputs.

So onwards we travel with our next Disc, 1.

I added 3 more AND gates, this time connected to the Disc 1 output of the RSG. Now I needed a slower 3 step counter. The direction should be the opposite
but that can easily be done by just swapping 2 outputs. I did some tests with a standard binary divider hoping I would be able to get all the slower 3-step
sequences out of it although I was pretty sure that wouldn't work, and indeed it didn't. That's when the magical elf appeared,.. or actually I connected
something without really thinking about it. Instead of adding another counter I just connected the AND gates to the already existing 3-step counter.
The elf chuckled while I looked on in amazement (at the simulated circuit, not the elf). Right in front of me Disc 1 was moving as it should, or at least the
direction and tempo were ok I just needed to shuffle the outputs a bit to get it on the correct pegs.

Could it really be that easy ?!

I carefully added Disc 2 to the circuit using 3 more AND gates and it also behaved as it should. Disc 3, 4 and 5 followed (the simulated RSG has 6 outputs)
and they all played along to the rules of Hanoi. Of course I now had 18 outputs (3 pegs for each disc) which is great but I just wanted the 3 peg sequences.
So I added 3 (6-input) OR gates to combine the outputs for each peg and that gave me the final 3 peg sequences.

I was happy that it worked but it did look a bit ridiculous with 3 AND gates for each disc, a total of 18 for this circuit (and 24 for the 8 disc version).
I labeled all the AND gates with an A, B or C so I could easily see which peg they were connected to and that's when I noticed something. Each set of
3 AND gates was connected to the corresponding disc output of the RSG but also all the AND gates for the odd discs had their other inputs connected
in the same order to the 3-step counter and the same was true for the even discs. This makes sense of course as all the odd discs move in one direction
and all the even discs in the opposite direction.

Since only 1 Disc output is high at any given time I combined the odd and even ones using 2 (3-input) OR gates which results in two outputs, one for
the odd discs and one for the even discs. I combined each one with the outputs of the 3-step counter using a total of 6 AND gates. This resulted in 6
outputs; odd discs peg A, even discs peg A, odd discs peg B, even discs peg B, odd discs peg C, even discs peg C. So all that was left to do was to combine
the even and odd outputs for each peg using 3 OR gates. Not only does this use less gates it can also be easily extended. For every disc, one of the OR
gates that combine the odd/even discs needs an extra input. Since this can be done with diodes that's just 1 diode extra per disc. Of course the RSG itself
needs some extra chips too for more discs.

And that's how I solved the Tower of Hanoi with the magic of 3's Very Happy


I drew another timing diagram, this time with a 3-step counter (and only 4 discs), which makes it clear why it works.

oh and I had 3 gates left (U5a, U6a, U7a) so I used those to switch the peg outputs between long or short mode. In short mode the outputs have the
same duty-cycle as the clock signal while in long mode they stay on for 1 full clock period. As a result if a peg output is high for 2 or more consecutive
steps it will create seperate short pulses in short mode, and one long pulse in long mode. I was thinking of using the enable inputs of the CD4043's
for this but they have 3-state ouputs so it depends a bit on what you connect it to if that would work. Also I connected the 3-step counter directly
to the clk signal instead of the first division. Works the same except the direction of all the discs get reversed. Hmm, I might aswell add another switch.
I will look into it a bit more to see if I can simplify it even further and have a another look at the other video.


Hanoi timing 2.gif
 Description:
the magic of 3's
 Filesize:  67.23 KB
 Viewed:  136 Time(s)
This image has been reduced to fit the page. Click on it to enlarge.

Hanoi timing 2.gif



Hanoi Sequencer.gif
 Description:
(not tested)
 Filesize:  90.33 KB
 Viewed:  147 Time(s)
This image has been reduced to fit the page. Click on it to enlarge.

Hanoi Sequencer.gif



_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider

Last edited by PHOBoS on Sat Aug 10, 2019 9:59 am; edited 2 times in total
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Fri Aug 09, 2019 2:52 pm    Post subject: Reply with quote  Mark this post and the followings unread

party time!

Brilliant Idea

I had been looking at 3 too .. as in ternary numbers .. or do stuff modulo 3 ... but it didnt bring me anything - glad it did so for you Smile

_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
PHOBoS



Joined: Jan 14, 2010
Posts: 4723
Location: Moon Base
Audio files: 641

PostPosted: Sat Aug 10, 2019 8:50 am    Post subject: Reply with quote  Mark this post and the followings unread

Blue Hell wrote:
... except that also I did not find a solution for not having to recalculate earlier elements when a longer sequence gets requested .. all other sequences I have do have this property of extensibility .. would be cool to have that for the peg sequence too.


That should actually be pretty easy now, well at least for the standard solution with the shortest number of steps .
The numbering might be off to what you're doing but I am going from how it works in the simulated circuit.

At the start position (step 0) it has the following ouputs:
- disc outputs (0..7) = all 0
- peg outputs (A,B,C) = all 0
- binary counter (0..255) = 0
- 3-step counter (0,1,2) = 0


The output from the 3-step counter can easily be calculated with i % 3, where i is the current step.

for the even discs this output translates to:
0 = peg C
1 = peg B
2 = peg A

for the odd discs this output translates to:
0 = peg B
1 = peg A
2 = peg C

hmm, I only notice now that they are in the same order just shifted, interesting. Unless I made a mistake somewhere.
The order does seem to be different from what I have in the circuit (will look into it later).
edit: I had swapped some connections. uploaded a fixed version

For every step you know the disc (ruler sequence) and the output from the 3-step counter,
from that you can now easily determine the peg.

examples:
------------
step = 17
- output from the 3-step counter = 17 % 3 = 2
- current disc = output from the ruler sequence for step 17 = 0
- 0 is an even disc and for even discs: 2 = peg A
- so at step 17 disc 0 is moved to peg A

step = 32
- output from the 3-step counter = 32 % 3 = 2
- current disc = output from the ruler sequence for step 32 = 5
- 5 is an odd disc and for odd discs: 2 = peg C
- so at step 32 disc 5 is moved to peg C

step = 42
- output from the 3-step counter = 42 % 3 = 0
- current disc = output from the ruler sequence for step 42 = 1
- 1 is an odd disc and for odd discs: 0 = peg B
- so at step 42 disc 1 is moved to peg B

_________________
"My perf, it's full of holes!"
http://phobos.000space.com/
SoundCloud BandCamp MixCloud Stickney Synthyards Captain Collider

Last edited by PHOBoS on Sat Aug 10, 2019 12:26 pm; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger
Blue Hell
Site Admin


Joined: Apr 03, 2004
Posts: 23010
Location: The Netherlands, Enschede
Audio files: 243
G2 patch files: 319

PostPosted: Sat Aug 10, 2019 11:31 am    Post subject: Reply with quote  Mark this post and the followings unread

That is quite elegant Cool
_________________
Jan
also .. could someone please turn down the thermostat a bit.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic Moderators: jksuperstar, Scott Stites, Uncle Krunkus
Page 1 of 2 [38 Posts]
View unread posts
View new posts in the last week
Goto page: 1, 2 Next
Mark the topic unread :: View previous topic :: View next topic
 Forum index » DIY Hardware and Software
Jump to:  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
e-m mkii

Please support our site. If you click through and buy from
our affiliate partners, we earn a small commission.


Forum with support of Syndicator RSS
Powered by phpBB © 2001, 2005 phpBB Group
Copyright © 2003 through 2009 by electro-music.com - Conditions Of Use