Discussoes de Programacao e Tecnologia

Simplificação de Múltiplos Somatórios

29 respostas
D
davidbuzatto

Olá pessoal,

Essa é para os matemáticos. :)
Estou trabalhando na solução de um problema (desafio de programação), mas o algoritmo que escrevi tem complexidade n^5, o que inviabiliza sua execução mesmo para valores pequenos de entrada.
O que preciso é realizar o somatório de múltiplos somatórios (a função está em anexo).

O algoritmo que tenho, extremamente lento, é o seguinte. 
BigInteger n = new BigInteger( "20" );
BigInteger soma = BigInteger.ZERO;

for ( BigInteger i = BigInteger.ONE; !(i.compareTo( n ) > 0); i = i.add( BigInteger.ONE ) ) {
    for ( BigInteger j = BigInteger.ONE; !(j.compareTo( n ) > 0); j = j.add( BigInteger.ONE ) ) {
        for ( BigInteger k = BigInteger.ONE; !(k.compareTo( n ) > 0); k = k.add( BigInteger.ONE ) ) {
            for ( BigInteger l = BigInteger.ONE; !(l.compareTo( n ) > 0); l = l.add( BigInteger.ONE ) ) {
                for ( BigInteger m = BigInteger.ONE; !(m.compareTo( n ) > 0); m = m.add( BigInteger.ONE ) ) {
                    soma = soma.add( ( i.subtract( j ).multiply( j.subtract( k ).multiply( k.subtract( l ).multiply( l.subtract( m ).multiply( m.subtract( i ) ) ) ) ) ).abs() );
                }
            }
        }
    }
}
Queria saber se tem como simplificar a função para que o algoritmo fique mais rápido. Preciso executar ele cerca de 1000 vezes em menos de 3 segundos, para valores de n que variam de 1 a [telefone removido]. Para valores de n variando de 1 a 20 eu tenho os seguintes resultados. Imagem para n = [telefone removido]. 
0
0
120
3200
35160
237120
1164800
4572160
15174720
44200640
115961560
279227520
625888120
[telefone removido]
[telefone removido]
[telefone removido]
[telefone removido]
[telefone removido]
[telefone removido]
[telefone removido]

Já procurei bastante. O WolframAlpha só me retorna resultados para dois somatórios consecutivos. A partir do terceiro ele já não resolve, não entende o que estou pedindo. Se alguém tiver o Mathematica ou o MATLab e puder avaliar a expressão para mim, vendo se sugerem alguma simplificação, eu agradeço.

Se alguém quiser dar uma olhada no problema, é esse aqui: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3295

[]'s

Alura Git Flow: entenda o que é, como e quando utilizar Entenda o que é Git Flow, como funciona seu fluxo com branches como Master, Develop, Feature, Release e Hotfix, além de vantagens e desvantagens.

29 Respostas

E
entanglement

Ah, mas você não mostrou o problema corretamente. Você não viu o “módulo 10007” depois dos somatórios? Obviamente para você resolver o problema para n = [telefone removido] (que é o maior valor possível) você tem de levar em conta que há esse “módulo”.

Esse problema não pode ser resolvido simplesmente calculando todos os somatórios, e depois achando o módulo. Você tem de achar a fórmula já levando em conta a presença desse módulo.

E
entanglement

Dica: comece com 2 somatórios (porque você precisa ter i e j) e então veja se você consegue alguma generalização para 3 ou mais somatórios.

E
entanglement

Tem mais uma coisinha interessante. Veja o número [telefone removido] que ele passou. Ele é menor que 2^31 - 1, então isso quer dizer que você, de alguma forma, nem precisa usar “long”, talvez se você souber a fórmula certa precise apenas de fazer contas com “int”. Mas isso é para você descobrir.

E
entanglement

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

D
davidbuzatto

Oi entanglement, realmente, falou explicar isso. Não postei minha solução completa, mas no final, o que é exibido é o resto da divisão por 10007.
Tentei encontrar um ciclo, igual nesse problema aqui (que já resolvi), mas não consegui.
Pensei em algo do tipo que você mencionou, mas não saiu nada. Não pensei em levar em consideração o módulo, mas sim somente o “miolo” do problema. Realmente o número é representável por um long, o problema é o número gerado pela função, que como você mencionou, talvez não seja usado, visto o tempo necessário para gerá-lo.
Vou tentar encontrar um ciclo… Acho que talvez seja uma saída.

Obrigado!

L
Luiz_Augusto_Prado

bem legal essa questão.
Eu sei que existe simplificação para somatoria simples.
exemplo:
somatoria de 1 a n = (n*n+n)/2
vou pensar e se encontrar algum caminho posto aqui.

L
Luiz_Augusto_Prado

Nesse caso acho que ele quer o resto da divisão por 10007 porque o resultado dos somatorios seria muito grande.
Dando o resto da divisão por um numero primo fica mais fácil

D
davidbuzatto

As respostas variam de 0 a 10006, o problema é conseguir gerar o que deve ser dividido por 10007 ou então encontrar uma alternativa que dividida por 10007 dê o mesmo resultado.

D
davidbuzatto

Os números gerados são múltiplos de seus geradores.

L
Luiz_Augusto_Prado

já pensou em fazer com numeros pequenos, por exemplo de 0 à 30 e colocar em um gráfico para ver como é a curva?

L
Luiz_Augusto_Prado

Olha só, eu comecei pequeno:

<script>
	var n=12
	var result=0;
	var temp;
	for(var a=1; a<n; a++)
	{
		for(var b=1; b><n; b++)
		{
			temp=Math.abs(a-b);
			result+=temp;
			document.write( ""+a+" - "+b+" = "+temp+" result = "+result+"><br>")	
		}
	}
</script>
D
davidbuzatto

Já sim.

L
Luiz_Augusto_Prado

A curva segue algum padrão conhecido ou é muto caótica?

acho que encontrei um caminho:

<script>
	var n=10
	var result=0;
	var temp;
	for(var a=1; a<n; a++)
	{
		for(var b=1; b><n; b++)
		{
			temp=Math.abs(a-b);
			result+=temp;
			document.write( ""+a+" - "+b+" = "+temp+" result = "+result+"><br>")	
		}
		document.write( "<br>")
	}
</script>

Olha só, eu coloquei esse BR depois do segundo for. Ele separa blocos. O primeiro bloco é exatamente oposto ao ultimo. O segundo é oposto ao penultimo e assim vai.

D
davidbuzatto

E se colocar mais uma variável? E mais uma? Para duas é bastante trivial.

L
Luiz_Augusto_Prado

vc sabe a formula para duas variaveis?

L
Luiz_Augusto_Prado 
<script>
	var result;
	var temp;
	var fim=0; 
	for( var n=1; n<=12; n++)
	{ 
		result=0;
		for(var a=1; a<=n; a++)
		{
			for(var b=1; b<=n; b++)
			{
				temp=Math.abs(a-b);
				result+=temp;
				//document.write( ""+a+" - "+b+" = "+temp+" result = "+result+"<br>") 
			}
			//document.write( "<br>")
		}
		document.write( result+" = "+ (result-fim) )
		document.write( "<br>")
		fim=result;	
	}
</script>

Encontrei uma P.A.

Agora vou testar para as outras variaveis

L
Luiz_Augusto_Prado

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

<script>
	var result;
	var temp;
	var fimA=0; 
	var fimB=0; 
	var fimC=0; 
	var fimD=0; 
	var fimE=0;  
	var fimF=0;
	var r;
	for( var n=1; n<=12; n++)
	{
		r=n-1
		result=0;
		for(var a=1; a<=n; a++)
		{
			for(var b=1; b<=n; b++)
			{
				tempA=Math.abs(a-b)
				for(var c=1; c<=n; c++)
				{
					tempB=tempA*Math.abs(b-c);
					result+=tempB;
				}
			}
		}
		fimB = result-fimA
		fimA = result;

		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>
L
Luiz_Augusto_Prado

4 variaveis:

<script>
	var result;
	var temp;
	var fimA=0; 
	var fimB=0; 
	var fimC=0; 
	var fimD=0; 
	var fimE=0;  
	var fimF=0; 
	var fimG=0;
	var fimH=0;
	var r;
	for( var n=1; n<=12; n++)
	{
		result=0;
		for(var a=1; a<=n; a++)
		{
			for(var b=1; b<=n; b++)
			{
				tempA=Math.abs(a-b)
				for(var c=1; c<=n; c++)
				{
					tempB=tempA*Math.abs(b-c);
					//result+=tempB;
					for(var d=1; d<=n; d++)
					{
						tempC=Math.abs(c-d);
						result+=tempC*tempB;
					}
				}
			}
		}
		fimB = result-fimA
		fimA = result;


		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>
L
Luiz_Augusto_Prado

Solução:

<script>
	var result;
	var temp;
	var fimA=0; 
	var fimB=0; 
	var fimC=0; 
	var fimD=0; 
	var fimE=0;  
	var fimF=0; 
	var fimG=0;
	var fimH=0;
	var fimI=0;
	var fimJ=0;
	var fimK=0;
	var r;

	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

D
davidbuzatto

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

L
Luiz_Augusto_Prado

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:

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

[]'s

D
davidbuzatto

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

L
Luiz_Augusto_Prado 
<script>
	function somatoria(x)
	{
		//r=s+1 
		x-=2
		t=-5+x;
		s=t+1
		r=t+2
		q=t+3
		p=t+4
		o=t+5 
		document.write( (x+2)+" = "+ ( 
					(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>" ) 

		document.write( (t*(t+1)*(t+2)*(t+3)*(t+4)*(t+5)*(t+6)*(t+7)*(t+8)*(t+9)/3628800)*17120   )  //<================ possivel truncamento
		
	}
	somatoria(1001)
</script>

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

L
Luiz_Augusto_Prado

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:

<script>
/*
in	out
12	2199
20	803
1001	2390
0
*/

	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>
D
davidbuzatto

Oi Luiz,

No UVa, só 6 pessoas conseguiram responder.

[]'s

L
Luiz_Augusto_Prado

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.

D
davidbuzatto

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 :wink:

[]'s

L
Luiz_Augusto_Prado

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”

<script type="text/javascript" src="biginteger.js"></script>
<script>
	/*
	in	out
	12	2199
	20	803
	1001	2390
	0
	*/
	var fatoriais = [
		 BigInteger.parse(["120"],10)
		,BigInteger.parse(["720"],10)
		,BigInteger.parse(["5040"],10)
		,BigInteger.parse(["40320"],10)
		,BigInteger.parse(["362880"],10)
		,BigInteger.parse(["3628800"],10)
	]
	var chaves = [
		 BigInteger.parse(["120"],10)
		,BigInteger.parse(["2480"],10)
		,BigInteger.parse(["15280"],10)
		,BigInteger.parse(["38720"],10)
		,BigInteger.parse(["42800"],10)
		,BigInteger.parse(["17120"],10)
	] 
	function somatoria(x)
	{
		x-=2 
		t=-5+x; 

		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>
L
Luiz_Augusto_Prado

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/

<script type="text/javascript" src="jsbn.js"></script>
<script type="text/javascript" src="jsbn2.js"/></script>

<script>
	var fatorial0 = new BigInteger(""+120,10)
	var fatorial1 = new BigInteger(""+720,10)
	var fatorial2 = new BigInteger(""+5040,10)
	var fatorial3 = new BigInteger(""+40320,10)
	var fatorial4 = new BigInteger(""+362880,10)
	var fatorial5 = new BigInteger(""+3628800,10)

	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>
Criado 26 de janeiro de 2012
Ultima resposta 28 de jan. de 2012
Respostas 29
Participantes 3

Topicos relacionados

Recomendaçoes sobre Livro de Fisica 26 respostas Origem do termo bacalhau 12 respostas Cabeçalho de um JTable 6 respostas Como fazer para um JPanel receber JLabel dinâmicamente 5 respostas Setar foco em celula Jtable 10 respostas
Fiap Graduacao em Tecnologia — FIAP Analise e Desenvolvimento de Sistemas, Engenharia de Software e mais
Casa do Codigo Casa do Codigo — Livros de tecnologia Livros de programacao, infraestrutura e inovacao