flat assembler
Message board for the users of flat assembler.

Index > Main > Mystery Sequence Contest

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
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)/¯ unlicense.org


Last edited by bitRAKE on 06 Aug 2009, 02:01; edited 2 times in total
Post 01 Aug 2009, 05:52
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6035
Location: Poland
MHajduk
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:

  1. For the first two terms of this sequence it's obvious.

  2. 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.
Smile
Post 01 Aug 2009, 19:11
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6035
Location: Poland
MHajduk
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:
  1. For T(0) and T(1) it's obvious.

  2. 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?
Question
Post 01 Aug 2009, 19:52
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
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)/¯ unlicense.org
Post 01 Aug 2009, 23:05
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6035
Location: Poland
MHajduk
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)
...    
Smile
Post 02 Aug 2009, 19:19
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6035
Location: Poland
MHajduk
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
Post 02 Aug 2009, 19:42
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
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...
Post 03 Aug 2009, 00:21
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
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.
Post 03 Aug 2009, 13:53
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
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.
Post 03 Aug 2009, 15:18
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
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:
Image


Last edited by bitRAKE on 06 Aug 2009, 00:54; edited 5 times in total
Post 04 Aug 2009, 14:08
View user's profile Send private message Visit poster's website Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
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 ?
Post 04 Aug 2009, 20:43
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
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'
Post 05 Aug 2009, 10:18
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
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
Post 05 Aug 2009, 11:24
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
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
    
Post 05 Aug 2009, 12:47
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
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
Post 05 Aug 2009, 20:41
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
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
Post 06 Aug 2009, 03:37
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
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. Wink
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
Post 06 Aug 2009, 07:56
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2914
Location: [RSP+8*5]
bitRAKE
Azu wrote:
When/if computers start getting that kind of insane data compression, then criticize nature. Razz
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)/¯ unlicense.org
Post 06 Aug 2009, 13:43
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7734
Location: Kraków, Poland
Tomasz Grysztar
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
Post 06 Aug 2009, 13:46
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
A lot of redundant data compressed into a very tiny space.. Very Happy
Post 06 Aug 2009, 13:50
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
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


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.