← Euler Lab
#013

Suma Grande

Cargando Python...
← 012 014 →

Large Sum

Calcula los primeros 10 dígitos de la suma de 100 números de 50 dígitos cada uno.

● BigInt ● Precisión arbitraria ● Overflow

1 ¿Por qué este problema es interesante?

A primera vista parece trivial: sumar 100 números. Pero hay un detalle crucial: cada número tiene 50 dígitos. Esto rompe la mayoría de lenguajes de programación.

El Problema: Integer Overflow

En la mayoría de lenguajes, los enteros tienen un tamaño fijo:

32 bits
2,147,483,647
~2 mil millones
64 bits
9.2 × 1018
~19 dígitos
Nuestros números
1050
50 dígitos 💥

Un número de 50 dígitos necesitaría ~166 bits. ¡No cabe ni en un entero de 128 bits!

¿Qué pasa cuando hay overflow?

C / C++ Overflow silencioso 
int x = 2147483647;
x = x + 1;
// x = -2147483648 😱
// ¡Se volvió negativo!
Java Overflow silencioso 
long x = 9223372036854775807L;
x = x + 1;
// x = -9223372036854775808
// También negativo
JavaScript Pérdida de precisión 
let x = 9007199254740992;
x = x + 1;
// x = 9007199254740992
// ¡No cambió! 😱
Python Precisión arbitraria 
x = 10**100
x = x + 1
# x = 100000...00001
# ¡Funciona perfecto! ✓

¿Cómo funciona el overflow?

Con 8 bits puedes representar números del 0 al 255. Si sumas 255 + 1:

255 en binario:

1
1
1
1
1
1
1
1

255 + 1 = ¿256? No, = 0:

1
0
0
0
0
0
0
0
0

El bit 9 se pierde → resultado = 0

Los 100 números de 50 dígitos:

Nota: Los primeros 11 dígitos están resaltados. Spoiler: solo necesitas esos para obtener la respuesta.

Insight: ¿Necesitas los 50 dígitos?

Si solo queremos los primeros 10 dígitos de la suma, ¿necesitamos sumar números completos de 50 dígitos?

No. Los dígitos del final (posiciones 12-50) no pueden afectar los primeros 10 dígitos de la suma porque el "carry" máximo de 100 sumas es solo 2 dígitos.

Podríamos usar solo los primeros 13 dígitos de cada número y obtener la misma respuesta. Pero en Python, ¿para qué molestarse? Sumamos todo sin problema.

Primeros 10 dígitos
5537376230
Suma total (dígitos)
52

2 Python: Precisión Arbitraria Nativa

En Python, los enteros pueden ser tan grandes como quieras. No hay límite de 32 o 64 bits. El único límite es la memoria RAM.

¿Cómo lo hace Python?

Python representa números grandes como un array de "dígitos" en base 2³⁰ (o 2¹⁵ en sistemas de 32 bits):

# Internamente, un número grande se almacena así:

12345678901234567890

# → [dígito₀, dígito₁, dígito₂, ...] en base 2³⁰

# Cada "dígito" cabe en un entero de máquina

Las operaciones (+, -, ×, ÷) se implementan como algoritmos sobre estos arrays, similar a como harías suma larga en papel pero en base 2³⁰.

Python — Solución directa
// Output aparecerá aquí

Desglose del código

int(n)

Convierte un string a entero. Python automáticamente usa precisión arbitraria si el número es grande. No hay que hacer nada especial.

sum()

Suma todos los elementos de una lista. Funciona con enteros de cualquier tamaño.

str(n)[:10]

Convierte el número a string y toma los primeros 10 caracteres (dígitos).

Python — One-liner
// Output aparecerá aquí

El Shortcut: Solo los primeros dígitos

Si quisiéramos optimizar (por ejemplo, en C sin BigInt), podríamos usar solo los primeros 13 dígitos:

100 números × primer dígito máximo (9) = 900 de carry máximo
→ Solo necesitamos 3 dígitos extra de margen
→ 10 + 3 = 13 dígitos por número son suficientes
Python — Shortcut (no necesario pero didáctico)
// Output aparecerá aquí

¿Y en otros lenguajes?

JavaScript: Usar BigInt (desde ES2020): BigInt("123456...")

Java: Usar java.math.BigInteger

C/C++: Usar librerías como GMP, o implementar aritmética de strings

Rust: Crate num-bigint

✓ Integer overflow ✓ Precisión arbitraria ✓ BigInt en Python ✓ Conversión str ↔ int