Positional notation

Positional notation is the convention that a string of digits $d_{k-1} \dots d_1 d_0$ means $\sum_i d_i \, b^i$: each symbol is worth its face value times a power of the base $b$ fixed by where it sits. We use it so constantly that it disappears — and that is exactly why it keeps turning up in Project Euler. A large family of problems define their object by how a number is written rather than by what it is: digit sums, reversals, rotations, palindromes, digits that must or must not appear, numbers glued together by concatenation. Each of those is a question about the representation, and the recurring skill is translating it back into arithmetic on the value, where the real tools live.

Two views of the same number

Every problem on this page lives in the gap between two views:

  • The string view — a sequence of digits you can index, sort, reverse, count and compare. It is how the problem is stated, and in Python it is one str() away.
  • The value view — a polynomial in $b$ with digit coefficients. It is how carries, divisibility and bounds behave, and it is where algebra works.

The basic operations convert between them. n % b reads the last digit, n // b drops it, n * b + d appends one, $\lfloor \log_b n \rfloor + 1$ counts them. Concatenating $a$ and a $k$-digit $c$ is $a \cdot b^k + c$; moving the last digit $d$ of a $k$-digit $n = b\,m + d$ to the front gives $d \cdot b^{k-1} + m$. Once a string operation is written like that, it is an equation — and equations can be solved instead of searched.

For small inputs the string view is fine and honest. Problem 16 asks for the digit sum of $2^{1000}$, and Python's arbitrary-precision integers make that literally sum(int(c) for c in str(2**1000)). Problem 36 wants numbers palindromic in base 10 and base 2; the solution generates only the decimal palindromes — by mirroring a left half, so each is built once rather than filtered out of a million candidates — and tests the binary string with bin(). Problem 52's "permuted multiples" become a string equality on sorted digits, a canonical form for "same multiset of digits". None of these need more than the representation itself.

Turn the string into algebra

The problems get interesting once the search space outgrows the string view. Then the move is to write the digit condition as an equation in the value.

Problem 168 asks for numbers that divide their own right-rotation, below $10^{100}$. Enumerating is absurd, but writing $n = 10m + a$ and the rotation as $a \cdot 10^{k-1} + m = t\,n$ for a digit ratio $t$ solves for $m$ outright: $m = a(10^{k-1} - t)/(10t - 1)$. What was a search over a hundred-digit space becomes a few thousand candidate $(k, a, t)$ triples with one divisibility test each. Problem 932 has the same shape: a number that splits into $a \Vert c$ with $a \Vert c = (a+c)^2$ is the equation $a \cdot 10^d + c = s^2$ with $s = a + c$, which rearranges to $10^d - 1 \mid s(s-1)$ — and that divisibility, over coprime consecutive integers, is solved by the Chinese remainder theorem rather than by scanning. Problem 805 (shifted multiples) and the cyclic numbers behind $142857$ belong to the same family: digit shifts are multiplications by $b$ modulo $b^k - 1$.

Edits and cuts translate the same way. Changing the digit in place $b^k$ by $\delta$ is the offset $\pm\delta\, b^k$. Dropping the leading digit of a $d$-digit number is $n \bmod b^{d-1}$. Cutting the string after its low $k$ digits splits $n = h \cdot b^k + \ell$ into two independent halves. Problem 425 joins primes that differ in one digit, or by one prepended digit. Its solution never touches a string: each prime generates its smaller neighbours as $v - \delta \cdot 10^k$ and $v \bmod 10^{d-1}$. That is one array operation per (place, $\delta$) pair across all primes at once, and a union–find sweep in increasing order does the rest. Problem 637 inserts plus signs between digits. Two facts from the value view tame its $2^{L-1}$ splits. First, merging two parts never lowers the total, because $b\,a + c \ge a + c$. So the digit sum is always the smallest split sum, and it settles most numbers with no search at all. Second, a cut at place $b^k$ divides the number into a high half and a low half. Their split sums can be tabulated separately and joined meet-in-the-middle, so the same few thousand halves serve ten million numbers.

Partial digit constraints become congruences in the same way. Problem 206's square with alternate digits pinned reads its last digits first: the low digits of $n^2$ depend only on the low digits of $n$, because $n^2 \bmod 10^j$ is determined by $n \bmod 10^j$. That one fact cuts the candidates by two orders of magnitude, and it is the whole engine of problem 284's steady squares, where $n^2 \equiv n \pmod{b^k}$ is built up one digit at a time.

Count by position, not by number

The second big family asks how many numbers below some bound have a digit property, or how often a digit is written. Here the move is to iterate over places instead of numbers.

Problem 40's Champernowne digit falls out of the observation that the $d$-digit numbers form a band of exactly $d \cdot 9 \cdot 10^{d-1}$ characters; walk the bands, then a floor division and a modulus locate the digit:

while length_with_num_digits < n:
    num_digits += 1
    length_till_num_digits = length_with_num_digits
    length_with_num_digits += num_digits * 9 * 10 ** (num_digits - 1)

Problem 305 goes much deeper into the same string: it asks where the $n$-th occurrence of a digit pattern starts, at positions around $10^{12}$ and beyond, so scanning is out. The fix is to count instead of find. Let $C(N)$ be the number of occurrences that start inside one of $1 \dots N$. It is monotone, so a binary search for the smallest $N$ with $C(N) \ge n$ finds the right integer. $C$ itself splits into two kinds of occurrence. An occurrence that lies inside one integer is a count of free digits around a fixed window. An occurrence that crosses from $p-1$ into $p$ is the more instructive kind. "$p-1$ ends in this prefix" is just the congruence $p \equiv \text{prefix} + 1 \pmod{10^i}$, and the congruence handles the carry for you. That is the value view doing work the string view cannot: the carry that turns …1999 into …2000 would be awkward to handle as a string, but it costs nothing as a congruence.

Problem 156 counts how often a digit $d$ is written from $0$ to $n$; summed column by column, each place value contributes a closed-form amount, so the count is $O(\log n)$ — a digit-counting function. Problem 162 counts hexadecimal strings containing 0, 1 and A by inclusion–exclusion over forbidden symbols, because "avoid these digits" is a product of per-position choices. And when the property depends on more than one position — problem 145's reversible numbers, where each column of $n + \text{reverse}(n)$ couples mirror digits through the carry — the general tool is digit DP: build the number one place at a time and carry along only the state the property needs (a carry, a remainder, a running digit sum, a "still tight to the bound" flag).

A digit DP can also total the numbers' values, not just count them, because appending is linear. If a state holds $c$ prefixes whose values sum to $t$, appending the digit $d$ to all of them gives a total of $b\,t + d\,c$. A (count, sum) pair per state is therefore closed under the transition:

cnt2[s + d] += cnt[s]
tot2[s + d] += 10 * tot[s] + d * cnt[s]

Problem 776 uses this to sum $n / d(n)$ over about $10^{18}$ terms. The digit sum $d(n)$ takes at most 171 values, so the job reduces to the sum of all $n \le N$ with each digit sum. That is one (count, sum) digit DP, finished exactly with rationals.

At the other extreme, some properties ignore position entirely. Problem 520's simbers constrain only how often each digit occurs: even digits an even number of times, odd digits an odd number of times or not at all. A condition on the digit multiset is the home ground of exponential generating functions. Each digit contributes $\cosh x$ or $1 + \sinh x$, and $L!\,[x^L]$ of the product counts the strings of length $L$. Rewriting $\cosh$ and $\sinh$ in $e^{\pm x}$ makes that count an exact power sum $\sum_k c_k k^L$. Summing over lengths then gives a handful of geometric series, so lengths up to $2^{39}$ cost nothing. The leading zero is handled in the same algebra: pin the first digit to $0$ and the remaining positions must hold an odd number of zeros. When the order of the digits does not matter, stop building numbers place by place and count multisets.

The pages for digit sum, palindromic numbers and pandigital numbers are this tag's most crowded neighbours.

When an operation has no carries, the places come apart completely. Problem 778's "freshman's product" multiplies numbers digit by digit, keeping only the last digit of each product. Digit $i$ of the result depends only on digit $i$ of each factor, so by linearity the sum over all $(M+1)^R$ sequences is $\sum_i 10^i \cdot E_i$, where $E_i$ is a sum over one column alone. Within that column, each factor collapses to a ten-entry histogram of how often each digit appears in place $10^i$ across $[0, M]$ (closed form, from the period-$10^{i+1}$ cycle). The $R$-fold product then becomes an $R$-fold convolution over the digits under multiplication mod 10, which exponentiation by squaring handles in $O(\log R)$ steps. A count with a million digits reduces to a handful of $10 \times 10$ convolutions per column. The general lesson: check whether the carry is real before you build any machinery for it.

Problem 885 is a reminder that position carries weight, not just identity: summing "digits sorted ascending, zeros dropped" over all numbers groups the inputs by digit multiset, and the value of each group follows from where each digit lands — smaller digits occupy the more significant places.

Counting by prefix also runs the other way, as unranking: to find the $n$-th number with a digit property, choose its length and then its digits from the left, at each step subtracting the count of completions under each smaller choice. Problem 698's 123-numbers are a good example. They use only the digits 1–3, and each digit's count must be $0$ or another 123-number. Two facts make the problem tractable. First, among equal-length numbers over a fixed alphabet, numeric order is lexicographic order. Second, the property depends only on the digit counts, so the completions of a prefix total a sum of multinomial coefficients over the admissible count triples. The rank is around $10^{17}$, yet the answer is only 38 digits long. The whole unranking takes $38 \times 3$ such counts.

One digit, far away

The reverse question, "what is the digit at position $n$?", has a value-view answer too. Shift, then read low digits: the ten digits after the decimal point starting at position $n$ are $\lfloor 10^{n+9} x \rfloor \bmod 10^{10}$. Problem 731 asks for them at $n = 10^{16}$ in a Stoneham number $\sum_i 3^{-i} 10^{-3^i}$, where no expansion could ever be written out. Split the floor term by term. For each term $10^{e}/3^i = q_i + r_i/3^i$, the remainder is one modular exponentiation, $r_i = 10^e \bmod 3^i$. The quotient is needed only modulo $10^{10}$, and since $3^i$ is coprime to 10 it is an exact division by a modular inverse. The fractional parts add up to a small carry. The terms not yet started are provably too small to change the floor, so dropping them is exact. This is the same trick as the Bailey–Borwein–Plouffe formula for the hexadecimal digits of $\pi$: a digit deep in an expansion is a residue, not a string you have to reach.

The base is a parameter

Base 10 is an accident of anatomy, and several problems make the point by changing it.

  • Integer bases other than 10. Problem 162 states its count in hexadecimal; problem 36 mixes bases 2 and 10; problem 926 sums the trailing zeros of $n!$ in every base, which turns into counting pairs $(b, k)$ with $b^k \mid n!$ — a question about the prime factorisation, since "trailing zeros in base $b$" is just divisibility by powers of $b$.

  • Several bases at once. Problem 571 wants numbers pandigital in every base from 2 to $n$. It builds candidates as base-$n$ permutations, most significant digit first, and the pruning comes from one fact: a prefix in one base is an interval of values, and an interval fixes the leading digits in every base. The completions of a prefix span $[lo, hi]$, with the unused digits appended in ascending and in descending order. In any base $b$, every number in that range shares the leading digits that $lo$ and $hi$ agree on. If the shared prefix is missing more digits than the free places below it can supply, nothing in the subtree is base-$b$ pandigital. That branch-and-bound test prunes almost every branch long before it reaches the $4 \times 10^8$ leaves of the twelve-digit tree. It is "high digits as bounds" used across bases.

  • The number as a word. Problem 963 plays a game in which moves delete a $0$, $1$ or $2$ from a number's ternary expansion. There the value of $x$ hardly matters. The integer is only a label for a ternary word, and everything follows from the word's structure. The game's number part comes from the word with its $2$s deleted, and its infinitesimal part comes from how many zeros follow each leading $2$. When the object is a word, analyse the word, and stop looking for arithmetic in the value.

  • The base as structure. Problem 288 hands you a number already written as $\sum T_n p^n$ with $0 \le T_n < p$ — that is, its base-$p$ digits — and Legendre's formula in its digit-sum form, $v_p(N!) = (N - s_p(N))/(p-1)$, lets you answer without ever forming $N$. Recognising "this sum is a base-$b$ expansion" is often the whole problem. Problem 396's weak Goodstein sequences repeatedly reinterpret base-$b$ digits in base $b+1$.

  • Exotic bases. Problem 473 uses base $\varphi$ (the golden ratio), problem 558 an irrational base, problem 508 the complex base $i - 1$, and mixed-radix systems such as the factorial number system use place values that are not powers of one base at all. What survives is the core idea — value equals a weighted sum of digit times place — but uniqueness, carry rules and the set of allowed digits must be re-derived for each base, and that is where those problems put their difficulty.

    Problem 473 shows what that re-derivation looks like. Base $\varphi$ uses the digits 0 and 1, and forbidding adjacent 1s makes the expansion unique, the same rule Zeckendorf's theorem imposes on Fibonacci sums. The question asks which integers have palindromic expansions. Because the radix point counts as a character, a palindrome must have it in the middle, so the digits pair up as $\varphi^k + \varphi^{-(k+1)}$. Every such pair is $\tfrac12(a + b\sqrt5)$ with Lucas and Fibonacci coefficients, so "the sum is an integer" becomes "the $\sqrt5$ parts cancel". That is an exact balance condition over non-adjacent subsets, and a branch-and-bound search can prune on it. It is also a pointed instance of the floating-point warning below: in an irrational base, integrality has to be decided in $\mathbb{Z}[\varphi]$, never by rounding a float.

How to reason about it

  • Decide which view you are in. String operations are clear and quick to write; if the space is small (problems 16, 36, 52), use them and stop. If it is not, translate the condition into the value view before writing a loop.
  • Read low digits as congruences, high digits as bounds. The last $k$ digits are $n \bmod b^k$ — they compose with multiplication and are where modular arithmetic prunes. The leading digits and the digit count fix an interval $[b^{k-1}, b^k)$, which is where length-preservation arguments ("$6x$ must not gain a digit") come from. Both readings generalise. A digit deep inside an expansion becomes low digits after a shift (problem 731). A prefix in one base is an interval that bounds the prefix in another (problem 571).
  • Ask what the property depends on. If it depends on running digit statistics, use a digit DP, and carry value sums alongside counts when you need totals (problem 776). If it depends only on the digit multiset, count with generating functions and forget positions (problem 520).
  • Group by digit length. Almost every closed form here is per length band: rotations, reversals, concatenation and leading-zero rules all depend on $k$, and fixing it first turns them into ordinary algebra. It also orders things: over a fixed alphabet, "ascending" means "by length, then lexicographic", which is what makes unranking (problem 698) a left-to-right walk.
  • Mind the leading zero. It is the commonest off-by-one in the family: a rotation or reversal that produces a leading zero is not a $k$-digit number (problems 145, 168), and inclusion–exclusion over digit strings must treat the first position separately (problem 162). Sometimes the rule is the whole problem. In problem 963, deleting a leading $2$ also drops the run of zeros behind it, so one move removes several digits. The game's infinitesimals come entirely from that one effect.
  • Do not trust floating point for digit counts. len(str(n)) or an integer-only loop is exact; int(math.log10(n)) + 1 is wrong near powers of ten for large $n$ — see exact arithmetic for equality.
  • Watch the width. Digit problems invite huge values ($10^{100}$, $2^{1000}$). Python hides that; a C port needs a modulus, a digit array, or a carry-arithmetic bignum — see watch integer width.

Problems32 / 53

  • ● 0016 — Power Digit Sum
  • ● 0017 — Number Letter Counts
  • ● 0036 — Double-base Palindromes
  • ● 0040 — Champernowne's Constant
  • ● 0052 — Permuted Multiples
  • ● 0145 — Reversible Numbers
  • ● 0156 — Counting Digits
  • ● 0162 — Hexadecimal Numbers
  • ● 0168 — Number Rotations
  • ● 0206 — Concealed Square
  • ● 0255 — Rounded Square Roots
  • ● 0269 — Polynomials with at Least One Integer Root
  • ○ 0284 — Steady Squares
  • ● 0288 — An Enormous Factorial
  • ● 0305 — Reflexive Position
  • ○ 0316 — Numbers in Decimal Expansions
  • ○ 0361 — Subsequence of Thue-Morse Sequence
  • ○ 0368 — A Kempner-like Series
  • ○ 0396 — Weak Goodstein Sequence
  • ○ 0414 — Kaprekar Constant
  • ○ 0419 — Look and Say Sequence
  • ● 0425 — Prime Connection
  • ○ 0442 — Eleven-free Integers
  • ● 0473 — Phigital Number Base
  • ○ 0508 — Integers in Base $i-1$
  • ● 0520 — Simbers
  • ○ 0524 — First Sort II
  • ● 0558 — Irrational Base
  • ● 0571 — Super Pandigital Numbers
  • ○ 0592 — Factorial Trailing Digits 2
  • ○ 0603 — Substring Sums of Prime Concatenations
  • ● 0637 — Flexible Digit Sum
  • ○ 0660 — Pandigital Triangles
  • ○ 0676 — Matching Digit Sums
  • ● 0698 — 123 Numbers
  • ○ 0714 — Duodigits
  • ● 0731 — A Stoneham Number
  • ● 0749 — Near Power Sums
  • ● 0776 — Digit Sum Division
  • ● 0778 — Freshman's Product
  • ○ 0805 — Shifted Multiples
  • ○ 0817 — Digits in Squares
  • ○ 0831 — Triple Product
  • ○ 0865 — Triplicate Numbers
  • ● 0885 — Sorted Digits
  • ○ 0893 — Matchsticks
  • ● 0926 — Total Roundness
  • ● 0932 — $2025$
  • ● 0963 — Removing Trits
  • ● 0990 — Addition Equations
  • ● 1003 — Lonely Singles
  • ○ 1004 — Balanced Integer
  • ● 1006 — Fibonacci Subwords