Watch integer width

Almost every one of these problems is trivial in Python and a trap in C, for the same reason: Python's int is an arbitrary-precision "bignum" that grows to fit whatever you compute, while C's integers are fixed-width boxes that overflow the moment a value outgrows them. The takeaway is a habit: when you translate a working Python solution to C — as every problem here does — stop at each multiply, sum, and power and ask how big can this actually get? The number that matters is not the final answer but the largest intermediate value on the way to it — and, as the later problems show, the places Python does lose exactness are the fixed-width NumPy array underneath it and the 53-bit float.

The idea

Python never makes you think about width. 2**1000, product, pow(i, i, 10**10) — the interpreter promotes to a bignum silently and the arithmetic is exact up to the limits of memory. C gives you a fixed menu, and picking the wrong item is a silent, data-dependent bug: signed overflow is undefined behaviour, so a value that fits on your test case and wraps on the real one may still "run fine" and just print the wrong number. The widths worth memorising:

C type signed max roughly
int (32-bit) $2^{31}-1$ $2.1 \times 10^{9}$
long long / int64_t $2^{63}-1$ $9.2 \times 10^{18}$
unsigned long long $2^{64}-1$ $1.8 \times 10^{19}$
__int128 (GCC/Clang) $2^{127}-1$ $1.7 \times 10^{38}$

Against that menu, the problems in this topic fall into three tiers, and each tier has a standard C response.

Tier 1 — reach for 64 bits. The value overflows a 32-bit int but fits comfortably in a long long. Problem 8 multiplies thirteen digits: $9^{13} \approx 2.5 \times 10^{12}$, past int but far short of long long. Problem 6 squares a sum near $n(n+1)/2$; for the real $n$ the square lands around $10^{10}$. The whole fix is to declare the accumulators long long and move on:

long long product = 1;                 /* not int — 9^13 overflows 32 bits */
for (int j = i; j < i + length; j++)
    product *= (number[j] - '0');

"Fits in 64 bits" is a claim to check, not assume, once the answer gets close to the ceiling. Problems 240 and 242 land at 80–97% of $2^{63}-1$, and both C ports keep long long only after bounding every term added; 242's answer grows like $t^{\log_2 3}$, so a modestly larger input would cross the line. Problem 365's answer sits near $9 \times 10^{18}$ — inside long long, but close enough that the port takes an unsigned __int128 accumulator as the honest choice rather than defend a margin of a few percent. And the claim has to hold for every input the solution is run on, not only the headline one: problem 531's main total sits inside half the signed range, but one of its larger test windows sums past $2^{63}$, so its accumulator is unsigned __int128 too. The test cases, not the problem statement, set the width.

Tier 2 — the intermediate overflows 64 bits, even though the answer doesn't. Problem 48 sums $i^i \bmod 10^{10}$. The answer is a ten-digit number, but computing it multiplies two operands each near $10^{10}$, and their product $\approx 10^{20}$ blows past a signed 64-bit long long. The reduced result fits; the multiply on the way to it does not. Two mitigations, often combined: reduce modulo at every step so operands stay small, and widen the multiply itself to a type that holds the product before you reduce:

/* operands near 10^10, product ~10^20 — widen to __int128 before reducing */
result = (__int128)result * base % mod;

Where __int128 isn't available, the same job is done by a mulmod built from repeated doubling, or by splitting the operands into high and low halves.

The modulus decides the tier, so read it first. Problem 455 iterates $x \leftarrow n^x \bmod 10^9$ for a million bases at once: residues stay below $10^9$, every product below $10^{18} < 2^{63}$, and plain int64 square-and-multiply is safe — in C and in the vectorised NumPy alike, with no wider type anywhere. Move the modulus from $10^9$ to $10^{10}$, as problem 48 does, and the same loop needs the widened multiply above.

The single most common Tier 2 site in this collection is the modular squaring inside Miller–Rabin: a candidate near $3 \times 10^9$ already squares past $2^{63}$ (problem 248), so problems 241, 245 and 248 all route that one multiply through __int128 — which is also how the C keeps pace with CPython's compiled pow(a, d, n). The widened operation need not be a modular one: problem 255 keeps every interval bound and its total in long long and widens only the final rounding step, which multiplies by $2 \times 10^{10}$.

The other half of Tier 2 is the accumulator. A running total of many 64-bit terms can clear $2^{64}$ even when no single term comes close: problem 421's total grows as $4N\pi(M)$ and passes $2^{64}$ by a quarter, and 272, 276, 297, 882 and 963 all have sums that outgrow 64 bits while the per-step values fit comfortably. Problem 473 shows how a representation choice spends headroom: it works in $\mathbb{Z}[\varphi]$ with every term doubled ($2\varphi^k = L_k + F_k\sqrt5$) so the Lucas and Fibonacci coefficients stay integers, which pushes a single rational part to about $4 \times 10^{18}$ — still a long long, barely — and leaves the running total to __int128. The fix is an unsigned __int128 total — and then a small printer, because printf has no conversion for it:

static const char *format_u128(unsigned __int128 value) {
    static char digits[40];                        /* 2^128 has 39 decimal digits */
    char *cursor = digits + sizeof digits - 1;
    *cursor = '\0';
    do { *--cursor = (char)('0' + (int)(value % 10)); value /= 10; } while (value);
    return cursor;
}

Sometimes it is the input that has outgrown the box. Problem 551 follows the sequence $a_{k+1} = a_k + s(a_k)$ ($s$ the digit sum) out to $n = 10^{20}$ — already past $2^{64}$ before any arithmetic happens — and its memoised digit-block jumps count steps and carry low parts of the same size. The C makes unsigned __int128 the working type throughout, stops its table of powers of ten at $10^{38}$, the largest that type holds, and parses the argument by hand, because the runner's parse_int stops at $2^{63}$; the printer above handles the way out.

Even 128 bits is a box with walls. Problem 241 carries exact fractions in unsigned __int128 and needs two guards to keep every product under $2^{128}$, one of them capping a product of primes at the largest primorial that fits — a cap the Python mirrors so both run the identical algorithm. Problem 698 hits the wall from the other side. Its counts of digit strings pass 64 bits (one input is $10^{30}$, which parse_int cannot even read), so the C counts in unsigned __int128 — but the Python's multinomial $L!/(a!\,b!\,c!)$ has a numerator that overflows even that. The port rewrites it as a product of two binomials from a Pascal table, $\binom{r}{x}\binom{r-x}{y}$, whose every intermediate is at most $3^r$; and since $3^{80} < 2^{128}$, it caps the string length at 80 and says so in a #define. The answer is the same number either way — what changed is the order the arithmetic runs in, so that no step is ever larger than the result it builds. Problem 659 makes the same choice between two correct formulas. To lift a root of $4k^2 + 1$ from $p^e$ to $p^{e+1}$ (Hensel's lemma) it could take a Newton step modulo $p^{e+1}$, whose products outgrow 64 bits as the power climbs; it instead solves for one digit $s$ modulo $p$ alone, so every operand stays below $p$ or $f(k)$, and only the final $k + p^e s$ is formed in __int128.

Tier 3 — no fixed width is enough; you must build the bignum yourself. Problem 16 wants the digit sum of $2^{1000}$ — a 302-digit number — and problem 25 hunts the first 1000-digit Fibonacci term. No C integer comes close. Here you re-implement, by hand, the arbitrary precision Python gave you for free: store the number as an array of decimal digits and do schoolbook long multiplication with carries.

/* digits[] little-endian; multiply the whole big number by base, once */
int carry = 0;
for (int j = 0; j < len; j++) {
    int val = digits[j] * base + carry;
    digits[j] = (unsigned char)(val % 10);
    carry = val / 10;
}
while (carry > 0) { digits[len++] = (unsigned char)(carry % 10); carry /= 10; }

When the bignum is only needed some of the time, don't pay for it all of the time. Problem 254's candidate length reaches about $10^{51}$ for the largest inputs, so its C uses GMP mpz_t — but keeps a native unsigned long long fast path for every candidate of at most 19 digits, which covers the dense small cases, and falls back to GMP only on the sparse large ones where a candidate or two settles the answer. Problem 988 makes the opposite call. Its headline total sits just below $2^{63}$ — a long long would do — but the extra benchmark inputs produce 27- and 101-digit totals from the same $O(ab)$ dynamic programme, so the C runs that DP over GMP throughout. With a table of a few thousand cells, the bignum costs about a millisecond, and no fast path is worth the second code path. The test cases set the tier, not just the width inside one. Problem 581 splits by quantity instead of by case: its Pell equations $x^2 - d\,y^2 = 1$ have $d$ past $2^{64}$ and $d\,y^2$ near $4 \times 10^{41}$ — beyond even __int128 — so the continued-fraction and recurrence arithmetic runs in GMP, but the hot smoothness test runs on $y$ alone, which a fixed cap holds below $10^{10}$, and so stays in native 64-bit words.

That is the whole spectrum: pick a wider built-in, widen just the risky operation, or hand-roll a bignum — in rising order of effort, chosen by how far the biggest intermediate exceeds the box.

Before climbing it, ask whether the big part of the number carries any information. Problem 615 wants the millionth number with at least a million prime factors — values of $2^{10^6}$ and up, which no bignum could usefully enumerate. But every early member is mostly twos, and once each carries at least $2^{k-36}$, dividing that common factor out maps the head of the list, in order, onto numbers with at least 36 prime factors — all below $2^{53}$, ordinary 64-bit integers. The huge factor comes back only at the end, as a modular power. The cheapest overflow fix is a reformulation in which the big number never exists.

Three places width hides

Inside a bound test. A guard like n1 * n1 * e < room reads as harmless, but the products a bound test exists to reject are exactly the large ones, so they are exactly the ones that overflow. In problem 251 that product wrapped for a large divisor, the wrapped value passed the test, and the count came out inflated — invisible on the main input, caught only by the larger benchmark cases. Problem 245's prefix tests $m p^2$ have the same shape. There are two fixes: evaluate the test in __int128 (245), or rearrange it so the large product is never formed (251), comparing against a cap computed once:

/* n1*n1*e < room  <=>  n1 <= isqrt((room - 1) / e) — no product can wrap */
unsigned long long cap = isqrt((room - 1) / e);

Inside NumPy. Python's int cannot overflow, but a NumPy int64 / uint64 array is a C array, and its arithmetic wraps just as silently. Problem 421 sums millions of uint64 terms; turning the array sum into a Python int afterwards does not help, because the array sum is what overflows. It splits each term into 32-bit halves first, so neither partial sum can wrap:

total = (int((terms >> 32).sum()) << 32) + int((terms & 0xFFFFFFFF).sum())

Problem 249 sums its counters in chunks of 1024 for the same reason, and problem 1010 trusts its int64 arithmetic only after proving the bound: every term counts a partition, the counts sum to an identity near $2.8 \times 10^{18}$, and --show checks that identity on every run. Problem 659's total reaches $4 \times 10^{21}$, so its Python adds the high and low $10^9$-digit halves separately before taking the last 18 digits.

Sometimes the value that overflows is one the computation would never use. Problem 749 sums the $k$-th powers of a number's digits as one int64 matrix product over a table $(0^k, \dots, 9^k)$, and at large $k$ the entry $9^k$ alone passes $2^{63}$. But a digit whose $k$-th power exceeds $10^d$ cannot occur in any row still alive at that $k$, since its power alone would overshoot every $d$-digit target. So the table stores 0 there, and every sum that is actually formed stays below $d \cdot 10^d$. This is the bound-test lesson again: the large values are the ones the search rejects, so reject them before the arithmetic instead of after it.

Inside a float. A double is a box too: its 53-bit significand holds every integer up to $2^{53} \approx 9 \times 10^{15}$ exactly, and beyond that it rounds. Problem 341 needs the least $i$ with $i(i+1) \ge c$ for a million values of $c$ at once, and takes it from the quadratic formula in floating point — safe because $c$ stays near $10^{14}$, inside the exact range, and made exact by one integer check that nudges the root by one if rounding landed it on the wrong side:

i = np.ceil((np.sqrt(4.0 * c + 1.0) - 1.0) / 2.0).astype(np.int64)
i += i * (i + 1) < c        # float rounding: correct to the exact root

The float gets within one; the integer comparison, done in a type that is exact, settles it. Problem 632 does the same for an integer square root in C, starting from sqrtl (a long double, 64-bit significand) and correcting. Problem 962 needs the same root of a bound $Dx\beta^2$ that can exceed $2^{63}$ itself, so it forms the argument in unsigned __int128 and only then hands it to sqrtl. Never let the float result stand unchecked once its argument nears $2^{53}$ — or past it, where consecutive integers share one double.

When the answer itself is real, the job is to decide where exactness ends. Problem 930 sums expected hitting times over every $(n, m)$ pair. Each term weights an exact combinatorial count — up to $16^{16}$, past 64 bits, so the C keeps it in unsigned __int128 — by a ratio of cosines that is irrational. The counts stay integers for as long as they can, and the conversion to floating point happens once per term, not once per multiply. The sum of many such terms then gets a better accumulator: Python uses math.fsum, which tracks the rounding error of every addition, and the C adds in long double. Width and precision are the same budget, spent in different units.

How to reason about it

  • Bound the intermediate, not the answer. A ten-digit result computed through a twenty-digit product is Tier 2, not Tier 1. Trace the largest value that ever exists, including inside a multiply before the % mod lands (problem 48), or a factorial or power that is reduced later (problems 97, 288). The intermediate need not be on the path to the answer at all: in problem 943 a deep subtree's leaf count can outgrow the root's, so its counts and sums are __int128. This is where a Python-to-C port most often goes wrong.
  • Reduce early to stay small — or spend the headroom on purpose. In modular problems, taking the remainder after every operation keeps operands small; that is what keeps modular exponentiation (problems 48, 97) inside 64 bits between multiplies — leaving only the single product to widen. But the % is the expensive part, and the width you have is a budget. Problem 249's fold can at most double a counter, so starting below $10^{16}$ it runs ten folds before reducing — the worst case, $2^{10} \cdot 10^{16} \approx 1.02 \times 10^{19}$, still fits an unsigned 64-bit word — and that batching cut the Python run time by more than half. A wider accumulator buys the same deferral: problem 866's convolution adds thousands of products, each below $2^{60}$, so its C sums a whole row in unsigned __int128 and reduces once per row instead of once per multiply-add.
  • Make the width limit an explicit input limit. Where a representation caps the input, say so up front instead of letting it wrap later. Problem 421's modular multiply needs $p^2 < 2^{64}$, so both versions reject a prime bound $M \ge 2^{32}$ on entry; problem 401 likewise asserts its modulus is below $2^{31}$, so residue products fit its NumPy int64 chunks; problem 963 packs a shape into an unsigned long long, which caps it at 13 trits.
  • Mind the order and exactness of mixed operations. (2*n+1)*(n+1)*n / 6 (problem 6) must keep the product exact before the division; reorder or widen so no partial product overflows and the final divide stays whole. Under a modulus this gets sharper. Problem 401 needs $x(x+1)(2x+1)/6 \bmod 10^9$ with $x$ up to $10^{15}$: the exact product is near $2 \times 10^{45}$, and 6 has no inverse modulo $10^9$, so "reduce, then divide" is not an option. The fix is to divide the factors — 2 goes into $x$ or $x+1$, 3 into exactly one of the three, chosen by $x \bmod 3$ — leaving three integers that each fit in 64 bits and can be reduced before they are multiplied. Problem 521 starts its tables at $v(v+1)/2$ for $v$ near $10^{12}$, and its NumPy version halves whichever factor is even before multiplying, so the product never has to exist at double size. The C takes the other road and forms the product in __int128.
  • Some quantities must be exact before they are reduced. Problem 632 multiplies together the non-zero counts $C_k$ modulo $10^9+7$ — and a count that happens to be a multiple of the modulus reduces to 0 while still being non-zero, so a "reduce first" version would silently drop a factor. The counts come from a binomial inversion, an alternating sum whose terms $\binom{j}{k} A_j$ approach $2^8 \cdot 10^{16}$ before they cancel down to the result: the intermediates outgrow the answer because of the cancellation. The C accumulates each $C_k$ in __int128, exactly, and reduces only after the sum is complete.
  • Staying in integers costs width. A count with a fraction in its formula can avoid rationals by scaling the denominator out and dividing it back at the end, but every intermediate then carries the scale factor. Problem 987 counts poker deals by inclusion–exclusion over straights that are forced to be flushes. Its weights would include $1/(c-k)!$ for interchangeable straights, so the DP multiplies in a binomial instead, scales each final state by a factorial and divides the grand total by $m!$. The answer alone, about $1.1 \times 10^{19}$, already passes $2^{63}$. The total before that division is larger still, and the inclusion–exclusion terms carry signs. An unsigned long long would hold the answer but not the negative terms on the way to it, so the C carries every weight in signed __int128. Count the sign bit when you size a type for an alternating sum.
  • Signed overflow is undefined, so it hides. Unlike Python, a C overflow throws no error and may pass small tests. When a C port disagrees with a verified Python solution only on the large input, an overflowed intermediate is the first suspect — reach for long long, then __int128, then a digit array. Unsigned overflow, by contrast, is defined: it wraps modulo $2^{64}$, so a total that is off by an exact multiple of $2^{64}$ points straight at the accumulator.
  • Let the Python version be the oracle — where it is pure Python. Python's own integers can't overflow, so arithmetic done in them is trustworthy by construction. Port to C for speed, but keep the Python solution as the reference the C output must match. That guarantee stops at the NumPy boundary: a vectorised solution needs the same width audit as its C port (problems 249, 341, 401, 421, 455, 521, 659, 749, 1010), and a brute force in plain Python ints is the better oracle for both.

Problems114 / 114

  • ● 0003 — Largest Prime Factor
  • ● 0005 — Smallest Multiple
  • ● 0006 — Sum Square Difference
  • ● 0008 — Largest Product in a Series
  • ● 0009 — Special Pythagorean Triplet
  • ● 0016 — Power Digit Sum
  • ● 0025 — $1000$-digit Fibonacci Number
  • ● 0031 — Coin Sums
  • ● 0048 — Self Powers
  • ● 0050 — Consecutive Prime Sum
  • ● 0055 — Lychrel Numbers
  • ● 0058 — Spiral Primes
  • ● 0065 — Convergents of $e$
  • ● 0066 — Diophantine Equation
  • ● 0071 — Ordered Fractions
  • ● 0076 — Counting Summations
  • ● 0080 — Square Root Digital Expansion
  • ● 0087 — Prime Power Triples
  • ● 0094 — Almost Equilateral Triangles
  • ● 0097 — Large Non-Mersenne Prime
  • ● 0108 — Diophantine Reciprocals I
  • ● 0110 — Diophantine Reciprocals II
  • ● 0111 — Primes with Runs
  • ● 0114 — Counting Block Combinations I
  • ● 0116 — Red, Green or Blue Tiles
  • ● 0119 — Digit Power Sum
  • ● 0120 — Square Remainders
  • ● 0121 — Disc Game Prize Fund
  • ● 0128 — Hexagonal Tile Differences
  • ● 0136 — Singleton Difference
  • ● 0138 — Special Isosceles Triangles
  • ● 0140 — Modified Fibonacci Golden Nuggets
  • ● 0147 — Rectangles in Cross-hatched Grids
  • ● 0148 — Exploring Pascal's Triangle
  • ● 0157 — Base-10 Diophantine Reciprocal
  • ● 0166 — Criss Cross
  • ● 0176 — Common Cathetus Right-angled Triangles
  • ● 0178 — Step Numbers
  • ● 0180 — Golden Triplets
  • ● 0184 — Triangles Containing the Origin
  • ● 0189 — Tri-colouring a Triangular Grid
  • ● 0192 — Best Approximations
  • ● 0195 — $60$-degree Triangle Inscribed Circles
  • ● 0196 — Prime Triplets
  • ● 0198 — Ambiguous Numbers
  • ● 0202 — Laserbeam
  • ● 0208 — Robot Walks
  • ● 0209 — Circular Logic
  • ● 0210 — Obtuse Angled Triangles
  • ● 0217 — Balanced Numbers
  • ● 0218 — Perfect Right-angled Triangles
  • ● 0221 — Alexandrian Integers
  • ● 0233 — Lattice Points on a Circle
  • ● 0234 — Semidivisible Numbers
  • ● 0236 — Luxury Hampers
  • ● 0237 — Tours on a $4 \times N$ Playing Board
  • ● 0240 — Top Dice
  • ● 0241 — Perfection Quotients
  • ● 0242 — Odd Triplets
  • ● 0245 — Coresilience
  • ● 0248 — Euler's Totient Function Equals 13!
  • ● 0249 — Prime Subset Sums
  • ● 0250 — $250250$
  • ● 0251 — Cardano Triplets
  • ● 0254 — Sums of Digit Factorials
  • ● 0255 — Rounded Square Roots
  • ● 0259 — Reachable Numbers
  • ● 0272 — Modular Cubes, Part 2
  • ● 0276 — Primitive Triangles
  • ● 0277 — A Modified Collatz Sequence
  • ● 0288 — An Enormous Factorial
  • ● 0297 — Zeckendorf Representation
  • ● 0313 — Sliding Game
  • ● 0321 — Swapping Counters
  • ● 0341 — Golomb's Self-describing Sequence
  • ● 0365 — A Huge Binomial Coefficient
  • ● 0387 — Harshad Numbers
  • ● 0401 — Sum of Squares of Divisors
  • ● 0420 — $2 \times 2$ Positive Integer Matrix
  • ● 0421 — Prime Factors of $n^{15}+1$
  • ● 0429 — Sum of Squares of Unitary Divisors
  • ● 0455 — Powers with Trailing Digits
  • ● 0473 — Phigital Number Base
  • ● 0484 — Arithmetic Derivative
  • ● 0487 — Sums of Power Sums
  • ● 0521 — Smallest Prime Factor
  • ● 0531 — Chinese Leftovers
  • ● 0551 — Sum of Digits Sequence
  • ● 0581 — $47$-smooth Triangular Numbers
  • ● 0615 — The Millionth Number with at Least One Million Prime Factors
  • ● 0632 — Square Prime Factors
  • ● 0659 — Largest Prime
  • ● 0686 — Powers of Two
  • ● 0694 — Cube-full Divisors
  • ● 0698 — 123 Numbers
  • ● 0704 — Factors of Two in Binomial Coefficients
  • ● 0745 — Sum of Squares II
  • ● 0749 — Near Power Sums
  • ● 0751 — Concatenation Coincidence
  • ● 0787 — Bézout's Game
  • ● 0788 — Dominating Numbers
  • ● 0820 — $N$thDigit of Reciprocals
  • ● 0862 — Larger Digit Permutation
  • ● 0866 — Tidying Up B
  • ● 0882 — Removing Bits
  • ● 0930 — The Gathering
  • ● 0943 — Self Describing Sequences
  • ● 0944 — Sum of Elevisors
  • ● 0962 — Angular Bisector and Tangent 2
  • ● 0963 — Removing Trits
  • ● 0974 — Very Odd Numbers
  • ● 0987 — Straight Eight
  • ● 0988 — Non-attacking Frogs
  • ● 1010 — March of the Penguins