Mystery Sequence Contest

Index > Main > Mystery Sequence Contest

Goto page 1, 2 Next

Author

Thread

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 01 Aug 2009, 05:52

We explore another self-generating sequence with prefix bits in common across terms. Looking for smallest code fragments generating a range of terms. I have rediscovered this one many times. Very Happy

This sequence has many interesting properties. What can you discover? A perspective I like to entertain is one of the limit T(infinity), and imagine the result as a field. Instead of clearing or setting memory another field can be applied. In the case of Thue-Morse it is rather easy to query any point in the field without actually generating the field - it's the bit index parity. What is required to do the same with this sequence?

How can this sequence be expanded into higher-dimensions?

T0 = 0
T1 = 01
T2 = 010
T3 = 01001
T4 = 01001010
T5 = 0100101001001
T6 = 010010100100101001010
T7 = 0100101001001010010100100101001001
T8 = 0100101001001010010100100101001001010010100100101001010

Dynamic winner categories created by participation: processor mode (16-bit, 32-bit, 64-bit), supported range, and output format:

Code:

 Author         Format  Code     T-Range   Bytes  Notes

 Madis731       ASCII   64-bit   2 - 43    34     range 89 with 64-bit registers
                                                   and sufficient memory.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

Last edited by bitRAKE on 06 Aug 2009, 02:01; edited 2 times in total

01 Aug 2009, 05:52

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 01 Aug 2009, 19:11

Hi, bitRAKE! Smile

Let us define this sequence of strings made of 0 and 1 symbols by simple recursion:

Code:

T(0) = 0
T(1) = 01
T(n) = T(n-1)T(n-2) for every natural number n >= 2

Every term T(n) of the sequence T for n >= 2 is defined as a concatenation of preceding two terms (which are strings).

First, rather obvious, feature, which we can notice is that for every even n last character of the T(n) is 0 and for every odd n last character of T(n) is 1. It could be proved by induction as follows:

For the first two terms of this sequence it's obvious.
Let our assumption will be true for every natural k which are less than or equal some natural n>=1. We'll prove that then it would be true also for n+1.

If n+1 is even, then it could be denoted as 2m for some natural m. We have
Code:
```
T(n+1) = T(n+1-1)T(n+1-2) = T(2m-1)T(2m-2)    
```
But, from our assumption, T(2m-2) has the last character equal to 0 (2m-2 is an even number less than n = 2m-1).

If n+1 is odd, then it could be denoted as 2m+1 for some natural m. We have
Code:
```
T(n+1) = T(n+1-1)T(n+1-2) = T(2m+1-1)T(2m+1-2) = T(2m)T(2m-1)    
```
But 2m-1 is an odd number less than n = 2m and, from the given assumption, T(2m-1) has the last character equal to 1.

01 Aug 2009, 19:11

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 01 Aug 2009, 19:52

Next almost obvious feature. Wink

There doesn't exist term of the sequence which has substring made of 1 with length greater than 1. This also could be proved by induction as follows:

For T(0) and T(1) it's obvious.
Let our assumption will be true for every natural k less than or equal some natural n>=1. We'll prove that it would be also true for n+1. We have
Code:
```
T(n+1) = T(n+1-1)T(n+1-2) = T(n)T(n-1)    
```
There is only one place in the T(n+1) string where 1 symbols could be duplicated: place where ending symbol of the T(n) is a neighbor of the first symbol of T(n-1). But, from the obvious fact, starting symbol of every term of the T sequence is 0, hence newly created string also fulfills our assumption.

We can also prove this way another simple fact: there doesn't exist substring made of 0 with length greater than 2 (we can prove that if we observe that every term T(n) for n>=1 starts from the sequence 01 and there doesn't exist term which can have other ending sequence than 01 or 10 [for n>=1]). Smile

BTW, what do you exactly mean by this

bitRAKE wrote:

How can this sequence be expanded into higher-dimensions?

01 Aug 2009, 19:52

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 01 Aug 2009, 23:05

MHajduk wrote:

BTW, what do you exactly mean by this

bitRAKE wrote:
How can this sequence be expanded into higher-dimensions?

It is very ambiguous, but ideally we would want to bring as many features of this sequence into higher dimensions. It could be something as silly as shells in 2D/3D. (Another good example is the hilbert curve in higher-dimensions.) Or the sequence can be transformed into a higher dimensional object directly: 00->x++, 01->y++, 10->z++ (rotate on selected axis, and always move forward one unit). Very Happy

The limits are only the imagination and what can be discovered about the sequence. My intent was the former, but the pseudo-palindromic and fractal nature of the sequence could be fun.

http://www.youtube.com/watch?v=ZDGGEQqSXew

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

01 Aug 2009, 23:05

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 02 Aug 2009, 19:19

Yeah, I've realized that lengths of the terms of the T sequence correspond with the terms of the Fibonacci numbers sequence F. Wink

If we define l(n) as a length of the T(n) string, we will have

Code:

l(n) = l(n-1) + l(n-2)

because length of the concatenation of strings T(n-1) and T(n-2) is equal to the sum of lengths of these strings.

There is only one thing: we start from the natural numbers 1 and 2, not from the 0 and 1:

Code:

T(0) = 0                      l(0) = 1 = F(2)
T(1) = 01                     l(1) = 2 = F(3)
T(2) = 010 = T(1)T(0)         l(2) = l(1) + l(0) = 2 + 1 = 3 = F(4)
T(3) = 01001 = T(2)T(1)       l(3) = l(2) + l(1) = 3 + 2 = 5 = F(5)
T(4) = 01001010 = T(3)T(2)    l(4) = l(3) + l(2) = 5 + 3 = 8 = F(6)
...

02 Aug 2009, 19:19

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 02 Aug 2009, 19:42

As you said previously, terms of our sequence T show us some symmetry. But this symmetry is hidden rather in the rule of creation of the new terms than in the visible form of these strings (they usually aren't palindromes).

From definition of the T sequence we have

Code:

T(n) = T(n-1)T(n-2) = T(n-2)T(n-3)T(n-2) for every natural n>=3

It's obvious that T(n) for odd n can't be palindrome, because every term of the T sequence starts from 0, and every T(n) for odd n has 1 as a last symbol.

T(n) for even n>=4 also can't be palindrome, because (from the formula presented above in this post) even if T(n-2) would be palindrome T(n-3) isn't (n-3 is an odd number).

Only palindromic terms of the T sequence are T(0) and T(2). Smile

02 Aug 2009, 19:42

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 03 Aug 2009, 00:21

Just remove the last two digits of a term and it's a palindrome.
(So, I made up the term pseudo-palindromic - close enough.)

T(-1) = 1, and use the substitution definition: 0->01, 1->0; and the lengths are still F(n+2). Bit counts are also F() connected! (Another topic perhaps: the substitution definition also allows us to construct an interesting tree.)

What can be said about the partitions of T(inf)? We know 2-bit partitions consist of: 00 01 10.

2 | 00 01 10
3 | 001 010 100 101
4 | 0010 0100 0101 1001 1010

Hm...

03 Aug 2009, 00:21

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 03 Aug 2009, 13:53

It is possible to find bit-N of the infinite sequence in less than O(log base golden ratio N). This can be done by subtracting the largest fibonacci number until 0 or 1 is reached, then the bit value is opposite. (Bit count used here is 1 based not the typical 0 based bit numbering of x86.)

For example, bit 54 is 1:
54 - 34 = 20
20 - 13 = 7
7 - 5 = 2
2 - 2 = 0 <-- result is opposite.

03 Aug 2009, 13:53

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 03 Aug 2009, 15:18

Observation#1: There are no ones ('1') next to each-other
Observation#2:
When you start taking Fibonacci sequence amount of digits from the start
you can notice they are all palindromes. Example:
T8 = 0100101001001010010100100101001001010010100100101001010
'0', '1', '00', '101', '00100', '10100101', etc.
Observation#3:
When we construct the sequence throught T0 and T1, it is obvious where
the reversing / palindrome effect comes from:
T0; T1; T1+T0; T1+T0+T1; T1+T0+T1+T1+T0; etc.

@bitRAKE: Isn't is easier to use 0-based counting. This way
bitat[0]=0, bitat[1]=1, bitat[2]=2-2=0, bitat[3]=3-3=0, bitat[4]=4-3=1, etc.

03 Aug 2009, 15:18

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 04 Aug 2009, 14:08

Yeah, it works just fine with 0-based bit indexing:

Code:

       irp i,2,3,5,8,13,21,34 {
       reverse
             cmp rcx,i
           jc @F
               sub rcx,i
   @@:
     }

...it seems there is a method without the branch miss-penalties.

Code:

   irp i,2,3,5,8,13,21,34 {
       reverse
             mov rax,-i
          xadd rcx,rax
                cmovs rcx,rax
       }

(XADD/CMOV** is a nice combo. Cool

)

Sure beats trying to calculate:

Last edited by bitRAKE on 06 Aug 2009, 00:54; edited 5 times in total

04 Aug 2009, 14:08

r22

Joined: 27 Dec 2004
Posts: 805

r22 04 Aug 2009, 20:43

Expanding on the fact that there are never 2 consecutive 1's you can compress the sequence by only using the number of 0's between the 1's.

Uncompressed
T4 = 01001010
T5 = 0100101001001

Compressed
0 = one zero
1 = 2 zeros
T4 = 0100
T5 = 01011

When decompressing you'd add 1's between the sets of 0's and add the trailing 1 for the Odd iterations.

Perhaps the compressed sequence could be calculated in a more efficient manner than the original ?

04 Aug 2009, 20:43

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 05 Aug 2009, 10:18

Maybe I don't get the compression, but shouldn't it be:

Code:

T0 = 0           0
T1 = 01            1
T2 = 010   10
T3 = 01001        101
T4 = 01001010    10110

Just a find&replace

Pack: 01=>1; 0=>0

Unpack: 1=>01; 0=>0

EDIT: I get it
Rule#1: There are no two consecutive '1's
Rule#2: There are exactly {one | two} '0's

Observation: The string consists of two substrings - a '01' and a '001'

05 Aug 2009, 10:18

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 05 Aug 2009, 11:24

Maybe we can draw an "Ant" algorithm in the bitmap where it follows the cadence of 1-1-0-1-1-0 (odd-odd-even) and it turns left (in 2D) on each 1 (odd) and goes straight on on each 0 (even), flipping output bits if odd. If we get on a visited square, the bits in the output are inverted from that point on.

Example T5 = 0100101001001
Generating starts from co-ordinates (x:0,y:0), direction vector is (x:-1,y:0), "left" means vector is turned 90° so that new is (x:0,y:1).
1) print '0', mark (0,0) visited, odd=LEFT+FLIP
2) print '1', mark (0,1) visited, odd=LEFT+FLIP
3) print '0', mark (1,1) visited, even=STRAIGHT
4) print '0', mark (2,1) visited, odd=LEFT+FLIP
etc.

its a thought it progress so I don't promise anything Smile

05 Aug 2009, 11:24

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 05 Aug 2009, 12:47

Anyway my first try.

Version1 - 34 bytes. Rather elegant, not anything cryptic. 64-bit fastcall

Note: you can save a byte when mov word[rcx],'01' is replaced with mov byte[rcx+1],1

Code:

    fastcall  Mystery,TM,8

Mystery:          ;34 bytes
    mov       word[rcx],'01' ;5
    xor       eax,eax        ;2
    mov       al,1           ;2
    lea       ebx,[rax*2]    ;3
    dec       edx            ;2
    mov       esi,ecx        ;2
    lea       edi,[rcx+rbx]  ;3 - 19 bytes init
  @@:
    mov       ecx,eax        ;2
    rep       movsb          ;2
    sub       esi,eax        ;2
    add       eax,ebx        ;2
    xchg      eax,ebx        ;1
    dec       edx            ;2
    jnz       @b             ;2
    ret                      ;1 - 14 bytes program

05 Aug 2009, 12:47

r22

Joined: 27 Dec 2004
Posts: 805

r22 05 Aug 2009, 20:41

I've found the bit pattern in my compressed version

Here's T[9]
01001010010010100101001001010010010100101001001010010100100101001001010010100100101001001

Here's T[9] compressed (see above explanation)
0101101011011010110101101101011011

Fib. Numbers 0,1,1,2,3,5,8 etc.
If you notice they have a pattern of EVEN ODD ODD EVEN ODD ODD EVEN ODD ODD .etc

Here's the Even Odd pattern
And the compressed T[9] mapped to the even odd pattern

Code:

0110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110
01----01--1----01----01--1----01--1----01----01--1----01----01--1----01--1----01----01--1----01--1

Here's the pseudo code to generate the compressed pattern
* EDIT * I'll post actual code once I work it out. The pseudo code was flawed.

Pretty interesting

05 Aug 2009, 20:41

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 06 Aug 2009, 03:37

r22, data compression is one of the contexts in which I discovered this sequence. I asked myself, "Why nature doesn't use binary?" In a general sense, effective use of binary requires arbitrary quantities of two substances (one for 0 and one for 1). In reality often one substance is in short supply while another is abundant. My conclusion was that nature would choose an information storage method relying on a single limiting substance, and another which was abundant.

Code:

.0100101001001010010100100101001001
0101101011011010110101101101011011

FYI: "Compressed" it becomes the same as uncompressed. Wink

06 Aug 2009, 03:37

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 06 Aug 2009, 07:56

bitRAKE wrote:

r22, data compression is one of the contexts in which I discovered this sequence. I asked myself, "Why nature doesn't use binary?" In a general sense, effective use of binary requires arbitrary quantities of two substances (one for 0 and one for 1). In reality often one substance is in short supply while another is abundant. My conclusion was that nature would choose an information storage method relying on a single limiting substance, and another which was abundant.
Code:
.0100101001001010010100100101001001
0101101011011010110101101101011011    
FYI: "Compressed" it becomes the same as uncompressed.

I think nature compresses data pretty well already. Amoeba dubia, for example, have 670 billion base pairs (which are the equivilant of 1 or 2 bits each I think) in their genome.. in a single microscopic cell! Shocked

When/if computers start getting that kind of insane data compression, then criticize nature. Razz

06 Aug 2009, 07:56

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 06 Aug 2009, 13:43

Azu wrote:

When/if computers start getting that kind of insane data compression, then criticize nature.

Quite the contrary - I always look to nature for answers! How can we compete with trillions of simulations per second over billions of years? It is the language of nature which we have difficulty understanding (if history is any indication, it's our egos in the way).

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

06 Aug 2009, 13:43

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8351
Location: Kraków, Poland

Tomasz Grysztar 06 Aug 2009, 13:46

Actually, DNA contains a lot of redundant data (as it makes it more resistant to damage, etc.), so I wouldn't really use it as an example of a good data compression - quite the opposite. Wink

06 Aug 2009, 13:46

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 06 Aug 2009, 13:50

A lot of redundant data compressed into a very tiny space.. Very Happy

06 Aug 2009, 13:50

Goto page 1, 2 Next

< Last Thread | Next Thread >

Forum Rules:

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