Mobius and primes with no two equal adjacent digits

Mobius and primes with no two equal adjacent digits

Fix a base b >= 3. The set R_b holds the integers n >= 1 whose base-b digits have no two equal neighbours. Write A(x) for the number of n <= x in R_b, M(x) for the sum of mu(n) over them and psi_R(x) for the sum of Lambda(n). The set is read by a (b+1)-state automaton whose state is the last digit, it keeps b - 1 digits in every state, as a one-missing-digit set does, and it is no digit design, so no theorem on a digit design at base b reaches it and neither does the Kummer theorem of kummer: the automaton has no digit allowed in every state, no kernel holding two digits and no reset word. At even b a digit design at base b^2 lies inside it and already carries primes from b = 61270, at a lower count (bullet The embedded design); what this page adds is the count A(x)/log x on R_b itself, the Mobius bound, and the bases 1153..61268 and every odd base b >= 1153. This page states the inputs that the dissection of mobius reads off any digit automaton, proves the theorem from them, and supplies them for R_b: blocks cut by the top digit, a units digit uniform up to a bounded error, a contraction over two steps, and a certificate from a run expansion of the transform below 1/5 from base 1153. Every number below is printed by lab/py/adjacent-digits.

The automaton

  • The automaton. Proved. Read the digits d_0, d_1, .. of n from the units end. The states are a start state * and the digits 0..b-1. From * every digit d is allowed and moves to state d; from state c the digit d is allowed exactly when d != c, and moves to state d. Then n lies in R_b exactly when its word of exact length, top digit nonzero, is accepted: the state is the digit just read, and the one refusal is a digit equal to it. In the language of beneath this is the width-2 rule of the memory dial at base b that forbids exactly the b windows (d, d).
  • The mass. Proved. Read from the top, an integer of exactly L digits in R_b has b - 1 choices of top digit and b - 1 choices at each lower position, so R_b holds exactly (b-1)^L integers of L digits and A(b^L - 1) = (b-1)((b-1)^L - 1)/(b-2); the accepted words of length L with leading zeros allowed number b (b-1)^(L-1). So A(x) grows like x^(alpha_b), alpha_b = log(b-1)/log b, the dimension of a one-missing-digit set. The count matrix on the digit states is J - I, J the all-ones matrix, with (J - I)^n = (((b-1)^n - (-1)^n)/b) J + (-1)^n I, by induction from J^2 = b J: the words of length k >= 1 with bottom digit c and top digit c' number ((b-1)^(k-1) - (-1)^(k-1))/b + (-1)^(k-1) [c = c']. Its Perron root is b - 1 with the uniform vector on both sides, its other eigenvalue -1, and it is primitive at b >= 3, since (J - I)^2 = (b - 2) J + I is positive.
  • Not a digit design. Proved. 1 and b lie in R_b and b + 1 does not. As words of length two they are (1, 0), (0, 1) and (1, 1), units digit first, and a digit design holding the first two holds the third. A prime missing one digit may repeat a digit, and a member of R_b may use every digit, so no theorem on a digit design at base b reaches R_b.
  • The embedded design. Proved. At even b = 2h let F = {a + b beta : h <= a < b, 0 <= beta < h}, a digit design at base b^2. Its members read, at base b, a top-half digit at every even position and a bottom-half digit at every odd one, so two neighbours never agree, the top digit is nonzero, and S_F lies in R_b. Its transform is abs(hat F(t)) = abs(D_h(t) D_h(b t)), so its level-i grid sums at base b^2 are the level-2i grid sums of H = {0..h-1} at base b; the half interval at even base on mobius, section The digit progressions, certifies them below 1/5 from b = 61270, F keeps the pair h, h + 1, and kappa_F = (b/phi(b))(phi(b)/2) h/h^2 = 1. So the prime count of coprime already gives infinitely many primes in R_b at every even b >= 61270, at the lower count x^(log(b/2)/log b + o(1)). The odd-base version, through the intervals I_fill and I_(fill-1), is not written here. Verified: at b = 4, 6, 8, 10 the three-digit strings of F at base b^2 all lie in R_b, F keeps h and h + 1, kappa_F = 1 exactly, and abs(hat F_i) = abs(hat H_(2i)) at i = 1, 2 and twenty random t to 3.4 * 10^-11 (verb count).
  • Leading zeros and synchronisation. Proved. No digit is allowed in every state, so a leading zero changes membership: the word of n with one zero placed above it is accepted, the top digit being nonzero, and with two zeros it is refused. So R_b below b^L is not the set of accepted words of length L, which is where the Kummer automaton, whose digit 0 is allowed in every state and returns to state 0, differs; the blocks below carry the top digit at every scale. The automaton has no reset word, since a word whose first digit is d is refused from state d. Completed with a refusing sink it is synchronizing: the word 00 sends every state to the sink. R_b lies among the words that never reach it, the sparse support that kummer reads for its own completed automaton.
  • The check. Verified. The automaton against direct membership below b^6 at b = 3, 4, 5, 10, 0 mismatches and 597870 members at b = 10; the counts (b-1)^L and b (b-1)^5 there; the witness 1, b, b + 1 at every b = 3..39; (J - I)^n in closed form at b = 3..8, n = 0..8 (verb count).

The theorem on a digit automaton

The Kummer theorem of kummer reads a carry automaton through four inputs and never through binomial coefficients. This section states those inputs for any digit automaton and proves the Mobius bound and the prime count from them; the sections after it supply each input for R_b.

  • The setting. A digit automaton at base b >= 3 is a finite set Q of states with a start state * and digit kernels D_(q q'), subsets of {0..b-1} disjoint in q' for each q, read from the units digit. Let M(u) be the Q x Q matrix with entries M_(q q')(u) = sum_(d in D_(q q')) e(d u), e(x) = exp(2 pi i x), and Pi_i(u) = M(u) M(b u) ... M(b^(i-1) u), so that e_q^T Pi_i(u) w is the transform of the words of length i read from state q, weighted at their end state by w. A state keeps the union of its kernels; a state is live when some nonempty word reaches it from *.
  • The hypotheses. Fix fill >= 2, constants N_0, E_0 >= 1, kappa > 0 and a finite list Omega of end vectors with entries in {0, 1}. A set S of positive integers satisfies them when:
    • (H1) * keeps at most b digits and every live state at most fill.
    • (H2) For every x >= b with L digits, S below x is the disjoint union of at most N_0 blocks P b^j + W at each scale 1 <= j < L and at most N_0 further points, where W lies in [0, b^j), holds at most fill^j integers and has transform e_*^T Pi_j(u) w for some w in Omega; and A_S(x) >= fill^(L-1)/N_0.
    • (H3) There are C_F >= 1 and alpha_1 < 1/5 with sum_(a < b^i) abs(e_q^T Pi_i(s + a/b^i) w) <= C_F fill^i b^(i alpha_1) at every i >= 0, every real s, every state q and every w in Omega or a unit vector e_(q').
    • (H4) There are m_0 >= 1 and c_E < 1 such that, whenever v lies at distance at least 3/(8b) from Z and v_2, .., v_(m_0) are real, in the entrywise modulus of M(v) M(v_2) ... M(v_(m_0)) every live row sums to at most c_E fill^(m_0) and the row of * to at most c_E b fill^(m_0 - 1).
    • (H5) Every block of (H2) at j >= 1 has abs((b/phi(b)) #{t in W : gcd(t, b) = 1} - kappa abs(W)) <= E_0.
  • The theorem. Proved. If S satisfies (H1) to (H5), there are C, c > 0 computable from b and the data with abs(M_S(x)) <= C A_S(x) exp(-c sqrt(log x)) and abs(psi_S(x) - kappa A_S(x)) <= C A_S(x) exp(-c sqrt(log x)) at every x >= 2, A_S, M_S and psi_S the count and the sums of mu and Lambda over S up to x. Proof. Run the unconditional dissection of mobius and its von Mangoldt form on coprime, section The dissection for the von Mangoldt function, with the replacements below; every step they do not name reads neither a digit set nor the set and runs verbatim. Throughout, norm(v^T B)_1 <= sum_q abs(v_q) r_q, r_q the sum of row q of the entrywise modulus of B; a vector e_*^T Pi_j(u) at j >= 1 is supported on live states, whose successors are live, so (H1) gives norm(e_*^T Pi_j(u))_1 <= b fill^(j-1) and every further factor costs at most fill.
    • The blocks. (H2) gives the split, and a block's sum is y^(-1) sum_(a mod y) hat W(a/y) S_P(-a/y), y = b^j, by orthogonality mod y, which reads only that W lies in [0, y). The scales below L - K weigh at most N_0 sum_(j < L-K) fill^j <= 2 N_0 fill^(L-K) <= 2 N_0^2 fill^(1-K) A_S(x), and the further points at most N_0 log x.
    • Region A. The unshifted grid sum of a block is (H3) at s = 0, q = * and w in Omega.
    • The hybrid bound. Split e_*^T Pi_k(t) w = e_*^T Pi_1(t) Pi_2(V_1 t) Pi_3(y t/V_2) w over the lowest i_1, the middle and the top i_2 positions, so abs(hat W(t)) <= f(t) fill^(k - i_1 - i_2) g(y t/V_2) with f(t) = norm(e_*^T Pi_1(t))_1, the sum over q of abs(e_*^T Pi_1(t) e_q), and g(v) the largest abs(e_q^T Pi_3(v) w) over live q. Residues distinct mod V_2 pay at most sum_q sum_(a < V_2) abs(e_q^T Pi_3(a/V_2) w) <= abs(Q) C_F fill^(i_2) V_2^(alpha_1), (H3) from every start state. The bottom factor enters through 4 D^2 norm(f)_1 + norm(f')_1: (H3) with unit end vectors, integrated over the shift, gives norm(f)_1 <= abs(Q) V_1^(-1) C_F fill^(i_1) V_1^(alpha_1); differentiating the product one factor at a time, the factor at position j costs b^j pi b (b - 1), since the digits of a row are distinct and sum to at most b(b-1)/2, the factors below it pay the integrated norm(e_*^T Pi_j)_1 <= abs(Q) b^(-j) C_F fill^j b^(j alpha_1) and those above fill each, so norm(f')_1 <= pi b^2 abs(Q) C_F fill^(i_1 - 1) i_1 V_1^(alpha_1). A class R(D, H) pays at most C fill^k (V_1 V_2)^(alpha_1) log y, the shape of the hybrid bound there with one more power of log x, which the saving Z^(-1/10) of region B absorbs; region B, which asks alpha_1 < 1/4, runs verbatim.
    • Region C1. For d = e m' with m' > 1 coprime to b and l nonzero mod m', every window of m_d consecutive positions holds a position where b^l l/d sits at distance at least 1/(2b) from Z, by the proof of Lemma A' on coprime. At a C1 point l/d + eta the hypothesis abs(eta) < y^(-2/3)/(4b(b-1)) of the perturbed Lemma A' moves that phase by less than 1/(4b(b-1)) <= 1/(8b) at l < 2k/3, leaving it at least 3/(8b) from Z. The good positions of every m_0-th window start at least floor(floor(2k/(3 m_d))/m_0) disjoint runs of m_0 positions inside [0, k) once k >= 3 m_0; (H4) contracts each run and (H1) pays fill elsewhere, so abs(hat W(l/d + eta)) <= b fill^(k-1) c_E^(floor(floor(2k/(3 m_d))/m_0)). That is the bound the C1 bullet of mobius reads, with c' replaced by c_E^(1/m_0) up to a constant, and the assembly takes C_0 with that replacement.
    • Region C2 reads only abs(hat W) <= abs(W) <= fill^k.
    • The main term. The principal characters of C2 give a block (b/phi(b)) #{t in W : gcd(t, b) = 1}, by the identity of coprime, which holds over any finite set of t, coprimality to b being read on t since b divides y. By (H5) that is kappa abs(W) within E_0, and over the blocks kappa A_S(x) within N_0 E_0 log_b x and kappa times the discarded scales. □
  • Kummer's theorem is the two-state case. At (3, 1) take Q = {0, 1} with * the state 0, fill = (p+1)/2, Omega = {e_0, e_1} and the blocks by state, at most 2 fill + 2 per scale. (H3) is its certificate, its top-factor bound covering both start states; (H4) holds with m_0 = 1, since its l^infinity input gives every row at most fill - 2 + 2 cos(3 pi/(8p)) at distance 3/(8p) from Z; (H5) holds with kappa = p/(p+1) and E_0 = 1 by its main-term bullet. The one-missing-digit sets and the half interval of mobius are the one-state case, Q = {*} with * live, m_0 = 1 and the consecutive pair.
  • What changes from the every-pair theorem of kummer. That theorem is stated for Kummer automata and reads three features they share: the digit 0 is allowed in every state and returns to state (0, 0), so leading zeros change nothing and the blocks are words of a fixed length; the pair {0, 1} sits inside one kernel of every state, a one-step contraction; and a units digit 0 resets every state to (0, 0), which counts the block elements divisible by p. R_b has none of the three. Its blocks carry the top digit as an end vector, the integers shorter than x being blocks with a one-digit prefix; its contraction takes two steps, m_0 = 2; its main term is read off the exact counts of (J - I)^n. The number of states enters only the constants, through abs(Q) and N_0.

The blocks and the units digit

  • The blocks. Proved. Write W_j^(f) for the words of length j with no two equal adjacent digits and top digit not f, read as integers in [0, b^j), with W_0^(f) = {0}; it holds b (b-1)^(j-1) - (b-1)^(j-1) = (b-1)^j integers at j >= 1, and its transform is e_*^T Pi_j(u) (1 - e_f), 1 the all-ones vector on the digit states. Let x have L digits x_j. An element n < x of R_b with fewer than L digits has some top digit f >= 1 at position j < L - 1, so it lies in f b^j + W_j^(f), and every element of that block lies in R_b. An element with L digits first falls below x at a position j where its digit f is below x_j, the digits above copying those of x; that prefix has no two equal neighbours, f != x_(j+1) when j < L - 1 and f >= 1 when j = L - 1, so the element lies in P b^j + W_j^(f) with P the prefix followed by f, and the block lies in R_b. So R_b below x is the disjoint union of at most b - 1 blocks of each kind at each scale j < L and the point x when x lies in R_b: (H2) holds with fill = b - 1, N_0 = 2b, the blocks at scale 0 being single points, at most 2b - 1 of them with x, Omega = {1 - e_f : f < b}, each block holding exactly (b-1)^j integers, and A(x) >= (b-1)^(L-1) from the integers of L - 1 digits.
  • The units digit, and kappa_b = 1. Proved. Let U be the units mod b, phi = phi(b). By the word count of the first section the elements of W_j^(f) whose units digit lies in U number sum_(c in U) sum_(c' != f) (((b-1)^(j-1) - (-1)^(j-1))/b + (-1)^(j-1) [c = c']) = phi (b-1)^j/b + (-1)^(j-1)(phi/b - [f in U]), so (b/phi) #{t in W_j^(f) : gcd(t, b) = 1} = (b-1)^j + (-1)^(j-1)(1 - (b/phi)[f in U]), the block's size within b/phi. That is (H5) with kappa = 1 and E_0 = b/phi(b), at every base. The units digit of a block element is uniform up to that error because the uniform vector is the left Perron vector of J - I: every digit is refused in exactly one state, and the stationary law weighs the states equally. The correlation between the units digit and the digit above it changes the law of pairs and not the law of the units digit. A one-missing-digit set, which refuses the same digit e_0 in every position, has kappa = (b/phi)(phi - [e_0 in U])/(b - 1) by the theorem of coprime, 10/9 at base 10 missing 5; R_b refuses each digit in one state and reads 1.
  • The check. Verified. The block split against direct membership at 420 values of x at b = 3, 4, 5, 7, 10, at most 2(b-1) blocks per scale, each of (b-1)^j integers; the units-digit identity exactly at all 450 cells b = 3..12, j = 1..6, every f (verb count).

The two-step contraction

  • No kernel holds two digits. Proved. Each digit of state c moves to its own state, so every entry of M(u) is a single exponential or 0 and the entrywise modulus of M(u) is J - I on the digit states, with the row of * all ones, at every u. No one-step bound beats fill = b - 1: the consecutive pair that Lemma A' contracts is present in every state at b >= 4, {0, 1} or {2, 3}, but its two digits lead to two states and never meet in one entry.
  • Two steps meet. Proved. In M(v) M(v') the entry from state c to state c'' sums over the middle digit: e(c'' v') sum_(c' != c, c' != c'') e(c' v), of modulus abs(S_b(v) - e(c v) - [c'' != c] e(c'' v)) with S_b(v) = sum_(d < b) e(d v). So a digit row of the entrywise modulus sums to at most (b - 1)(abs(S_b(v)) + 2) + abs(S_b(v)) + 1 <= b abs(S_b(v)) + 2b - 1, and the row of *, whose entry to c'' has modulus abs(S_b(v) - e(c'' v)), to at most b abs(S_b(v)) + b. At distance at least 3/(8b) from Z, abs(S_b(v)) = abs(sin(pi b v)/sin(pi v)) <= sigma_b = sin(3 pi/8)/sin(3 pi/(8b)): on the main lobe the Dirichlet kernel decreases, and beyond it abs(S_b(v)) <= csc(pi/b) < sigma_b. So (H4) holds with m_0 = 2 and c_E = (b sigma_b + 2b - 1)/(b - 1)^2, the row of * being at most (b sigma_b + b)/(b(b - 1)) <= c_E of b fill. At b >= 1153, sin w >= w (1 - w^2/6) gives b sigma_b <= 0.784214 b^2 (1 + 10^-6), so c_E <= (0.7842148 + 2/b)/(1 - 2/b) < 0.7874; its limit is (8/(3 pi)) sin(3 pi/8) = 0.784213. The contraction is stronger than the pair's 1 - (2/fill)(1 - cos(pi/(4b))), which tends to 1, because two steps cancel the whole digit sum S_b(v) and not one pair.
  • The check. Verified. At 1600 random pairs with the first frequency at distance at least 3/(8b) from Z, b = 5, 10, 31, 101, the two-step rows sit at most 0.948152 of b abs(S_b(v)) + 2b - 1; c_E < 1 and decreasing at every b = 19..5000, 1.000923 at 18 and 0.787312 at 1153; at b = 31, level 12, 332 reduced l/d over 11 moduli carrying a prime outside b, each plus a rational perturbation inside the hypothesis of Lemma A' and phases computed exactly, abs(hat W_k(l/d + eta)) sits at most 2.417 * 10^-9 of b (b-1)^(k-1) c_E^(floor(floor(2k/(3 m_d))/2)) (verb check).

The run expansion

  • The product. Proved. With D(u) the diagonal matrix of e(c u), c < b, the transform of the words of length i >= 1 with end weight w on the digit states is T_i(u; w) = 1^T D(u) (J - I) D(b u) (J - I) ... (J - I) D(b^(i-1) u) w, which is e_*^T Pi_i(u) w: the row of * is 1^T D(u) and a digit row of M(u) is the same row of (J - I) D(u). Since every entry is a single exponential, the triangle inequality across the states, which kummer pays once per digit in its transfer inequality, gives here only the trivial bound; the cancellation sits between the paths and is read by expanding J - I.
  • The run expansion. Proved. Put rep_r = (b^r - 1)/(b - 1). Then T_i(u; w) = sum_(r = 1..i-1) (-1)^(r-1) S_b(rep_r u) T_(i-r)(b^r u; w) + (-1)^(i-1) sum_c w_c e(c rep_i u). Proof. 1^T D(u) J = S_b(u) 1^T, so expanding the first J - I gives T_i(u; w) = S_b(u) T_(i-1)(b u; w) - 1^T D(u + b u) (J - I) D(b^2 u) ... w, and the second term has the same form with D(u) replaced by D(rep_2 u); induct on r. □ So T_i is a signed sum over the compositions of the i positions into runs, a run of length r starting at position j contributing S_b(rep_r b^j u) with sign (-1)^(r-1): the transform of the words in which that run repeats one digit, the sign correcting the overcount, an inclusion-exclusion over the forbidden equalities.
  • Full blocks merge. Proved. Consecutive runs of length 1 at positions j..j+l-1 multiply to prod S_b(b^m u) = S_(b^l)(b^j u), the transform of the full interval [0, b^l). Group each maximal stretch of runs of length 1 into one full block. Then T_i(u; 1) is a signed sum over the sequences of segments covering the i positions in which a segment is a full block of length l >= 1 or a long run of length r >= 2 and no two full blocks are adjacent, the segment at position j contributing S_(b^l)(b^j u) or (-1)^(r-1) S_b(rep_r b^j u). The merge is what keeps the cost of a full block linear in l log b, as in the digit-uniform chain of coprime, where runs of the full digit set merge in the same way.
  • The check. Verified. The run expansion and the matrix product meet the direct transform at nine random frequencies at every level up to 7, 6, 5, 4, 4 at b = 3, 4, 5, 7, 10, largest error 3.39 * 10^-10 (verb identity).

The certificate

  • The chain. Proved. Let phi_l be the supremum over real tau of sum_(q < b^l) abs(S_(b^l)((tau + q)/b^l)), the shifted grid sum of a full block, and rho_r that of sum_(q < b^r) abs(S_b((tau + q)/b^r)). Write Sigma_i(s) = sum_(a < b^i) abs(T_i(s + a/b^i; 1)). Put c_0 = g_0 = 1, g_i = sum_(r = 2..i) rho_r c_(i-r), h_i = sum_(l = 1..i) phi_l g_(i-l) and c_i = g_i + h_i. Then Sigma_i(s) <= c_i at every i and every real s. Proof. By the triangle inequality over the segment sequences of the run expansion it suffices to bound the grid sum of one product, and that by peeling its lowest segment, of length m. Write a = a' + b^(i-m) q with a' < b^(i-m) and q < b^m; then s + a/b^i = (t + q)/b^m with t = b^m s + a'/b^(i-m), the higher segments read b^m (s + a/b^i) = t mod 1, free of q, and the lowest reads S_(b^l)((t + q)/b^l) or S_b(rep_r (t + q)/b^r). Summed over q that is at most phi_l, or at most rho_r, since rep_r = 1 mod b is a unit mod b^r, so rep_r q runs over every residue mod b^r and S_b has period 1. Induct on the number of segments, a full block being followed by a long run or nothing. □ So if x = 1/z has P(x)(1 + Phi(x)) <= 1, with Phi(x) = sum_(l >= 1) phi_l x^l and P(x) = sum_(r >= 2) rho_r x^r, then g_i <= sum_r rho_r z^(i-r)(1 + sum_l phi_l z^(-l)) <= z^i by induction and Sigma_i(s) <= (1 + Phi(1/z)) z^i.
  • The full blocks. Proved. phi_l <= b^l U(b^l) with U(N) = (2 log(N/2 + 1) + h*)/pi + (1 - 2/pi)(1/2 + 1/N) and h* the maximum of h(tau) = sin(pi tau)(-psi(tau) - psi(1 - tau)) on [0, 1/2], psi the digamma function. Proof. F_N(tau) = sum_(q < N) abs(S_N((tau + q)/N)) = sin(pi tau) sum_q csc(pi (tau + q)/N) on (0, 1), with F_N(0) = N and F_N(1 - tau) = F_N(tau); take tau in (0, 1/2]. The points sit at distance delta from Z, the low ones delta = (q + tau)/N for 0 <= q <= Q_1 and the high ones delta = (q' + 1 - tau)/N for 0 <= q' <= Q_2, all at most 1/2, with Q_1 + Q_2 + 2 = N, Q_1 + 1 + tau <= N/2 + 1 and Q_2 + 2 - tau <= N/2 + 1. On (0, 1/2], csc(pi delta) <= 1/(pi delta) + 2(1 - 2/pi) delta, the chord of the convex csc w - 1/w. The low reciprocals sum to psi(Q_1 + 1 + tau) - psi(tau) <= log(N/2 + 1) - psi(tau) by psi(x) <= log x, the high ones to at most log(N/2 + 1) - psi(1 - tau), and the delta of two sequences of spacing 1/N below 1/2 sum to at most N/2 - (n_1(n_1 - 1) + n_2(n_2 - 1))/(2N) <= N/4 + 1/2 at n_1 + n_2 = N. So F_N(tau) <= (N/pi)(2 sin(pi tau) log(N/2 + 1) + h(tau)) + (1 - 2/pi)(N/2 + 1). □ On a cell [t_1, t_2], h(tau) = sin(pi tau)/tau + sin(pi tau)(1/(1 - tau) - psi(1 + tau) - psi(2 - tau)) is at most sin(pi t_1)/t_1 + sin(pi t_2)(1/(1 - t_2) - psi(1 + t_1) - psi(2 - t_2)), sin(pi tau)/tau decreasing and psi increasing, and on 20000 cells this puts h* <= 3.927267 against h(1/2) = 2 gamma + 4 log 2 = 3.927020 (verb wall). At N = 1000 the bound reads U = 5.3898 against the supremum 5.3601 on 201 shifts (verb check).
  • The long runs. Proved. rho_r <= b^r R_r with R_r = (2 Si(pi) + 2(4 - pi)/M)/pi + K_b (2/pi + (1 - 2/pi)/M^2), where M = b^(r-1), Si(pi) = 1.8519370520, K_b = E_b/pi + (1 - 2/pi)(1/2 + 1/b) and E_b = 2 log(b/2) + 2 gamma - 1 + 2/(b - 1) + 2/b. Proof. Write q = m + M j with m < M and j < b; then (tau + q)/b^r = (tau_m + j)/b with tau_m = (tau + m)/M in [0, 1), so the sum is sum_(m < M) F_b(tau_m), the one-digit sum of the bullet above sampled on a shifted grid of M points. At tau' in (0, 1) the point of each class nearest 0 gives 1/tau' and 1/(1 - tau'), and the others pair as 1/(k + tau') + 1/(k + 1 - tau') <= 1/k + 1/(k + 1), convex and symmetric in tau', at most floor(b/2) pairs, which sum to at most 2 H_(floor(b/2)) - 1 + 1/(floor(b/2) + 1) <= E_b. With the chord, F_b(tau') <= (b/pi) s(tau') + ((b/pi) E_b + (1 - 2/pi)(b/2 + 1)) sin(pi tau') with s(x) = sin(pi x)(1/x + 1/(1 - x)). The geometric sum gives sum_m sin(pi tau_m) = cos(pi (tau - 1/2)/M)/sin(pi/(2M)) <= 2M/pi + (1 - 2/pi)/M. The function s is continuous on [0, 1] with s(0) = s(1) = pi, increasing on [0, 1/2] since its log-derivative 1/(1 + x) - sum_(k >= 2) 2x/(k^2 - x^2) decreases to 0 at 1/2, and so of variation 2(4 - pi) over a period, whence sum_m s(tau_m) <= M int_0^1 s + 2(4 - pi) = 2 Si(pi) M + 2(4 - pi). Divide by b^r = b M. □ At b = 1000 the bound reads R_2 = 3.8462 against the supremum 3.7890 on 21 shifts (verb check).
  • The certificate. Proved. Summing the two bounds, Phi(y/b) <= Phi*(y) = (2/pi)(log b) y/(1 - y)^2 + c_0 y/(1 - y) + (1 + 2/pi)(y/b)/(1 - y/b) with c_0 = (h* - 2 log 2)/pi + (1 - 2/pi)/2, by log(N/2 + 1) <= log N - log 2 + 2/N, and P(y/b) <= P*(y) = y^2 ((2 Si(pi)/pi + 2 K_b/pi)/(1 - y) + (2(4 - pi)/pi)/(b - y) + (1 - 2/pi) K_b/(b^2 - y)). Put Q_b(y) = P*(y)(1 + Phi*(y)), increasing in y. If Q_b(y) <= 1, then with z = b/y and C_1 = 1 + Phi*(y), Sigma_i(s) <= C_1 z^i at every i and every real s. The other weights follow. The words ending in f satisfy T_i(u; e_f) = e(f b^(i-1) u) T_(i-1)(u; 1 - e_f), so abs(T_i(u; e_f)) <= 1 + sum_(k = 1..i-1) abs(T_k(u; 1)), and a level-k transform on the level-i grid sums to at most b^(i-k) shifted level-k sums, C_1 z^i y^(i-k); so their grid sums are at most C_e z^i with C_e = C_1 y/(1 - y) + 1, and those of the blocks W_j^(f) at most (C_1 + C_e) z^i. From a digit state c' the words are those with bottom digit not c', R_i(u) = T_i(u; w) - e(c' u) R_(i-1)(b u), so abs(R_i(u)) <= 1 + sum_(k < i) abs(T_(i-k)(b^k u; w)) and their grid sums are at most ((C_1 + C_e)/(1 - y) + 1) z^i; no word enters *. So (H3) holds with C_F = (C_1 + C_e)/(1 - y) + 1 and b^(alpha_1) = z/(b - 1) = b/((b - 1) y), and alpha_1 < 1/5 exactly when Q_b(b^(4/5)/(b - 1)) < 1.
  • The rate is below log b. Proved. At y = c (log b)^(-2/3) the leading terms are P*(y) = (4/pi^2) c^2 (log b)^(-1/3)(1 + o(1)) and Phi*(y) = (2/pi) c (log b)^(1/3)(1 + o(1)), so Q_b(y) tends to (8/pi^3) c^3, below 1 at every c < pi/2. So the certificate's rate is z/(b - 1) <= (2/pi + o(1))(log b)^(2/3), against (2/pi) log b for the half interval of mobius, about 1.18 log p for the Kummer set and sqrt((4/pi) log b) for the chain of one missing digit: below the half interval because full blocks merge, and above one missing digit because each long run pays a whole log b.
  • The check. Verified. On 201 shifts of [0, 1/2] the full-block sums at every N = b^l <= 200000 over b = 3..40, 64, 101, 257, 1000, 1009 stay at most 0.996523 of U(N), on 100 shifts the long-run sums at every b^r <= 400000 over b = 3..40, 64, 101, 257 at most 0.981280 of R_r, and the exact grid sums by FFT at b = 3, 4, 5, 7, 10, every level with b^i <= 10^6 and four shifts, at most 0.304639 of C_1 z^i, the blocks W_j^(f) at f = 0, b - 1 at most 0.132486 of (C_1 + C_e) z^i, with y the root of Q_b at the certified h* = 3.927267 (verb check).

The wall

  • The wall. Proved. alpha_1 < 1/5 at every base b >= 1153. The closed form Q_b(b^(4/5)/(b - 1)) is certified below 1 at 120 bits at every base 1153..2400, reading at most 0.9997265 at 1153, and is at least 1.0001617 at 1152. Beyond 2400 put e_1 = 2400/2399, so y = b^(4/5)/(b - 1) <= e_1 b^(-1/5) <= y_max = e_1 2400^(-1/5); with y_max in every denominator 1 - y and b >= 2400 in every term divided by b or b^2, Q_b(y) <= g(b) = e_1^2 b^(-2/5)(p_1 log b + p_0)(1 + e_1 b^(-1/5)(f_1 log b + f_0)) for constants p_1, p_0, f_1, f_0 > 0, and b^(-a)(p log b + p') decreases once log b > 1/a - p'/p, which puts g decreasing from log b = 3.772, with g(2400) <= 0.697083. At 1153, y = 0.24436871, C_1 <= 3.2416, C_e <= 2.0484 and 1/5 - alpha_1 >= 1.1311 * 10^-5. Against 1/4, which region B asks, the same closed form clears at every base b >= 185, certified at 185..600 with the tail from 600, g(600) <= 0.476207, failing at 184, and 1/4 - alpha_1 >= 4.5472 * 10^-5 at 185 (verb wall, 2 seconds).
  • The spread, and what sits near the cut. Verified, upper ends of the certificate printed by the generator.
balpha_1z/(b-1)
100.51553743.27746
1000.27527303.55260
10000.20299574.06431
11530.19998874.09573
10^40.16466044.55661
10^50.14006405.01557
10^60.12269045.44682
10^70.10965415.85570
10^80.09945156.24614
10^90.09121376.62100

The certificate reads alpha_1 < 0.22 at every base 489..1000 and 0.2200423 at 488, and alpha_1 < 0.18 at every base 3452..5000 and 0.1800013 at 3451, the two scans run on 300..1000 and 2500..5000 with no tail: on them the band abs(alpha_1 - 1/5) < 0.02 opens at 489 and closes at 3451, a factor of about 7 in the base, against almost two decades at the Kummer set, because the wall sits at a smaller base, where a decade moves the exponent by about 0.038, 0.2029957 at 1000 against 0.1646604 at 10^4. At b <= 7 the certificate sits above the exponent 1 - log(b - 1)/(2 log b) that Cauchy-Schwarz and Parseval give for free, 1.2998 against 0.6845 at b = 3, and at b = 10 it reads 0.5155 against 0.5229 (verb wall).

The theorem on R_b

  • The theorem. Proved. At every base b >= 1153 there are C, c > 0 computable from b alone with abs(M(x)) <= C A(x) exp(-c sqrt(log x)) and abs(psi_R(x) - A(x)) <= C A(x) exp(-c sqrt(log x)) at every x >= 2: the Mobius function cancels on the integers with no two equal adjacent base-b digits against their own count, and the sum of Lambda over them is their count, with constant kappa_b = 1. So at every such base there are infinitely many primes with no two equal adjacent digits, and up to x they number (A(x)/log x)(1 + O(1/log x)). Proof. The theorem on a digit automaton, with its hypotheses checked one by one. (H1): * keeps b digits and every digit state b - 1 = fill, by the first section. (H2): the blocks bullet, with N_0 = 2b and Omega = {1 - e_f}. (H3): the certificate, with C_F = (C_1 + C_e)/(1 - y) + 1 and alpha_1 < 1/5 from 1153 by the wall. (H4): the two-step contraction, m_0 = 2 and c_E < 0.7874. (H5): the units digit, kappa = 1 and E_0 = b/phi(b). For the count of primes, the prime powers up to x weigh O(x^(1/2) log x), below the error since A(x) >= (b-1)^(L-1) > (x/b)^(alpha_b) with alpha_b = log(b - 1)/log b > 1/2, so the sum of log p over the primes of R_b up to x is A(x)(1 + O(exp(-c sqrt(log x)))); partial summation against A(t) = O(t^(alpha_b)) gives the count. □
  • What the theorem reads off R_b. The certificate below 1/5 at s = 0 for region A, at every shift and from every state for the hybrid bound, alpha_1 < 1/4 for region B, the two-step contraction for C1, and the block counts (b-1)^j for C2, the mass floor and the units-digit counts for the main term. The rule between neighbouring digits enters through nothing else.
  • What stays open. Below 1153 the certificate does not reach 1/5, and at base 10 it reads 0.5155, so the primes of R_10 are not proved infinite here. The exact grid sums of the readings below sit well under the chain, which pays the triangle inequality between the segment sequences of the run expansion, so a certificate that reads the long runs together, or a transfer operator on the phase of the open run, moves the wall down; neither is written here. The theorem on a digit automaton carries any other rule between neighbouring digits, such as abs(d_(i+1) - d_i) >= 2, once its certificate and contraction are supplied; none is computed here. Conjecture. At every base b >= 3, psi_R(x) is asymptotic to A(x): the readings at b = 3, 4, 5, 7, 10 at x = 10^8 sit within 0.0066 of 1, the farthest 0.993479 at b = 3, while at 10^6 base 3 reads 1.0425 (verb primes).

Readings

  • The true rate. Verified, as readings that bound nothing. The exact unshifted grid sums by FFT give Sigma_L(0)/Sigma_(L-1)(0)/(b - 1) reading, at the last level reached, 2.0577 at b = 3 (level 13), 2.1360 at 4 (level 10), 2.2055 at 5 (level 8), 2.3108 at 7 (level 7) and 2.4144 at 10 (level 6), against the certificate's z/(b - 1) of 4.17033, 3.72150, 3.52190, 3.35411 and 3.27746: at base 10 the chain pays a factor 1.36 per digit. At every base the ratio drops at level 4, 3.0163, 2.8334, 2.4037, 2.3757, 2.4144 at levels 2..6 at base 10, five ratios and no settled value, and at b = 31 and 100 the FFT reaches only levels 4 and 3, 2.6765 and 3.8378; nothing is read there about the rate near the wall (verb rate).
  • The prime count. Verified, as readings far below the wall. With prime powers, psi_R(x)/A(x) reads 1.0015, 1.0004, 0.9995 at x = 10^6, 10^7, 10^8 at base 10, and 1.0000, 0.9991, 0.9991 at base 7, A counted exactly through the blocks, A(10^8) = 48427560 at base 10 and 26183346 at base 7; at b = 3, 4, 5 the readings at 10^8 are 0.993479, 0.9978, 1.0016. The constant 1 is read within 0.001 at bases 7 and 10, where the one-missing-digit constant reads 10/9 or 5/6 at base 10 and 7/6 or 35/36 at base 7: a falsification line for kappa_b, and no evidence for the theorem (verb primes).
  • The meter. Verified, a sanity print. Over R_10 below 10^8, M(10^8) = 4558 against A^(1/2) = 6959, abs(M)/A^(1/2) = 0.655, and the largest abs(M(n)) up to 10^8 reads 0.790 of A(10^8)^(1/2); the sieve meets pi(10^8) = 5761455 and the Mertens value M(10^8) = 1928 (verb primes, 8 seconds).

What is in print

  • The search. Queries for primes with no two equal adjacent digits, primes avoiding a digit block or pattern, digital blocks along primes, primes in sparse automatic sets, primes in sets cut by a subshift of finite type or a forbidden adjacent pair, and primes with restricted digits beyond missing digits, through the arXiv listings to the present, found no source on primes or Mobius sums on R_b, or on any set defined by forbidden adjacent digit pairs, at the scale A(x)/log x. What the search found is below, each read at source as stated.
  • The sequence. Verified. A050757 lists the primes with no pair of consecutive equal decimal digits, the primes of R_10; the entry, read whole, has no references and no comments.
  • Missing digits. Verified. Maynard 2022, Theorem 1.1, read at source: the asymptotic for Lambda over one missing digit at base q > 2 * 10^6 with a log-power error, which the text says holds uniformly when the excluded digit depends on the position; R_b excludes a digit that depends on the neighbouring digit, which that statement does not cover. The paper states as a consequence that infinitely many primes have no run of 15 equal consecutive decimal digits, through a set missing digits at base 10^8, a digit design at that base; among the theorems the search found, that bound on runs is the nearest to R_b that places primes. Maynard 2019, read in its abstract, Theorem 1.1 and introduction, gives the order of magnitude at base 10, and its survey Maynard 2019 survey, Theorem 2.3, at every base b >= 10; neither treats mu.
  • Digital functions along primes. Verified. Mauduit and Rivat 2015, read in its abstract and Sections 1 and 2, bound the sums of Lambda and of mu twisted by a digital function of modulus 1 with a carry property and a small Fourier transform, Rudin-Shapiro and its block products included: statements at positive density. Hanna 2017, read in arXiv v1, pp. 1 to 6, proves the prime number theorem for e(alpha a(n)) with a(n) block-additive, mu included by its Remark 1.4. Its Section 7, Example III, read at source, takes for a(n) the number of words of one repeated letter of a fixed length, so at length 2 the number of equal adjacent pairs, and puts it under that theorem at every base q >= 3, so the count is equidistributed mod m' along the primes: the nearest result in print, a statement at positive density. R_b is the level set a(n) = 0, of density 0, which an equidistribution statement for e(alpha a(n)) does not reach at the scale A(x)/log x.
  • Automatic sequences. Verified. Mullner 2017, Theorems 1.2 and 1.3 read at source: every automatic sequence is orthogonal to mu, o(N) with no rate, and the letter frequencies along the primes exist for a strongly connected automaton whose initial state is fixed by the digit 0; the completed automaton of R_b has a sink and R_b has density 0. Deshouillers, Drmota and Mullner 2015, read at the authors' text, prove the Sarnak conjecture for synchronizing automata, which covers R_b through the word 00, with frequency 0 along the primes. Adamczewski, Drmota and Mullner 2022, read in its abstract, prove that the logarithmic densities along the primes exist, 0 here.
  • Neighbour rules elsewhere. Verified. Drmota, Mullner and Spiegelhofer 2021, read in its introduction and Chapter 9, prove a local limit theorem for the Zeckendorf digit sum of primes and a power saving for mu twisted by it; the Zeckendorf digits obey a no-two-adjacent-ones rule, but every integer has a Zeckendorf representation, so the rule constrains the representation and not the set. Saavedra-Araya 2024, read in Section 1 and Section 5.3, studies the integers whose digits follow a 0/1 transition matrix T and proves joint equidistribution mod a when T is irreducible, regular and has digits d, d' with T(d, d) = T(d, d') = T(d', d) = 1; R_b is the case T = J - I, whose diagonal is 0, so that hypothesis fails, and primes are not treated. The prescribed-digit theorems of Bourgain 2013, read in its abstract, and the almost primes of Dartyge and Mauduit 2000, read in its abstract, are stated for digit designs.
  • What this page adds. On R_b itself at every base b >= 1153: the prime count A(x)/log x with constant 1, at the exponent log(b-1)/log b, and a Mobius bound against the set's own count, both with a saving of zero-free-region shape, constants computable from b and an explicit least base. Infinitely many primes in R_b follow from the tree's own prime count at every even b >= 61270, through the embedded design of the first section at the lower exponent log(b/2)/log b; the bases 1153..61268 and every odd base b >= 1153 are new here, and the asymptotic count and the Mobius bound are new at every base b >= 1153; for a digit automaton in general, the five hypotheses under which the dissection carries both, the Kummer set, the half interval and one missing digit being cases.

Generators

  • lab/py/adjacent-digits, one file, six verbs. count: the automaton against direct membership, the counts, the block split, the units-digit identity, the witness against a digit design, (J - I)^n. identity: the run expansion and the matrix product against the direct transform. wall: h*, the closed form Q_b at 120 bits, the walls at 1/5 and 1/4 with their tails, C_1 and C_e, the spread and the band near the cut. check: the full-block and long-run sums against U and R_r, the grid sums against the certificate, the two-step rows, c_E and the C1 bound. rate: the exact grid sums. primes: the prime count and the Mobius meter below 10^8.