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