Fa unes setmanes em va apretar per esbrinar quin és el número primer més petit les xifres del qual sumin un primer més gran que 100. No té cap interès científic, però m’ha servit per a recordar una mica el C i veure les diferències de temps d’execució amb el Python, que és el llenguatge de programació que darrerament faig servir per a scripts i proves de concepte.

El número que busco ha de tenir, com a mínim, 12 xifres per raons òbvies, i ha de ser més gran que 299.999.999.999 (que és divisible per 7). Per trobar-lo he fet servir una aproximació de “força bruta”, comprovant tots els senars des del 299.999.999.999 fins al 999.999.999.999.

Se’m planteja el problema de calcular de forma eficient la suma de les xifres d’un número. Faig una primera aproximació en Python, amb diverses variants:

def suma1(numeroASumar):
    suma = 0
    s = str(numeroASumar)
    for n in range(len(s)):
        suma = suma + int(s[n])
    return suma

def suma2(numeroASumar):
    suma = 0
    s = str(numeroASumar)
    for n in range(len(s)):
        suma = suma + ord(s[n]) - 48
    return suma

def suma3(numeroASumar):
    suma = 0
    s = str(numeroASumar)
    longitud = len(s)
    for n in range(longitud):
        suma = suma + ord(s[n]) - 48
    return suma

def suma4(numeroASumar):
    suma = 0
    s = str(numeroASumar)
    for n in s:
        suma = suma + ord(n) - 48
    return suma

def suma5(numeroASumar):
    suma = 0
    s = str(numeroASumar)
    for n in s:
        suma += ord(n) - 48
    return suma

def suma6(numeroASumar):
    suma = 0
    while (numeroASumar > 0):
        suma += numeroASumar % 10
        numeroASumar /= 10
    return suma

Els resultats que obtinc són (temps mesurats amb la funció time.clock() per les sumes del primer milió d’enters):

algorisme	temps
suma1	8,86
suma2	6,26
suma3	6,24
suma4	4,93
suma5	4,87
suma6	3,62

Vistos els resultats és obvi pensar que la conversió a string consumeix força temps, i que l’aritmètica entera de suma6 és molt més ràpida.

Implemento en C l’algorisme complet, amb la precaució que guardi els resultats parcials a disc i sàpiga reprendre l’execució on ha estat aturada. Deixo el procés uns quants dies amb prioritat baixa. No tinc anotades les diferències de temps d’execució entre C i Python, però són molt grans (ho tornaré a mesurar).

El número buscat és el 399.999.998.999 I només hi ha 3 números primers més petits que 1.000.000.000.000 les xifres del qual sumin 107. Són els 999.998.999.999, 999.999.999.899, 999.999.999.989.