Sommatoria in binario – Programmare con Python

Olimpiadi di Matematica – Fase nazionale a squadre

(…) Siano $z(n)$ e $u(n)$ due funzioni che restituiscono rispettivamente il numero di zeri e di uni nella scrittura in base 2 del numero $n$ , e sia $\displaystyle f(n)=\frac{(-1)^{z(n)}}{2^{u(n)}}$ .
Per esempio, quindi, $\displaystyle f(13)=f(1101_2)=\frac{(-1)^1}{2^3} = -\frac{1}{8}$ , mentre $\displaystyle f(17)=f(10001_2)=\frac{(-1)^3}{2^2}=-\frac{1}{4}$ .
Calcolare quanto vale la somma $f(1)+f(2)+f(3)+...+f(1023)$ .
Rispondere con la somma di numeratore e denominatore della frazione ridotta ai minimi termini.

Vedi la discussione

import fractions


def f(n, z_n, u_n):
    num = (-1)**z_n                       # Numeratore
    den = 2**u_n                          # Denominatore 
    return fractions.Fraction(num, den)   # Frazione


F_n=0                      # Somma parziale <-- 0
for n in range(1, 1024):   # Per n da 1 a 1023 
    n2 = bin(n)            # Numero in binario con prefisso 0b
    n2 = n2[2:]            # Numero in binario senza prefisso
    z_n = n2.count('0')    # Numero di zeri
    u_n = n2.count('1')    # Numero di uni
    f_n = f(n, z_n, u_n)   # Funzione di n
    F_n += f_n             # Somma parziale aggiornata

    print("%4d | %10s | %d | %2d | %6s | %8s" %(n, n2, z_n, u_n, f_n, F_n))

risposta=F_n.numerator+F_n.denominator
print()
print("Risposta =", risposta)

Output

   1 |          1 | 0 |  1 |    1/2 |      1/2
   2 |         10 | 1 |  1 |   -1/2 |        0
 ... |        ... | . |  . |    ... |      ...
  13 |       1101 | 1 |  3 |   -1/8 |      3/8
 ... |        ... | . |  . |    ... |      ...
  17 |      10001 | 3 |  2 |   -1/4 |     9/16 
 ... |        ... | . |  . |    ... |      ...
1022 | 1111111110 | 1 |  9 | -1/512 |   85/256
1023 | 1111111111 | 0 | 10 | 1/1024 | 341/1024

Risposta = 1365