Página 2 de 2

Re: Números especiais

MensagemEnviado: Terça Fev 10, 2009 8:56 pm
por Bruno Oliveira
Sim, Ivo, sou português de Portugal :lol: , e estou registado no PE, o nickname que uso é kuruma (a história deste nome, não tem mistério nenhum, precisava de um nome para registar uma conta de um jogo á muito tempo, que agora já nem jogo computador, e usei um gerador de nomes que lá estava, gerou este nome e olha, fiquei com ele :lol: )

Re: Números especiais

MensagemEnviado: Terça Fev 10, 2009 9:31 pm
por jap
Ivo_Timóteo Escreveu:(...)

Mas como saber que não há números maiores que N que satisfazem a condição? Que N é esse?
Embora ligeiramente fora do âmbito do Quark!, podem tentar demonstrar :) É mesmo muito fácil :D


Lazy, brute force approach:

Código: Seleccionar Todos
"""
Project Euler 30

Sum all numbers that are equal to the sum of the mth power of its digits

@jap-2009 having fun with Quark!
"""

m = 5

def sumdigits(n,m):
    "sum of the mth power of the digits of n"
    return sum(map(lambda c: int(c)**m,str(n)))

# Wild guess that the maximum number of digits is, at most, 10 and try to refine your guess to a smaller number...

for ndigits in range(1,10):
    if ndigits*9**m < 10**ndigits: break
else:
    print "Outch, the numbers can be really huge!!!"
   
# Now we hopefully know an upper bound for the number of digits...

print "Maximum number of digits to search", ndigits
print "Please wait..."

L = filter(lambda n: n == sumdigits(n,m), xrange(10,10**ndigits))

print "The numbers are", L
print "and their sum is", sum(L)

Re: Números especiais

MensagemEnviado: Terça Fev 10, 2009 9:36 pm
por Bruno Oliveira
Gosto desta approach :D

É bastante gira e fácil de perceber :wink:

Re: Números especiais

MensagemEnviado: Terça Fev 10, 2009 9:38 pm
por hexphreak
Por acaso está tecnicamente errada, já que não prova que não existam números com mais de dez dígitos para os quais a condição se verifique :P Mas é extremamente fácil mostrar que apenas números com até seis dígitos o podem fazer...

Re: Números especiais

MensagemEnviado: Terça Fev 10, 2009 9:44 pm
por jap
hexphreak Escreveu:Por acaso está tecnicamente errada, já que não prova que não existam números com mais de dez dígitos para os quais a condição se verifique :P Mas é extremamente fácil mostrar que apenas números com até seis dígitos o podem fazer...


Se existissem números com mais de 10 dígitos que satisfizessem as condições do problema ele não seria colocado no projecto Euler porque o tempo de computação dos ditos números, por qualquer algoritmo razoável, excederia o tempo de execução alocado. Experimenta percorrer simplesmente uma lista de 10000000000 números no teu PC... :lol:

Por isso a guess N=10 (deverei chamar-lhe ansatz?) e depois refiná-la para encontrar um upper bound menor parece-me *tecnicamente* bastante bom, embora insatisfatório, é claro, do ponto de vista matemático... :lol:

Re: Números especiais

MensagemEnviado: Terça Fev 10, 2009 9:52 pm
por Bruno Oliveira
Pois, o tempo de execução é de apenas um minuto, e percorrer uma lista de 10000000000 números deve de certeza levar muito tempo, mesmo num pc bem artilhado :roll:

Re: Números especiais

MensagemEnviado: Quarta Fev 11, 2009 12:38 am
por RicardoCampos
Bruno Oliveira Escreveu:Prof. de facto tanto o 0 como o 1, satisfazem as condições do problema, mas eles dizem para não contar com o 1, pois é uma soma de dígitos, então a resposta é 443839.

As1 = 1^4 is not a sum it is not included.


\sum_{i=1}^1 a_i = a_1

Re: Números especiais

MensagemEnviado: Quarta Fev 11, 2009 11:42 am
por Tharis
Bem, falando em termos de velocidade... É muito verdade que não se conseguem correr 10 000 000 000 iterações no PC em tempo útil, mas como até sou maluco, fui fazê-lo em C :), aqui ficam os resultados e o código:

tharis@tharis-lp:~$ time ./test

real 1m10.905s
user 1m1.104s
sys 0m0.156s


Código: Seleccionar Todos
int main() {
   unsigned long long i;
   const unsigned long long l=10000000000ULL;
   for (i=0;i<l;i++);
   return 0;
}


Não precisava de um unsigned long long, mas pronto, mais vale prevenir do que remediar.... (já agora, alguém me sabe dizer porque é que podia ter usado um long long (signed) em vez de um unsigned long long? :P Matemáticos, it's your turn! (apesar de não ser muito difícil) :P

Continuando, podemos reduzir em o MUITO o tempo de execução, cortando operações e usando cálculos que já efectuámos, bem como, o uso de um JIT (Just in Time Compiler), porque apesar de Python ser interpretado, também é compilado para bytecode... :)

Mostro-vos o JIT do Python que é o Psyco... Chega a reduzir tempos de execução bruscamente (provado por mim em exercícios de grafos). :D

E para o usarem, só precisam de o ter instalado e meter duas linhas de código:

Código: Seleccionar Todos
import psyco
psyco.full()


Atenção que não vou usar o PSYCO neste post. :)

Com o código do Prof. JAP , temos um tempo muito bom para o Python :hands: :
tharis@tharis-lp:~$ time python test.py
Maximum number of digits to search 6
Please wait...
The numbers are [4150, 4151, 54748, 92727, 93084, 194979]
and their sum is 443839

real 0m11.984s
user 0m11.517s
sys 0m0.052s


Mas, será que o podemos melhorar? Eu estou a escrever isto e ainda não fiz as modificações, por isso, estou como vocês: "será que vou conseguir melhorar o código em termos de execução de tempo?" Vamos ver! Pegando no código e assumindo que o Prof. o lançou em Open-Xor (OpenSource) e que podemos modificá-lo.

Aqui ficam os resultados, tal como eu esperava! :D Menos 10 segundos de execução! Acabei de usar programação dinâmica, que é uma das competências em que tenho mais dificuldade e que ando a treinar! Por isso, deixem-me só :hands: a mim próprio! :P

tharis@tharis-lp:~$ time python test.py
Maximum number of digits to search 6
Please wait...
The numbers are [4150, 4151, 54748, 92727, 93084, 194979]
and their sum is 443839

real 0m2.779s
user 0m1.760s
sys 0m0.168s


Aqui fica o código modificado:

Código: Seleccionar Todos
"""
Project Euler 30

Sum all numbers that are equal to the sum of the mth power of its digits

@jap-2009 having fun with Quark!

Modifications by Tharis: dictionary `d' and `sumdigits' function
"""

m = 5

d= dict( [(i,i**m) for i in range(10)] )

def sumdigits(n,m):
    "sum of the mth power of the digits of n"
    global d
    d[n]=d[n/10]+d[n%10]
    return d[n]

# Wild guess that the maximum number of digits is, at most, 10 and try to refine your guess to a smaller number...

for ndigits in range(1,10):
    if ndigits*9**m < 10**ndigits: break
else:
    print "Outch, the numbers can be really huge!!!"
       
# Now we hopefully know an upper bound for the number of digits...

print "Maximum number of digits to search", ndigits
print "Please wait..."

L = filter(lambda n: n == sumdigits(n,m), xrange(10,10**ndigits))

print "The numbers are", L
print "and their sum is", sum(L)


Alguém me consegue encontrar as modificações e explicar porque as fiz? :P :)

Re: Números especiais

MensagemEnviado: Quarta Fev 11, 2009 5:42 pm
por jap
Muito bem! :hands:

O velo truque da "look-up table" funciona sempre! :lol: