Simplificação de Múltiplos Somatórios

vc sabe a formula para duas variaveis?

This message was edited 1 time. Last update was at 26/01/2012 18:13:20

Encontrei uma P.A.

Agora vou testar para as outras variaveis

A sacada do problema é conhecer triangulo de pascal e arranjos.
Não sou muito bom nisso por isso estou deduzindo de outra forma.
analizando as diferêncas atá encontrar uma razão.

a solucao para 3 variaveis é essa:
((r*(r+1)*(r+2)/3) + (n*(n+1)*(n+2)*(n+3)*(n+4)/60)*7)
onde r=n+1 e n qualquer inteiro

Esse é o caminho
[]'s

fimC = fimB-fimC
		fimD = fimC-fimD
		fimE = fimD-fimE
		fimF = fimE-fimF

document.write( " "+fimA+" -- diffs: "+fimB+" "+ fimC + " "+ fimD+" "+ fimE+" "+ fimF)
		fimF = fimE
		fimE = fimD
		fimD = fimC
		fimC = fimB 
		document.write( "<br>" ) 
	}

//================================================================
	// solucao para 3 variaveis
	//================================================================
	for( var n=-1; n<11; n++)
	{
		r=n+1
		//document.write(" - "+ ((r*(r+1)*(r+2)/6)*2 + (n*(n+1)*(n+2)*(n+3)*(n+4)/120)*14) )
		document.write(" - "+ ((r*(r+1)*(r+2)/3) + (n*(n+1)*(n+2)*(n+3)*(n+4)/60)*7) )
		document.write( "<br>" ) 
	}

/*
	//================================================================
	// possivelmente poderemos usar
	//================================================================
	n*(n+1)/2  = 1 3 6 10 15 21 28... 
	n² = 1 4 9 16 25 36 49... 
	n*(3n-1)/2 = 1 5 12 22 35 51 70... 
	n*(4n-2)/2 = 1 6 15 28 45 66 91... 
	n*(5n-3)/2 = 1 7 18 34 55 81 112... 
	n*(3n-2) = 1 8 21 40 65 96 133...

//================================================================
	chave para as soluções futuras
	//================================================================
	n*(n+1)/2 = 1 3 6 10 15 21... 
	n*(n+1)*(n+2)/6 = 1 4 10 20 35 56... 
	n*(n+1)*(n+2)*(n+3)/24 = 1 5 15 35 70 126... 
	n*(n+1)*(n+2)*(n+3)*(n+4)/120 ...
	*/
</script>

4 variaveis:

fimC = fimB-fimC
		fimD = fimC-fimD
		fimE = fimD-fimE
		fimF = fimE-fimF
		fimG = fimF-fimG
		fimH = fimG-fimH

document.write( " "+fimA+" -- diffs: "+fimB+" "+fimC +" "+fimD+" "+fimE+" "+fimF+" "+fimG+" "+fimH)
		fimH = fimG
		fimG = fimF
		fimF = fimE
		fimE = fimD
		fimD = fimC
		fimC = fimB 
		document.write( "<br>" ) 
	}

//================================================================
	// solucao para 4 variaveis
	//================================================================
	for( var q=-4; q<11; q++)
	{
		p=q+1
		o=q+2
		n=q+3
		m=q+4
		document.write(" - "+ ( (m*(m+1)*(m+2)/6)*2 + 
					(n*(n+1)*(n+2)*(n+3)/24)*52 + 
					(o*(o+1)*(o+2)*(o+3)*(o+4)/120)*256  + 
					(p*(p+1)*(p+2)*(p+3)*(p+4)*(p+5)/720)*408 + 
					(q*(q+1)*(q+2)*(q+3)*(q+4)*(q+5)*(q+6)/5040)*204    ) ) 
		document.write( "<br>" ) 
	}

/*
	//================================================================
	chave para as soluções futuras
	//================================================================

for( var o=1; o<20; o++)
	{
		//1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 
		//document.write(  o*(o+1)/2   )

//1 4 10 20 35 56 84 120 165 220 286 364 455 560 680 816 969 1140 1330 
		//document.write(  o*(o+1)*(o+2)/6   )

//1 5 15 35 70 126 210 330 495 715 1001 1365 1820 2380 3060 3876 4845 5985 7315 
		//document.write(  o*(o+1)*(o+2)*(o+3)/24   )

//1 6 21 56 126 252 462 792 1287 2002 3003 4368 6188 8568 11628 15504 20349 26334 33649 
		//document.write(  o*(o+1)*(o+2)*(o+3)*(o+4)/120   )

//1 7 28 84 210 462 924 1716 3003 5005 8008 12376 18564 27132 38760 54264 74613 100947 134596 
		//document.write(  o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)/720   )

//1 8 36 120 330 792 1716 3432 6435 11440 19448 31824 50388 77520 116280 170544 245157 346104 480700 
		//document.write(  o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)*(o+6)/5040   )

//1 9 45 165 495 1287 3003 6435 12870 24310 43758 75582 125970 203490 319770 490314 735471 1081575 1562275 
		//document.write(  o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)*(o+6)*(o+7)/40320   )

document.write( " " ) 
	}
	*/
</script>

Solução:

for( var n=1; n<=20; n++)
	{
		result=0;
		for(var i=1; i<=n; i++)
		{
			for(var j=1; j<=n; j++)
			{
				tempA=Math.abs(i-j)
				for(var k=1; k<=n; k++)
				{
					tempB=tempA*Math.abs(j-k);
					//result+=tempB;
					for(var l=1; l<=n; l++)
					{
						tempC=tempB*Math.abs(k-l);
						//result+=tempC;
						for(var m=1; m<=n; m++)
						{
							tempD=tempC*Math.abs(l-m)*Math.abs(m-i);
							result+=tempD;
						}
					}
				}
			}
		}
		fimB = result-fimA
		fimA = result;

fimC = fimB-fimC
		fimD = fimC-fimD
		fimE = fimD-fimE
		fimF = fimE-fimF
		fimG = fimF-fimG
		fimH = fimG-fimH
		fimI = fimH-fimI
		fimJ = fimI-fimJ
		fimK = fimJ-fimK

document.write( " "+fimA+" -- diffs: "+fimB+" "+fimC +" "+fimD+" "+fimE+" "+fimF+" "+fimG+" "+fimH+" "+fimI+" "+fimJ+" "+fimK)
		fimK = fimJ
		fimJ = fimI
		fimI = fimH
		fimH = fimG
		fimG = fimF
		fimF = fimE
		fimE = fimD
		fimD = fimC
		fimC = fimB 
		document.write( "<br>" ) 
	}

//================================================================
	// solucao para 5 variaveis - FALTA SIMPLIFICAR!
	//================================================================
	for( var x=0; x<20; x++)
	{
		//r=s+1 
		t=-5+x;
		s=t+1
		r=t+2
		q=t+3
		p=t+4
		o=t+5 
		document.write(" - "+ ( 
					(o*(o+1)*(o+2)*(o+3)*(o+4)/120)*120  + 
					(p*(p+1)*(p+2)*(p+3)*(p+4)*(p+5)/720)*2480 + 
					(q*(q+1)*(q+2)*(q+3)*(q+4)*(q+5)*(q+6)/5040)*15280  +
					(r*(r+1)*(r+2)*(r+3)*(r+4)*(r+5)*(r+6)*(r+7)/40320)*38720  +
					(s*(s+1)*(s+2)*(s+3)*(s+4)*(s+5)*(s+6)*(s+7)*(s+8)/362880)*42800  +
					(t*(t+1)*(t+2)*(t+3)*(t+4)*(t+5)*(t+6)*(t+7)*(t+8)*(t+9)/3628800)*17120  		
		)%10007 ) 
		document.write( "<br>" ) 
	}

/*
	//================================================================
	// possivelmente poderemos usar
	//================================================================
	n*(n+1)/2  = 1 3 6 10 15 21 28... 
	n² = 1 4 9 16 25 36 49... 
	n*(3n-1)/2 = 1 5 12 22 35 51 70... 
	n*(4n-2)/2 = 1 6 15 28 45 66 91... 
	n*(5n-3)/2 = 1 7 18 34 55 81 112... 
	n*(3n-2) = 1 8 21 40 65 96 133...

//================================================================
	chave para as soluções
	//================================================================

for( var o=1; o<20; o++)
	{
		//1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 
		//document.write(  o*(o+1)/2   )

//1 4 10 20 35 56 84 120 165 220 286 364 455 560 680 816 969 1140 1330 
		//document.write(  o*(o+1)*(o+2)/6   )

//1 5 15 35 70 126 210 330 495 715 1001 1365 1820 2380 3060 3876 4845 5985 7315 
		//document.write(  o*(o+1)*(o+2)*(o+3)/24   )

//1 6 21 56 126 252 462 792 1287 2002 3003 4368 6188 8568 11628 15504 20349 26334 33649 
		//document.write(  o*(o+1)*(o+2)*(o+3)*(o+4)/120   )

//1 7 28 84 210 462 924 1716 3003 5005 8008 12376 18564 27132 38760 54264 74613 100947 134596 
		//document.write(  o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)/720   )

//1 8 36 120 330 792 1716 3432 6435 11440 19448 31824 50388 77520 116280 170544 245157 346104 480700 
		//document.write(  o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)*(o+6)/5040   )

//1 9 45 165 495 1287 3003 6435 12870 24310 43758 75582 125970 203490 319770 490314 735471 1081575 1562275 
		//document.write(  o*(o+1)*(o+2)*(o+3)*(o+4)*(o+5)*(o+6)*(o+7)/40320   )

document.write( " " ) 
	}
	*/
</script>

[]'s

Legal Luiz!
Traduza para Java (use BigInteger) e poste no UVa sua solução para ver se está ok.
Não vou copiar sua solução, afinal, vc acabou fazendo praticamente tudo.

[]'s

This message was edited 1 time. Last update was at 27/01/2012 09:39:25

Nem, vai lá. O problema era seu. Pode fazer em java, se quiser, e colocar lá a resposta.
Detalhe, acho que não precisa usar biginteger se vc fizer por log.

tem um problema que eu to buscando resposta até hoje e não consegui asolução. se quiser me ajudar, se quiser fazer e me mostrar a solução:
http://www.guj.com.br/java/262664-thuemorse-sequence-dificil

problema:
http://projecteuler.net/problem=361

[]'s

Não funcionou não.
Você testou as entradas do problema? Foram geradas as saídas corretas?

Não fiz para todos os inputs.
Acho que está ocorrendo um truncamento dos inteiros.
Vou fazer aqui usando log. pra me certificar.

Esse probleminha tá foda.
Eu simplifiquei para log, mas ainda estou tendo o mesmo erro. tenho que estudar isso com maior cuidado.
Se encontrar alguma solução eu posto aqui mais tarde.
Alguem já respondeu esse problema? Não existe possibilidade desse 1001 estar errado?

aqui minha simplificação:

function somatoria(x)
	{
		var fatoriais	=[Math.log(120),Math.log(720),Math.log(5040),Math.log(40320),Math.log(362880),Math.log(3628800)]
		var chaves	=[Math.log(120),Math.log(2480),Math.log(15280),Math.log(38720),Math.log(42800),Math.log(17120) ]
		var arraySums = new Array();

x-=2 
		t=-5+x;

var prime = Math.log(10007);

arraySums.push( Math.log(t+9)+Math.log(t+8)+Math.log(t+7)+Math.log(t+6)+Math.log(t+5) ) 
		arraySums.push( Math.log(t+4)+arraySums[0] ) 
		arraySums.push( Math.log(t+3)+arraySums[1] ) 
		arraySums.push( Math.log(t+2)+arraySums[2] ) 
		arraySums.push( Math.log(t+1)+arraySums[3] ) 
		arraySums.push( Math.log(t)+arraySums[4] )

var a=arraySums[0]-fatoriais[0]+chaves[0]
		a=(Math.exp(a-prime) - Math.floor(Math.exp(a-prime)))*10007
		if(a==0)
		a=arraySums[0]-fatoriais[0]+chaves[0]

var b=arraySums[1]-fatoriais[1]+chaves[1]
		b=(Math.exp(b-prime) - Math.floor(Math.exp(b-prime)))*10007
		if(b==0)
		b=arraySums[1]-fatoriais[1]+chaves[1]

var c=arraySums[2]-fatoriais[2]+chaves[2]
		c=(Math.exp(c-prime) - Math.floor(Math.exp(c-prime)))*10007
		if(c==0)
		c=arraySums[2]-fatoriais[2]+chaves[2]

var d=arraySums[3]-fatoriais[3]+chaves[3]
		d=(Math.exp(d-prime) - Math.floor(Math.exp(d-prime)))*10007
		if(d==0)
		d=arraySums[3]-fatoriais[3]+chaves[3]

var e=arraySums[4]-fatoriais[4]+chaves[4]
		e=(Math.exp(e-prime) - Math.floor(Math.exp(e-prime)))*10007
		if(e==0)
		e=arraySums[4]-fatoriais[4]+chaves[4]

var f=arraySums[5]-fatoriais[5]+chaves[5]
		f=(Math.exp(f-prime) - Math.floor(Math.exp(f-prime)))*10007
		if(f==0)
		f=arraySums[5]-fatoriais[5]+chaves[5]

document.write( (x+2)+" = "+ Math.round(a  +b  +c  +d  +e  +f )%10007 ) 
		document.write( "<br>" )

//document.write( (t*(t+1)*(t+2)*(t+3)*(t+4)*(t+5)*(t+6)*(t+7)*(t+8)*(t+9)/3628800)*17120   ) 
		
	}

for(var i=1; i<=1001; i++)
	{
		somatoria(i)
	}

</script>

Oi Luiz,

No UVa, só 6 pessoas conseguiram responder.

[]'s

Acho que descobri porque não tá dando cert, mas não tenho como testar.
Eu não to com o Java instalado aqui e por isso não tenho como utilizar o BigInteger.
Eu acho que os numeros encontrados são tão grandes que o log não está pegando casas decimais suficientes.
Acho que seria uma boa se vc tentasse fazer ai utilizando biginteger mesmo, como vc estava tentando antes.
No bigInteger existe como pegar o logaritimo?
Se tiver acho que tem como testar. Acha que pode testar ai e me dizer se funcionou para o 1001?
Se não for isso tenho que pedir arrego.

Oi Luiz, valeu pelo empenho!
Estou mexendo com algumas coisas agora e na hora q tiver um tempinho eu vou ver o que faço!
Valeu

[]'s

This message was edited 1 time. Last update was at 27/01/2012 21:23:04

Como eu lhe falei o Logaritmo tá sendo truncado e por isso o erro.
Tive que fazer usando BigInteger:

biginteger.js do site http://silentmatt.com/biginteger/
Anexei o arquivo "biginteger.js"

var a0	=BigInteger.parse([""+(t+9)],10)
			.multiply(BigInteger.parse([""+(t+8)],10))
			.multiply(BigInteger.parse([""+(t+7)],10))
			.multiply(BigInteger.parse([""+(t+6)],10))
			.multiply(BigInteger.parse([""+(t+5)],10))

var a1 = new BigInteger()
		a1=a1.add(a0.multiply(BigInteger.parse([""+(t+4)],10)))

var a2 = new BigInteger()
		a2=a2.add(a1.multiply(BigInteger.parse([""+(t+3)],10)))

var a3 = new BigInteger()
		a3=a3.add(a2.multiply(BigInteger.parse([""+(t+2)],10)))

var a4 = new BigInteger()
		a4=a4.add(a3.multiply(BigInteger.parse([""+(t+1)],10)))

var a5 = new BigInteger()
		a5=a5.add(a4.multiply(BigInteger.parse([""+t],10)))

var a=a0.quotient(fatoriais[0]).multiply(chaves[0])
		var b=a1.quotient(fatoriais[1]).multiply(chaves[1]) 
		var c=a2.quotient(fatoriais[2]).multiply(chaves[2])
		var d=a3.quotient(fatoriais[3]).multiply(chaves[3])
		var e=a4.quotient(fatoriais[4]).multiply(chaves[4]) 
		var f=a5.quotient(fatoriais[5]).multiply(chaves[5])

document.write( (x+2)+" = "+ (a.add(b).add(c).add(d).add(e).add(f).remainder(10007).toString(10))   );
		document.write( "<br>" ) 		
	}
	somatoria(1001)
</script>

This message was edited 1 time. Last update was at 28/01/2012 13:53:16

entanglement wrote:Note também que 10007 é um número primo, e números primos costumam ter propriedades interessantes.

vc tem razão. Os ciclos aparecem com apenas 2 repetições de numeros quando pegamos o resto de um numero primo.
Se o numero não for primo, poderão existir muitos zeros e muitos numeros repetidos antes de um novo ciclo se iniciar.

Melhorias do codigo.
biblioteca que estou usando:
http://www-cs-students.stanford.edu/~tjw/jsbn/

var chave0 = new BigInteger(""+120,10)
	var chave1 = new BigInteger(""+2480,10)
	var chave2 = new BigInteger(""+15280,10)
	var chave3 = new BigInteger(""+38720,10)
	var chave4 = new BigInteger(""+42800,10)
	var chave5 = new BigInteger(""+17120,10)

function somatoria(x)
	{ 
		t=-7+x; 
		t%=10007

var a0	=new BigInteger((t+9)+"",10)
			.multiply(new BigInteger((t+8)+"",10))
			.multiply(new BigInteger((t+7)+"",10))
			.multiply(new BigInteger((t+6)+"",10))
			.multiply(new BigInteger((t+5)+"",10))

var a1 = a0.multiply(new BigInteger((t+4)+"",10))
		var a2 = a1.multiply(new BigInteger((t+3)+"",10))
		var a3 = a2.multiply(new BigInteger((t+2)+"",10))
		var a4 = a3.multiply(new BigInteger((t+1)+"",10))
		var a5 = a4.multiply(new BigInteger(t+"",10))

var b0 = a0.divide(fatorial0).multiply(chave0)
		var b1 = a1.divide(fatorial1).multiply(chave1)
		var b2 = a2.divide(fatorial2).multiply(chave2)
		var b3 = a3.divide(fatorial3).multiply(chave3)
		var b4 = a4.divide(fatorial4).multiply(chave4)
		var b5 = a5.divide(fatorial5).multiply(chave5)

var sums = b0.add(b1).add(b2).add(b3).add(b4).add(b5);

document.write(x+"-"+ sums.remainder(new BigInteger("10007",10)).toString(10));
		document.write( "<br>" ) 		
	}

//ciclos para exemplo de demonstracao. Qualquer n.
	var n=12;

somatoria(n+10007*0)
	somatoria(n+10007*1)
	somatoria(n+10007*2)
	somatoria(n+10007*3)
	somatoria(n+10007*4)
	somatoria(n+10007*32)
</script>

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