flat assembler
Message board for the users of flat assembler.
Index
> Main > Mystery Sequence Contest Goto page 1, 2 Next 
Author 

bitRAKE 01 Aug 2009, 05:52
We explore another selfgenerating 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.
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 ThueMorse 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 higherdimensions? 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 (16bit, 32bit, 64bit), supported range, and output format: Code: Author Format Code TRange Bytes Notes Madis731 ASCII 64bit 2  43 34 range 89 with 64bit 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 01 Aug 2009, 19:52
Next almost obvious feature. 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:
BTW, what do you exactly mean by this bitRAKE wrote: How can this sequence be expanded into higherdimensions? 

01 Aug 2009, 19:52 

bitRAKE 01 Aug 2009, 23:05
MHajduk wrote: BTW, what do you exactly mean by this http://www.youtube.com/watch?v=ZDGGEQqSXew _________________ ¯\(°_o)/¯ “languages are not safe  uses can be” Bjarne Stroustrup 

01 Aug 2009, 23:05 

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.
If we define l(n) as a length of the T(n) string, we will have Code: l(n) = l(n1) + l(n2) 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 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(n1)T(n2) = T(n2)T(n3)T(n2) for every natural n>=3 T(n) for even n>=4 also can't be palindrome, because (from the formula presented above in this post) even if T(n2) would be palindrome T(n3) isn't (n3 is an odd number). Only palindromic terms of the T sequence are T(0) and T(2). 

02 Aug 2009, 19:42 

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 pseudopalindromic  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 2bit 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 03 Aug 2009, 13:53
It is possible to find bitN 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 03 Aug 2009, 15:18
Observation#1: There are no ones ('1') next to eachother
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 0based counting. This way bitat[0]=0, bitat[1]=1, bitat[2]=22=0, bitat[3]=33=0, bitat[4]=43=1, etc. 

03 Aug 2009, 15:18 

bitRAKE 04 Aug 2009, 14:08
Yeah, it works just fine with 0based bit indexing:
Code: irp i,2,3,5,8,13,21,34 { reverse cmp rcx,i jc @F sub rcx,i @@: } Code: irp i,2,3,5,8,13,21,34 { reverse mov rax,i xadd rcx,rax cmovs rcx,rax } 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 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 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 05 Aug 2009, 11:24
Maybe we can draw an "Ant" algorithm in the bitmap where it follows the cadence of 110110 (oddoddeven) 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 coordinates (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 

05 Aug 2009, 11:24 

Madis731 05 Aug 2009, 12:47
Anyway my first try.
Version1  34 bytes. Rather elegant, not anything cryptic. 64bit 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 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 0101101011011010110101101101011011 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 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 

06 Aug 2009, 03:37 

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. When/if computers start getting that kind of insane data compression, then criticize nature. 

06 Aug 2009, 07:56 

bitRAKE 06 Aug 2009, 13:43
Azu wrote: When/if computers start getting that kind of insane data compression, then criticize nature. _________________ ¯\(°_o)/¯ “languages are not safe  uses can be” Bjarne Stroustrup 

06 Aug 2009, 13:43 

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.


06 Aug 2009, 13:46 

Azu 06 Aug 2009, 13:50
A lot of redundant data compressed into a very tiny space..


06 Aug 2009, 13:50 

Goto page 1, 2 Next < Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992024, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.