Thue?Morse sequence (Difícil!)

This message was edited 2 times. Last update was at 11/01/2012 15:19:01

Olá pessoal!

Alguem aqui já trabalhou com isso?
Se eu quiser saber se existe o numero 11010011 na sequencia dada é facil verificar com um 'indexOf'.
Mas será que existe uma formula simples para dizer se existe ou não?
Por enquanto estou achando que só é possivel na força bruta.
Pra quem tiver interesse, deem uma olhada no metodo 'getDigit' responsavel por mostrar o digito na posição 'n'

Deem uma olhada no que já fiz:

/*
	Luiz Augusto Prado - Morse-Thue sequence

The Morse-Thue is give by this :
	T0 = 0
	T2n = Tn
	T2n+1 = 1 - Tn

Where we have:
	01101001100101101001011001101001....

note:
	0 	= 0
	2 	= 1
	4 	= 10
	8 	= 1001
	16	= 10010110
	32	= 1001011001101001
	64	= 10010110011010010110100110010110
	*/

function log2(n)
	{
		return Math.log(n)/Math.log(2);
	}

//=============================================================================
	// Sequence by arrays. It can be hard if you wanna have only some digits
	//=============================================================================
	document.write( "<pre>" );
	var tm=60
	var array=new Array()
	for(var i=1; i<tm; i++)
	{
		array.push(0);
	}
	for(var i=0; i<tm/2+1; i++)
	{
		array[2*i]=array[i];
		array[2*i+1]=1-array[i];
	}
	document.write( array.join(' ') +" <br><br>");

//=================================================================================
	// I made this source to get only the digts that I wanna have. Better!
	//=================================================================================
	function getDigit(n, invert)
	{
		if(n==0)return 0
		var pA = Math.floor(log2(n))
		var v  = Math.round( Math.pow(2, pA) )
		var remainder=n-v
		if(remainder>v)
		{
			invert=1-invert	
			remainder-=v
		}
		if(remainder>1) remainder = getDigit(remainder, invert)
		if(invert==0) remainder=1-remainder
		return remainder
	}

//=================================================================================
	// Example
	//=================================================================================
	for(var i=0; i<18; i++)
	{
		for(var k=Math.pow(2,i); k<Math.pow(2,i+1); k++)
		{
			document.write( getDigit(k, 0) +"" );
		}
		document.write( "<br>" );
	}

</script>

Notícias, artigos e o maior fórum brasileiro sobre Java