Números especiais

[Bruno Oliveira]

Sim, Ivo, sou português de Portugal , 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 )

[jap]

(...)

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

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)

[Bruno Oliveira]

Gosto desta approach

É bastante gira e fácil de perceber

[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 Mas é extremamente fácil mostrar que apenas números com até seis dígitos o podem fazer...

[jap]

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 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...

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...

[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

[RicardoCampos]

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.

As is not a sum it is not included.

[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? Matemáticos, it's your turn! (apesar de não ser muito difícil)

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).

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 :

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! 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ó a mim próprio!

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?

[jap]

Muito bem!

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