Re: Collatz at the Hilbert Hotel

mensanator_at_aol.compost
Date: 01/06/05 

Date: 5 Jan 2005 16:42:13 -0800

Michael Collins wrote:
> First a brief story and then the maths to go with it. I'll try to
keep
> it as concise as possible.
>
> 1. Story
> The Hilbert hotel has recently been refurbished so that each room now
> has a 'Godel duplicator', a machine that can be used to duplicate
> anything put into it.
> Unfortunately, in order to create so many duplicators they had to
> duplicate the original one.
> As luck would have it was just able to fit into itself so it was
copied
> and eventually each room got one.
> Before the system was, itself, copied it had been tested by
duplicating
> a person. The system tries to stop this from happening by creating
> Drones that don't think, only obeying simple fixed rules. Drones are
> easily destroyed using a tool called a 'bopper'.
> Unfortunately there's a glitch in the system that means that at 9am
> every day some of these machines will create new Drones which, by
> following these rules generally clog up the hotel before finally
being
> rounded up by all the staff and 'bopped'.
> The Manager of the hotel is distressed by this as it has been causing
no
> end of problems for the guests.
> He has no choice but to close the hotel and call in the "Collatz
> Exterminators" who specialise in drone 'bopping' and other such
> problems.
> Mr Ulam Collatz, the owner of the company himself comes along (in the
> hail) and observes the first day's events in order to work out the
rules
> of Drone behaviour.
> After the staff have rounded up the last straggler - there's always
one
> - he tells the hotel manager that he'll be quite happy to come back
the
> next day and get rid of them all.
> The following day he arrives just before 9 and as the drones appear
he
> steps into the first room with a drone in, quickly bops it and is
ready
> to get rid of all the others.
>
> The Rules are as follows:
> The entity (Collatz or Drone) in the lowest room moves to the higher
> room two along.
> Every other entity duplicates itself and quickly sends the new
duplicate
> into the next higher room.
> At this point in time the fighting breaks out, any time a Drone
enters a
> room that's already occupied there will be fight and one of them will
> 'pop' with the victor moving up a room to (possibly) fight all over
> again.
> Being as Collatz is a proper human (armed with a bopper no less) he's
> able to win every duel.
> As this is repeated over and over, Collatz always emerges the victor.
>
> Maths:
> Obviously this comes from the Collatz conjecture, the well known
> iterative Diophantine equation.
> The original Collatz conjecture is that any positive integer, n,
> operated on iteratively eventually reaches 1.
> The rules for the iteration are that of n is even n --> n/2 and that
if
> n is odd n -> 3n+1.
> This is more usually shown as
> F(n) = 3n +1 if n=1 (mod2)
> n/2 if n=0 (mod2)
>
> If we look at the binary representation of n with the lowest bit on
the
> left and increasing powers of 2 represented to the right then n/2 is
> purely shifting n left one and this will keep repeating until the
lowest
> bit is a 1 and therefore become 1 mod2.

Why are you doing your binary numbers backwards? You're a disgrace to
the IT community. ;)

> As an example 12 can be represented as 0011 ( 0x2^0 + 0x2^1 + 1x2^2 +
> 1*2^3) = 4 + 8 and the next two iterations become 011 and then 11 in
> binary, six and three respectively.
> n = 3 -> n' = 10 ( n = 11 -> n' = 0101 in binary)
>
> If, rather than n -> 3n + 1 we express the 3n+1 portion of the
collatz
> conjecture as n -> 3n + 2^x with 2^x being the lowest non-zero power
of
> two in the binary representation of n then we can do away with the
n/2
> section and, rather than the Colatz conjecture stating that the
result
> must eventually reach 1 we can instead state an equal conjecture that
> iterating n->3n + 2^x eventually reaches 2^y.
> F(n) = 3n + 2^x
> n original(bin) 3n + 2^x variant
> 3 11 11
> 10 0101 0101
> 5 101 -
> 16 00001 000001

If I'm following this correctly, at each iteration, you multiply
by 3 and increment by the least significant 1 (sorry, there's only
one way to do binary numbers and that's the right way):

' 11 n
' 110 n*2
'----
'1001 n*3
' 1 inc by 2**0
'----
'1010
'
'
' 1010 n
' 10100 n*2
' -----
' 11110 n*3
' 10 inc by 2**1
'------
'100000

And you stop at a power of two.

That's an interesting approach. What you are doing is preserving
the most significant bit pattern and remembering all the 0s that
would normally be discarded by the n/2 operation.

> The strength in this is that we have a steadily increasing sequence
that
> doesn't have the n/2 section giving these additional iterations and
we
> have a sequence that terminates in less iterations as well.

There's another way to accomplish the same objective. If the
original Collatz sequence were to show only the odd numbers,
you would also preserve the most significant bit pattern only
without all the trailing 0s.

>
> I've not looked at whether this gives any better relationship between
> the chosen starting number and the number of iterations until the
result
> reaches 2^y.

Your iteration count would be the same as the regular Collatz
count of 3n+1 operations.

> The chosen starting number isn't relevant, the number of digits
between
> the starting and ending 1 in the binary representation are relevant.
> 1010001100001 will behave exactly the same as
> 000000000000001010001100001 without having to be reduced to an odd
> number first.

As you have noted, what's important is the most significant
bit pattern sequence. Patterns are what drives Collatz,
not values. If you place your numbers on a tree, the trunk
would be the powers of 2 and each odd number starts a new
branch. All numbers on the same branch have the same most
significant bit pattern, just different numbers of least
significant 0s. If I define ORDER as the number of branches
from n to the trunk, then 1010001100001 and
000000000000001010001100001 have the same ORDER as they are
both on the same branch.

Although n may "hailstone" (rise and fall in value) ORDER
always decreases in a Collatz sequence. And since all ORDERs
are finite, the sequence always terminates.

>
> In effect the conjecture is getting us to multiply n by 3 and then
add
> an ever increasing 2^x
> What is in effect happening is that the lowest bit is being
multiplied
> by 4 and shifting to the right by 2 in the binary representation (
> multiply by 3 and then add the 2^n) and the rest of n is being
> multiplied by 3
> This x3 in binary represents taking the original part of n (not
> including the lowest bit) and then adding itself shifted to the right
by
> one ( n + 2n to end up multiplying by 3).
> You can only ever add zeroes to the left of the sequence as
> multiplication of integers (in any number base) can never affect
digits
> lower than those represented in the numbers being multiplied.
> All this means that no bit can ever appear in subsequent n' lower
than
> the lowest bit set in n. (lower than 2^(x+1) actually as the lowest
bit
> is multiplied by 4.)
>
> I'm not sure how much sense the above couple of paragraphs make as
I'm
> more of an IT person than a mathematician but I liked working with
this
> and hadn't seen this being done before and besides I liked the story.
>
> If we show subsequent iterations starting from a large number the
> trailing edge always seems to be advancing faster than the leading
edge.

Yes, you are basically remembering all the 0s you would have
stripped away by n/2 operations. There will always be more n/2
than 3n+1 iterations.

>
> Obviously, with the story I could have kept the original n/2
iteration
> and had Collatz coming out of room 1 at the end every time but I'd
been
> using the maths to get rid of the modular arithmetic so didn't want
to
> bring it back in even though it does make the story a lot nicer.
>
> The Drones bopping each other is binary addition leading to them to
move
> into the next highest room (a carry).
> The duplication and sending the duplicate into the next highest room
us
> multiplying by three.
> The entity in the lowest room moving two rooms up is the lowest bit
> being multiplied by four.
> The door number for each room represents the power of two in
binary(if
> you have a room 0 anyway).
>
> As an addendum if the duplicators are programmed so that the creation
of
> the Drones is a function of the neighbouring rooms and have Drones
using
> similar rules about whether to remain in the room or leave (which
must
> be nicer than being 'bopped') then Hilbert's Hotel will instead
function
> as a CA and, from the CAs in Wolframm's ANKOS, the hotel can be made
to
> function as a Turing Machine.
>
> We could also have the hotel not being allowed to have more than 9
> entites in each room for example with 8 being requested to leave and
the
> remaining one moving up a room to represent base10.
>
> This could also lead to arbitrary bases with different rooms having
> different maximums based on whatever rules we choose to assign
filling
> electron orbitals or keep adding people to the next room until a
prime
> is reached and then start on the next room etc.
>
> Any comments on this will be gratefully received.

Here's my Python implementation of your Hilbert algorithm
vs my Collatz algorithm that shows only odd numbers:

(if Google fucks this up, try viewing original. the # at
the start of each line is there to preserve leading whitespace)

#import gmpy
#
#def collatz(b):
# print b,gmpy.digits(b,2)
# # print b and b in binary
# collatz_hotel.append(gmpy.digits(b,2))
# # check the binary version into the hotel
# while b>1:
# # collatz stops at 1
# z = gmpy.scan1(b)
# # find least significant 1 bit
# if z==0:
# b = b*3 + 1
# # stadard collatz when odd
# else:
# b = b/(2**z)
# # do all the n/2 iterations in a single step
# print b,gmpy.digits(b,2)
# # only odd numbers are printed
# collatz_hotel.append(gmpy.digits(b,2))
#
#
#def hilbert(b):
# # hilbert stops on a power of 2
# while gmpy.popcount(b)>1:
# # popcount is count of 1 bits
# print b,gmpy.digits(b,2)
# hilbert_hotel.append(gmpy.digits(b,2))
# # check this one into the hilbert hotel
# z = gmpy.scan1(b)
# b = b*3 + 2**z
# # increment by least signifcant 1 bit
# print b,gmpy.digits(b,2)
# hilbert_hotel.append(gmpy.digits(b,2))
#
#
#
#
#hilbert_hotel = []
#collatz_hotel = []
#
#b = 27
#
#hilbert(b)
#print
#collatz(b)
#print
#for i in range(len(hilbert_hotel)):
# # now that both hotels are full
# print hilbert_hotel[i]
# # compare hilbert resident
# print collatz_hotel[i]
# # to collatz resident in room number
# print

Here's the sample run showing the Hilbert algorithm.
Note that the most significant bit pattern "hailstones"
while the least significant 0s simply accumulate.

27 11011
82 1010010
248 11111000
752 1011110000
2272 100011100000
6848 1101011000000
20608 101000010000000
61952 1111001000000000
186368 101101100000000000
561152 10001001000000000000
1687552 110011100000000000000
5079040 10011011000000000000000
15269888 111010010000000000000000
45875200 10101111000000000000000000
137887744 1000001110000000000000000000
414187520 11000101100000000000000000000
1243611136 1001010001000000000000000000000
3732930560 11011110100000000000000000000000
11207180288 1010011100000000000000000000000000
33688649728 11111011000000000000000000000000000
101200166912 1011110010000000000000000000000000000
303868936192 100011011000000000000000000000000000000
912680550400 1101010010000000000000000000000000000000
2740189134848 100111111000000000000000000000000000000000
8229157339136 1110111110000000000000000000000000000000000
24704651886592 101100111100000000000000000000000000000000000
74148315398144 10000110111000000000000000000000000000000000000
222513665671168 110010100110000000000000000000000000000000000000
667678435966976 10010111110100000000000000000000000000000000000000
2003310185807872 111000111100000000000000000000000000000000000000000
6012129580679168 10101010111000000000000000000000000000000000000000000
18040786788548608
1000000000110000000000000000000000000000000000000000000
54131156458668032
11000000010100000000000000000000000000000000000000000000
162411061562048512
1001000001000000000000000000000000000000000000000000000000
487514659662856192
11011000100000000000000000000000000000000000000000000000000
1463669878895411200
1010001010000000000000000000000000000000000000000000000000000
4395513236313604096
11110100000000000000000000000000000000000000000000000000000000
13258597302978740224
1011100000000000000000000000000000000000000000000000000000000000
40352252661239644160
100011000000000000000000000000000000000000000000000000000000000000
122209679488325779456
1101010000000000000000000000000000000000000000000000000000000000000
368934881474191032320
101000000000000000000000000000000000000000000000000000000000000000000
1180591620717411303424
10000000000000000000000000000000000000000000000000000000000000000000000

Here's the same sequnce using the odd numbers only Collatz algorithm.

27 11011
41 101001
31 11111
47 101111
71 1000111
107 1101011
161 10100001
121 1111001
91 1011011
137 10001001
103 1100111
155 10011011
233 11101001
175 10101111
263 100000111
395 110001011
593 1001010001
445 110111101
167 10100111
251 11111011
377 101111001
283 100011011
425 110101001
319 100111111
479 111011111
719 1011001111
1079 10000110111
1619 11001010011
2429 100101111101
911 1110001111
1367 10101010111
2051 100000000011
3077 110000000101
577 1001000001
433 110110001
325 101000101
61 111101
23 10111
35 100011
53 110101
5 101
1 1

Do you see the similarities?
It might help if I show them together:

11011
11011
1010010
101001
11111000
11111
1011110000
101111
100011100000
1000111
1101011000000
1101011
101000010000000
10100001
1111001000000000
1111001
101101100000000000
1011011
10001001000000000000
10001001
110011100000000000000
1100111
10011011000000000000000
10011011
111010010000000000000000
11101001
10101111000000000000000000
10101111
1000001110000000000000000000
100000111
11000101100000000000000000000
110001011
1001010001000000000000000000000
1001010001
11011110100000000000000000000000
110111101
1010011100000000000000000000000000
10100111
11111011000000000000000000000000000
11111011
1011110010000000000000000000000000000
101111001
100011011000000000000000000000000000000
100011011
1101010010000000000000000000000000000000
110101001
100111111000000000000000000000000000000000
100111111
1110111110000000000000000000000000000000000
111011111
101100111100000000000000000000000000000000000
1011001111
10000110111000000000000000000000000000000000000
10000110111
110010100110000000000000000000000000000000000000
11001010011
10010111110100000000000000000000000000000000000000
100101111101
111000111100000000000000000000000000000000000000000
1110001111
10101010111000000000000000000000000000000000000000000
10101010111
1000000000110000000000000000000000000000000000000000000
100000000011
11000000010100000000000000000000000000000000000000000000
110000000101
1001000001000000000000000000000000000000000000000000000000
1001000001
11011000100000000000000000000000000000000000000000000000000
110110001
1010001010000000000000000000000000000000000000000000000000000
101000101
11110100000000000000000000000000000000000000000000000000000000
111101
1011100000000000000000000000000000000000000000000000000000000000
10111
100011000000000000000000000000000000000000000000000000000000000000
100011
1101010000000000000000000000000000000000000000000000000000000000000
110101
101000000000000000000000000000000000000000000000000000000000000000000
101
10000000000000000000000000000000000000000000000000000000000000000000000
1

The most significant bit pattern is identical for
each paired resident of the two hotels. The difference
is that you keep the trailing 0s while I discard them.
>
> Regards,
> Mike...

Quantcast