Simplificação de Múltiplos Somatórios

This message was edited 5 times. Last update was at 26/01/2012 13:54:15

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.

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 2000000000.
Para valores de n variando de 1 a 20 eu tenho os seguintes resultados. Imagem para n = 2000000000.

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

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

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 = 2000000000 (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.

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

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.

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

Tem mais uma coisinha interessante. Veja o número 2000000000 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.

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

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

This message was edited 4 times. Last update was at 26/01/2012 17:07:11

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!

This message was edited 1 time. Last update was at 26/01/2012 16:57:27

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.

This message was edited 1 time. Last update was at 26/01/2012 17:03:36

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

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

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.

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

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

This message was edited 3 times. Last update was at 26/01/2012 17:26:16

Olha só, eu comecei pequeno:

Já sim.

This message was edited 3 times. Last update was at 26/01/2012 17:34:24

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

acho que encontrei um caminho:

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.

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

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