Riepilogo delle cifre!

Question

Hi Ho cercato questo problem:

Suppose P(n) is sum of digits of 2^n
For example:
As 2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26,so P(15)=26.
Catulate sum of the P(n) for n=1 to 10000.

Ecco il mio python code che sta dando 67.783.431 come risposta, ma il giudice non sembra essere d'accordo su questo:

def P(n): 
    n = int(1<<n) 
    S = 0 
    while n != 0: 
     S += (n%10) 
     n /= 10 
    return S 

Sum = 0 
for i in range(1,10001): 
    Sum += P(i) 
else: 
    print(Sum) 

Qualcuno potrebbe dirmi cosa c'è che non va nel mio approccio? Sarei grato se qualcuno mi indicasse una soluzione matematica per lo stesso.

Answer 1

Se avessi mostrato i commenti, avresti notato che i proprietari del sito, o il problema mai Nostre, è un deficiente.

Intendeva dire da "0 a 10000", non "1 a 10000", ma a quanto pare il problema non può essere modificato, o il manutentore non vuole farlo.

La somma è disattivata di 1 poiché 1<<0 è 1, che aggiunge 1 alla somma.

provare a inviare 67783432.

Nota: mi rendo conto che chiamare i responsabili del sito o il manutentore un deficiente potrebbe sembrare duro, ma quando la pubblicazione di contenuti su un sito a proposito di "Matematica", la precisione è un po importante. Avere un tale sito senza l'abilità, o il requisito, di risolvere problemi sbagliati, mi sembra abbastanza stupido.

Answer 2

La soluzione richiede molto tempo per essere eseguita (più di un minuto, comunque). Esiste un limite di tempo imposto dal giudice per quanto tempo le soluzioni possono impiegare per eseguire?

Inoltre, se si utilizza Python 3, l'operatore di divisione() produce sempre un risultato in virgola mobile. In Python 2, il risultato verrebbe troncato a un intero con input di tipo intero.

In realtà, con Python 3 ottengo un errore di overflow:

Traceback (most recent call last): 
    File "<stdin>", line 2, in <module> 
    File "<stdin>", line 6, in P 
OverflowError: int/int too large for a float 

Answer 3

Ecco un'implementazione alternativa che conferma la vostra risposta è corretta:

>>> sum(reduce(lambda x, y: x + int(y), str(2**n), 0) for n in xrange(1, 10001)) 
67783431 

O uno che memoizes:

>> reduce(lambda x, y: (sum(int(c) for c in str(x[1]*2)) + x[0], x[1]*2), xrange(0, 10000), (0,1))[0] 
67783431 

Answer 4

Una soluzione più elegante in termini di programmazione funzionale potrebbe essere:

>>> P = lambda n: sum(map(int, str(1 << n))) 
>>> sum(P(i) for i in xrange(10001)) 
67783432 

(nota questo calcola la somma di P (i) per i = da 0 a 10000.)

Answer 5

In realtà, poiché Java non può produrre numeri così grandi (a meno che tu non usi la classe BigInteger - che non ho mai usato), è meglio se usi linguaggi flessibili come Python

Python mi ha dato 2 ** 1000.è un numero molto grande la cui soluzione è

provare questo in pitone

a = 2 ** 1000 stampa (a)

poi prendere l'uscita pitone come stringa e prendere somma ogni cifra