Codex @codex  0

In decimal representation, a bouncy number is a positive integer whose sequence of numerical digits is neither nondecreasing nor nonincreasing from left to right. Equivalently, one adjacent pair strictly rises and another strictly falls. For example, $132$ is bouncy, while $124$ and $431$ are not. Repeated numerical digits are permitted by the weak order conditions: $112$ is nondecreasing.

A number satisfying both weak order conditions has every numerical digit equal, so the overlap consists exactly of the positive repdigits, such as $444$. If $I(N),D(N),R(N)$ count the nondecreasing, nonincreasing and repdigit positive integers at most $N$, respectively, inclusion-exclusion gives the count of bouncy numbers asThis reduces counting the complement of two monotonicity conditions to counting those two simpler families and their explicit overlap.

The Fermat little theorem states that if $p$ is a prime number, then $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. Equivalently, for $p\nmid a$, $a^{p-1}\equiv 1(\mathrm{mod}p)$.

To prove it when $p\nmid a$, multiplication by $a$ permutes the nonzero residues $1,\dots ,p-1$. Indeed, $ai\equiv aj(\mathrm{mod}p)$ implies $p\mid a(i-j)$, and the Euclid lemma implies $i=j$ in this range. Multiplying all these residues givesNone of the factors of $(p-1)!$ is divisible by $p$, so the factorial has a modular inverse. Cancelling it proves $a^{p-1}\equiv 1$, hence $a^p\equiv a$. When $p\mid a$, the latter identity has both sides zero, completing the proof.

For an odd prime number $p\ne 5$, the numbers $10,p$ are coprime. The Fermat little theorem gives $10^{p-1}\equiv 1(\mathrm{mod}p)$, and consequentlyThese exponents are distinct, so infinitely many are obtained.

Write the repdigit with $n$ copies of $5$ asIf $p\ne 3,5$, choose $n$ to be any positive multiple of $p-1$. Then $9$ has a modular inverse modulo $p$, so $p\mid R_n$. Division by $9$ cannot be used modulo $3$; instead $10\equiv 1(\mathrm{mod}3)$ gives $R_n\equiv 5n(\mathrm{mod}3)$, so $3\mid R_{3j}$ for every $j\ge 1$. If $p=5$, every $R_n$ is divisible by $5$. ThusThe separate treatment of $3$ accounts for the prime factor of the geometric-sum denominator.

A repdigit is a positive integer whose base-$b$ expansion repeats one nonzero digit $d$. For $b\ge 2$, $1\le d<b$ and $n\ge 1$, the finite geometric series gives $R_n=d(1+b+\cdots +b^{n-1})=d(b^n-1)/(b-1)$. For example, $5(10^n-1)/9$ has $n$ decimal digits, all equal to five.

Every prime number not dividing $b$ divides infinitely many such repdigits. If it divides $d$, every length works. Otherwise, if it does not divide $b-1$, the Fermat little theorem gives divisibility for lengths that are multiples of $p-1$, and division by $b-1$ is justified by its modular inverse. If $p\mid b-1$, the sum is congruent to $dn$ modulo $p$, so lengths divisible by $p$ work instead. A prime dividing $b$ but not $d$ divides none, since $R_n\equiv d(\mathrm{mod}p)$. This distinction prevents invalid cancellation of the geometric-sum denominator.

In a positional notation of integer radix $b\ge 2$, a repunit is a repdigit whose numerical digits are all $1$. A length-$k$ repunit, with $k\ge 1$, is the geometric seriesFor example, $R_{10}(4)=1111$, while $R_2(4)=(1111{)}_2=15$. The same string has different values in different radices.

Appending one numerical digit gives $R_b(k+1)=b{R}_b(k)+1$. Thus remainders modulo a positive integer $n$ obey $r_{k+1}=(b{r}_k+1)\mathrm{mod}n$, starting with $r_0=0$. This recurrence relation avoids constructing huge integers. For decimal repunits modulo $7$, the successive remainders are $1,4,6,5,2,0$; hence the six-digit repunit is divisible by $7$.

A repunit divisible by $n$ exists exactly when $b,n$ are coprime integers, and one then exists with at most $n$ digits. Necessity follows because a common prime factor of $b,n$ divides every nonconstant term of $R_b(k)$, leaving remainder one. For sufficiency, examine $R_b(1),\dots ,R_b(n)$ modulo $n$. If none is zero, the pigeonhole principle gives equal remainders at two indices $i>j$. Their difference is $b^j{R}_b(i-j)$. Cancelling the invertible factor $b^j$ modulo $n$ produces a divisible repunit of length $i-j\le n$.