
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, ..ofnfrom the units end. The states are a start state*and the digits0..b-1. From*every digitdis allowed and moves to stated; from statecthe digitdis allowed exactly whend != c, and moves to stated. Thennlies inR_bexactly 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 basebthat forbids exactly thebwindows(d, d). - The mass. Proved. Read from the top, an integer of exactly
Ldigits inR_bhasb - 1choices of top digit andb - 1choices at each lower position, soR_bholds exactly(b-1)^Lintegers ofLdigits andA(b^L - 1) = (b-1)((b-1)^L - 1)/(b-2); the accepted words of lengthLwith leading zeros allowed numberb (b-1)^(L-1). SoA(x)grows likex^(alpha_b),alpha_b = log(b-1)/log b, the dimension of a one-missing-digit set. The count matrix on the digit states isJ - I,Jthe all-ones matrix, with(J - I)^n = (((b-1)^n - (-1)^n)/b) J + (-1)^n I, by induction fromJ^2 = b J: the words of lengthk >= 1with bottom digitcand top digitc'number((b-1)^(k-1) - (-1)^(k-1))/b + (-1)^(k-1) [c = c']. Its Perron root isb - 1with the uniform vector on both sides, its other eigenvalue-1, and it is primitive atb >= 3, since(J - I)^2 = (b - 2) J + Iis positive. - Not a digit design. Proved.
1andblie inR_bandb + 1does 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 ofR_bmay use every digit, so no theorem on a digit design at basebreachesR_b. - The embedded design. Proved. At even
b = 2hletF = {a + b beta : h <= a < b, 0 <= beta < h}, a digit design at baseb^2. Its members read, at baseb, 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, andS_Flies inR_b. Its transform isabs(hat F(t)) = abs(D_h(t) D_h(b t)), so its level-igrid sums at baseb^2are the level-2igrid sums ofH = {0..h-1}at baseb; the half interval at even base on mobius, section The digit progressions, certifies them below1/5fromb = 61270,Fkeeps the pairh, h + 1, andkappa_F = (b/phi(b))(phi(b)/2) h/h^2 = 1. So the prime count of coprime already gives infinitely many primes inR_bat every evenb >= 61270, at the lower countx^(log(b/2)/log b + o(1)). The odd-base version, through the intervalsI_fillandI_(fill-1), is not written here. Verified: atb = 4, 6, 8, 10the three-digit strings ofFat baseb^2all lie inR_b,Fkeepshandh + 1,kappa_F = 1exactly, andabs(hat F_i) = abs(hat H_(2i))ati = 1, 2and twenty randomtto3.4 * 10^-11(verbcount). - Leading zeros and synchronisation. Proved. No digit is allowed in every state, so a leading zero changes membership: the word of
nwith one zero placed above it is accepted, the top digit being nonzero, and with two zeros it is refused. SoR_bbelowb^Lis not the set of accepted words of lengthL, which is where the Kummer automaton, whose digit0is allowed in every state and returns to state0, differs; the blocks below carry the top digit at every scale. The automaton has no reset word, since a word whose first digit isdis refused from stated. Completed with a refusing sink it is synchronizing: the word00sends every state to the sink.R_blies 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^6atb = 3, 4, 5, 10,0mismatches and597870members atb = 10; the counts(b-1)^Landb (b-1)^5there; the witness1, b, b + 1at everyb = 3..39;(J - I)^nin closed form atb = 3..8,n = 0..8(verbcount).
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 >= 3is a finite setQof states with a start state*and digit kernelsD_(q q'), subsets of{0..b-1}disjoint inq'for eachq, read from the units digit. LetM(u)be theQ x Qmatrix with entriesM_(q q')(u) = sum_(d in D_(q q')) e(d u),e(x) = exp(2 pi i x), andPi_i(u) = M(u) M(b u) ... M(b^(i-1) u), so thate_q^T Pi_i(u) wis the transform of the words of lengthiread from stateq, weighted at their end state byw. A state keeps the union of its kernels; a state is live when some nonempty word reaches it from*. - The hypotheses. Fix
fill >= 2, constantsN_0, E_0 >= 1,kappa > 0and a finite listOmegaof end vectors with entries in{0, 1}. A setSof positive integers satisfies them when:- (H1)
*keeps at mostbdigits and every live state at mostfill. - (H2) For every
x >= bwithLdigits,Sbelowxis the disjoint union of at mostN_0blocksP b^j + Wat each scale1 <= j < Land at mostN_0further points, whereWlies in[0, b^j), holds at mostfill^jintegers and has transforme_*^T Pi_j(u) wfor somewinOmega; andA_S(x) >= fill^(L-1)/N_0. - (H3) There are
C_F >= 1andalpha_1 < 1/5withsum_(a < b^i) abs(e_q^T Pi_i(s + a/b^i) w) <= C_F fill^i b^(i alpha_1)at everyi >= 0, every reals, every stateqand everywinOmegaor a unit vectore_(q'). - (H4) There are
m_0 >= 1andc_E < 1such that, whenevervlies at distance at least3/(8b)fromZandv_2, .., v_(m_0)are real, in the entrywise modulus ofM(v) M(v_2) ... M(v_(m_0))every live row sums to at mostc_E fill^(m_0)and the row of*to at mostc_E b fill^(m_0 - 1). - (H5) Every block of (H2) at
j >= 1hasabs((b/phi(b)) #{t in W : gcd(t, b) = 1} - kappa abs(W)) <= E_0.
- (H1)
- The theorem. Proved. If
Ssatisfies (H1) to (H5), there areC, c > 0computable fromband the data withabs(M_S(x)) <= C A_S(x) exp(-c sqrt(log x))andabs(psi_S(x) - kappa A_S(x)) <= C A_S(x) exp(-c sqrt(log x))at everyx >= 2,A_S,M_Sandpsi_Sthe count and the sums ofmuandLambdaoverSup tox. 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_qthe sum of rowqof the entrywise modulus ofB; a vectore_*^T Pi_j(u)atj >= 1is supported on live states, whose successors are live, so (H1) givesnorm(e_*^T Pi_j(u))_1 <= b fill^(j-1)and every further factor costs at mostfill.- 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 mody, which reads only thatWlies in[0, y). The scales belowL - Kweigh at mostN_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 mostN_0 log x. - Region A. The unshifted grid sum of a block is (H3) at
s = 0,q = *andwinOmega. - 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) wover the lowesti_1, the middle and the topi_2positions, soabs(hat W(t)) <= f(t) fill^(k - i_1 - i_2) g(y t/V_2)withf(t) = norm(e_*^T Pi_1(t))_1, the sum overqofabs(e_*^T Pi_1(t) e_q), andg(v)the largestabs(e_q^T Pi_3(v) w)over liveq. Residues distinct modV_2pay at mostsum_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 through4 D^2 norm(f)_1 + norm(f')_1: (H3) with unit end vectors, integrated over the shift, givesnorm(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 positionjcostsb^j pi b (b - 1), since the digits of a row are distinct and sum to at mostb(b-1)/2, the factors below it pay the integratednorm(e_*^T Pi_j)_1 <= abs(Q) b^(-j) C_F fill^j b^(j alpha_1)and those abovefilleach, sonorm(f')_1 <= pi b^2 abs(Q) C_F fill^(i_1 - 1) i_1 V_1^(alpha_1). A classR(D, H)pays at mostC fill^k (V_1 V_2)^(alpha_1) log y, the shape of the hybrid bound there with one more power oflog x, which the savingZ^(-1/10)of region B absorbs; region B, which asksalpha_1 < 1/4, runs verbatim. - Region C1. For
d = e m'withm' > 1coprime tobandlnonzero modm', every window ofm_dconsecutive positions holds a position whereb^l l/dsits at distance at least1/(2b)fromZ, by the proof of Lemma A' on coprime. At a C1 pointl/d + etathe hypothesisabs(eta) < y^(-2/3)/(4b(b-1))of the perturbed Lemma A' moves that phase by less than1/(4b(b-1)) <= 1/(8b)atl < 2k/3, leaving it at least3/(8b)fromZ. The good positions of everym_0-th window start at leastfloor(floor(2k/(3 m_d))/m_0)disjoint runs ofm_0positions inside[0, k)oncek >= 3 m_0; (H4) contracts each run and (H1) paysfillelsewhere, soabs(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, withc'replaced byc_E^(1/m_0)up to a constant, and the assembly takesC_0with 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 oft, coprimality tobbeing read ontsincebdividesy. By (H5) that iskappa abs(W)withinE_0, and over the blockskappa A_S(x)withinN_0 E_0 log_b xandkappatimes the discarded scales. □
- The blocks. (H2) gives the split, and a block's sum is
- Kummer's theorem is the two-state case. At
(3, 1)takeQ = {0, 1}with*the state0,fill = (p+1)/2,Omega = {e_0, e_1}and the blocks by state, at most2 fill + 2per scale. (H3) is its certificate, its top-factor bound covering both start states; (H4) holds withm_0 = 1, since itsl^infinityinput gives every row at mostfill - 2 + 2 cos(3 pi/(8p))at distance3/(8p)fromZ; (H5) holds withkappa = p/(p+1)andE_0 = 1by 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 = 1and 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
0is 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 digit0resets every state to(0, 0), which counts the block elements divisible byp.R_bhas none of the three. Its blocks carry the top digit as an end vector, the integers shorter thanxbeing 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, throughabs(Q)andN_0.
The blocks and the units digit
- The blocks. Proved. Write
W_j^(f)for the words of lengthjwith no two equal adjacent digits and top digit notf, read as integers in[0, b^j), withW_0^(f) = {0}; it holdsb (b-1)^(j-1) - (b-1)^(j-1) = (b-1)^jintegers atj >= 1, and its transform ise_*^T Pi_j(u) (1 - e_f),1the all-ones vector on the digit states. LetxhaveLdigitsx_j. An elementn < xofR_bwith fewer thanLdigits has some top digitf >= 1at positionj < L - 1, so it lies inf b^j + W_j^(f), and every element of that block lies inR_b. An element withLdigits first falls belowxat a positionjwhere its digitfis belowx_j, the digits above copying those ofx; that prefix has no two equal neighbours,f != x_(j+1)whenj < L - 1andf >= 1whenj = L - 1, so the element lies inP b^j + W_j^(f)withPthe prefix followed byf, and the block lies inR_b. SoR_bbelowxis the disjoint union of at mostb - 1blocks of each kind at each scalej < Land the pointxwhenxlies inR_b: (H2) holds withfill = b - 1,N_0 = 2b, the blocks at scale0being single points, at most2b - 1of them withx,Omega = {1 - e_f : f < b}, each block holding exactly(b-1)^jintegers, andA(x) >= (b-1)^(L-1)from the integers ofL - 1digits. - The units digit, and
kappa_b = 1. Proved. LetUbe the units modb,phi = phi(b). By the word count of the first section the elements ofW_j^(f)whose units digit lies inUnumbersum_(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 withinb/phi. That is (H5) withkappa = 1andE_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 ofJ - 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 digite_0in every position, haskappa = (b/phi)(phi - [e_0 in U])/(b - 1)by the theorem of coprime,10/9at base10missing5;R_brefuses each digit in one state and reads1. - The check. Verified. The block split against direct membership at
420values ofxatb = 3, 4, 5, 7, 10, at most2(b-1)blocks per scale, each of(b-1)^jintegers; the units-digit identity exactly at all450cellsb = 3..12,j = 1..6, everyf(verbcount).
The two-step contraction
- No kernel holds two digits. Proved. Each digit of state
cmoves to its own state, so every entry ofM(u)is a single exponential or0and the entrywise modulus ofM(u)isJ - Ion the digit states, with the row of*all ones, at everyu. No one-step bound beatsfill = b - 1: the consecutive pair that Lemma A' contracts is present in every state atb >= 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 statecto statec''sums over the middle digit:e(c'' v') sum_(c' != c, c' != c'') e(c' v), of modulusabs(S_b(v) - e(c v) - [c'' != c] e(c'' v))withS_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 toc''has modulusabs(S_b(v) - e(c'' v)), to at mostb abs(S_b(v)) + b. At distance at least3/(8b)fromZ,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 itabs(S_b(v)) <= csc(pi/b) < sigma_b. So (H4) holds withm_0 = 2andc_E = (b sigma_b + 2b - 1)/(b - 1)^2, the row of*being at most(b sigma_b + b)/(b(b - 1)) <= c_Eofb fill. Atb >= 1153,sin w >= w (1 - w^2/6)givesb sigma_b <= 0.784214 b^2 (1 + 10^-6), soc_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's1 - (2/fill)(1 - cos(pi/(4b))), which tends to1, because two steps cancel the whole digit sumS_b(v)and not one pair. - The check. Verified. At
1600random pairs with the first frequency at distance at least3/(8b)fromZ,b = 5, 10, 31, 101, the two-step rows sit at most0.948152ofb abs(S_b(v)) + 2b - 1;c_E < 1and decreasing at everyb = 19..5000,1.000923at18and0.787312at1153; atb = 31, level12,332reducedl/dover11moduli carrying a prime outsideb, each plus a rational perturbation inside the hypothesis of Lemma A' and phases computed exactly,abs(hat W_k(l/d + eta))sits at most2.417 * 10^-9ofb (b-1)^(k-1) c_E^(floor(floor(2k/(3 m_d))/2))(verbcheck).
The run expansion
- The product. Proved. With
D(u)the diagonal matrix ofe(c u),c < b, the transform of the words of lengthi >= 1with end weightwon the digit states isT_i(u; w) = 1^T D(u) (J - I) D(b u) (J - I) ... (J - I) D(b^(i-1) u) w, which ise_*^T Pi_i(u) w: the row of*is1^T D(u)and a digit row ofM(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 expandingJ - I. - The run expansion. Proved. Put
rep_r = (b^r - 1)/(b - 1). ThenT_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 firstJ - IgivesT_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 withD(u)replaced byD(rep_2 u); induct onr. □ SoT_iis a signed sum over the compositions of theipositions into runs, a run of lengthrstarting at positionjcontributingS_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
1at positionsj..j+l-1multiply toprod 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 length1into one full block. ThenT_i(u; 1)is a signed sum over the sequences of segments covering theipositions in which a segment is a full block of lengthl >= 1or a long run of lengthr >= 2and no two full blocks are adjacent, the segment at positionjcontributingS_(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 inl 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,4atb = 3, 4, 5, 7, 10, largest error3.39 * 10^-10(verbidentity).
The certificate
- The chain. Proved. Let
phi_lbe the supremum over realtauofsum_(q < b^l) abs(S_(b^l)((tau + q)/b^l)), the shifted grid sum of a full block, andrho_rthat ofsum_(q < b^r) abs(S_b((tau + q)/b^r)). WriteSigma_i(s) = sum_(a < b^i) abs(T_i(s + a/b^i; 1)). Putc_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)andc_i = g_i + h_i. ThenSigma_i(s) <= c_iat everyiand every reals. 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 lengthm. Writea = a' + b^(i-m) qwitha' < b^(i-m)andq < b^m; thens + a/b^i = (t + q)/b^mwitht = b^m s + a'/b^(i-m), the higher segments readb^m (s + a/b^i) = tmod1, free ofq, and the lowest readsS_(b^l)((t + q)/b^l)orS_b(rep_r (t + q)/b^r). Summed overqthat is at mostphi_l, or at mostrho_r, sincerep_r = 1modbis a unit modb^r, sorep_r qruns over every residue modb^randS_bhas period1. Induct on the number of segments, a full block being followed by a long run or nothing. □ So ifx = 1/zhasP(x)(1 + Phi(x)) <= 1, withPhi(x) = sum_(l >= 1) phi_l x^landP(x) = sum_(r >= 2) rho_r x^r, theng_i <= sum_r rho_r z^(i-r)(1 + sum_l phi_l z^(-l)) <= z^iby induction andSigma_i(s) <= (1 + Phi(1/z)) z^i. - The full blocks. Proved.
phi_l <= b^l U(b^l)withU(N) = (2 log(N/2 + 1) + h*)/pi + (1 - 2/pi)(1/2 + 1/N)andh*the maximum ofh(tau) = sin(pi tau)(-psi(tau) - psi(1 - tau))on[0, 1/2],psithe 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), withF_N(0) = NandF_N(1 - tau) = F_N(tau); taketauin(0, 1/2]. The points sit at distancedeltafromZ, the low onesdelta = (q + tau)/Nfor0 <= q <= Q_1and the high onesdelta = (q' + 1 - tau)/Nfor0 <= q' <= Q_2, all at most1/2, withQ_1 + Q_2 + 2 = N,Q_1 + 1 + tau <= N/2 + 1andQ_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 convexcsc w - 1/w. The low reciprocals sum topsi(Q_1 + 1 + tau) - psi(tau) <= log(N/2 + 1) - psi(tau)bypsi(x) <= log x, the high ones to at mostlog(N/2 + 1) - psi(1 - tau), and thedeltaof two sequences of spacing1/Nbelow1/2sum to at mostN/2 - (n_1(n_1 - 1) + n_2(n_2 - 1))/(2N) <= N/4 + 1/2atn_1 + n_2 = N. SoF_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 mostsin(pi t_1)/t_1 + sin(pi t_2)(1/(1 - t_2) - psi(1 + t_1) - psi(2 - t_2)),sin(pi tau)/taudecreasing andpsiincreasing, and on20000cells this putsh* <= 3.927267againsth(1/2) = 2 gamma + 4 log 2 = 3.927020(verbwall). AtN = 1000the bound readsU = 5.3898against the supremum5.3601on201shifts (verbcheck). - The long runs. Proved.
rho_r <= b^r R_rwithR_r = (2 Si(pi) + 2(4 - pi)/M)/pi + K_b (2/pi + (1 - 2/pi)/M^2), whereM = b^(r-1),Si(pi) = 1.8519370520,K_b = E_b/pi + (1 - 2/pi)(1/2 + 1/b)andE_b = 2 log(b/2) + 2 gamma - 1 + 2/(b - 1) + 2/b. Proof. Writeq = m + M jwithm < Mandj < b; then(tau + q)/b^r = (tau_m + j)/bwithtau_m = (tau + m)/Min[0, 1), so the sum issum_(m < M) F_b(tau_m), the one-digit sum of the bullet above sampled on a shifted grid ofMpoints. Attau'in(0, 1)the point of each class nearest0gives1/tau'and1/(1 - tau'), and the others pair as1/(k + tau') + 1/(k + 1 - tau') <= 1/k + 1/(k + 1), convex and symmetric intau', at mostfloor(b/2)pairs, which sum to at most2 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')withs(x) = sin(pi x)(1/x + 1/(1 - x)). The geometric sum givessum_m sin(pi tau_m) = cos(pi (tau - 1/2)/M)/sin(pi/(2M)) <= 2M/pi + (1 - 2/pi)/M. The functionsis continuous on[0, 1]withs(0) = s(1) = pi, increasing on[0, 1/2]since its log-derivative1/(1 + x) - sum_(k >= 2) 2x/(k^2 - x^2)decreases to0at1/2, and so of variation2(4 - pi)over a period, whencesum_m s(tau_m) <= M int_0^1 s + 2(4 - pi) = 2 Si(pi) M + 2(4 - pi). Divide byb^r = b M. □ Atb = 1000the bound readsR_2 = 3.8462against the supremum3.7890on21shifts (verbcheck). - 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)withc_0 = (h* - 2 log 2)/pi + (1 - 2/pi)/2, bylog(N/2 + 1) <= log N - log 2 + 2/N, andP(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)). PutQ_b(y) = P*(y)(1 + Phi*(y)), increasing iny. IfQ_b(y) <= 1, then withz = b/yandC_1 = 1 + Phi*(y),Sigma_i(s) <= C_1 z^iat everyiand every reals. The other weights follow. The words ending infsatisfyT_i(u; e_f) = e(f b^(i-1) u) T_(i-1)(u; 1 - e_f), soabs(T_i(u; e_f)) <= 1 + sum_(k = 1..i-1) abs(T_k(u; 1)), and a level-ktransform on the level-igrid sums to at mostb^(i-k)shifted level-ksums,C_1 z^i y^(i-k); so their grid sums are at mostC_e z^iwithC_e = C_1 y/(1 - y) + 1, and those of the blocksW_j^(f)at most(C_1 + C_e) z^i. From a digit statec'the words are those with bottom digit notc',R_i(u) = T_i(u; w) - e(c' u) R_(i-1)(b u), soabs(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 withC_F = (C_1 + C_e)/(1 - y) + 1andb^(alpha_1) = z/(b - 1) = b/((b - 1) y), andalpha_1 < 1/5exactly whenQ_b(b^(4/5)/(b - 1)) < 1. - The rate is below
log b. Proved. Aty = c (log b)^(-2/3)the leading terms areP*(y) = (4/pi^2) c^2 (log b)^(-1/3)(1 + o(1))andPhi*(y) = (2/pi) c (log b)^(1/3)(1 + o(1)), soQ_b(y)tends to(8/pi^3) c^3, below1at everyc < pi/2. So the certificate's rate isz/(b - 1) <= (2/pi + o(1))(log b)^(2/3), against(2/pi) log bfor the half interval of mobius, about1.18 log pfor the Kummer set andsqrt((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 wholelog b. - The check. Verified. On
201shifts of[0, 1/2]the full-block sums at everyN = b^l <= 200000overb = 3..40, 64, 101, 257, 1000, 1009stay at most0.996523ofU(N), on100shifts the long-run sums at everyb^r <= 400000overb = 3..40, 64, 101, 257at most0.981280ofR_r, and the exact grid sums by FFT atb = 3, 4, 5, 7, 10, every level withb^i <= 10^6and four shifts, at most0.304639ofC_1 z^i, the blocksW_j^(f)atf = 0, b - 1at most0.132486of(C_1 + C_e) z^i, withythe root ofQ_bat the certifiedh* = 3.927267(verbcheck).
The wall
- The wall. Proved.
alpha_1 < 1/5at every baseb >= 1153. The closed formQ_b(b^(4/5)/(b - 1))is certified below1at 120 bits at every base1153..2400, reading at most0.9997265at1153, and is at least1.0001617at1152. Beyond2400pute_1 = 2400/2399, soy = b^(4/5)/(b - 1) <= e_1 b^(-1/5) <= y_max = e_1 2400^(-1/5); withy_maxin every denominator1 - yandb >= 2400in every term divided byborb^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 constantsp_1, p_0, f_1, f_0 > 0, andb^(-a)(p log b + p')decreases oncelog b > 1/a - p'/p, which putsgdecreasing fromlog b = 3.772, withg(2400) <= 0.697083. At1153,y = 0.24436871,C_1 <= 3.2416,C_e <= 2.0484and1/5 - alpha_1 >= 1.1311 * 10^-5. Against1/4, which region B asks, the same closed form clears at every baseb >= 185, certified at185..600with the tail from600,g(600) <= 0.476207, failing at184, and1/4 - alpha_1 >= 4.5472 * 10^-5at185(verbwall, 2 seconds). - The spread, and what sits near the cut. Verified, upper ends of the certificate printed by the generator.
b | alpha_1 | z/(b-1) |
|---|---|---|
10 | 0.5155374 | 3.27746 |
100 | 0.2752730 | 3.55260 |
1000 | 0.2029957 | 4.06431 |
1153 | 0.1999887 | 4.09573 |
10^4 | 0.1646604 | 4.55661 |
10^5 | 0.1400640 | 5.01557 |
10^6 | 0.1226904 | 5.44682 |
10^7 | 0.1096541 | 5.85570 |
10^8 | 0.0994515 | 6.24614 |
10^9 | 0.0912137 | 6.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 >= 1153there areC, c > 0computable frombalone withabs(M(x)) <= C A(x) exp(-c sqrt(log x))andabs(psi_R(x) - A(x)) <= C A(x) exp(-c sqrt(log x))at everyx >= 2: the Mobius function cancels on the integers with no two equal adjacent base-bdigits against their own count, and the sum ofLambdaover them is their count, with constantkappa_b = 1. So at every such base there are infinitely many primes with no two equal adjacent digits, and up toxthey 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):*keepsbdigits and every digit stateb - 1 = fill, by the first section. (H2): the blocks bullet, withN_0 = 2bandOmega = {1 - e_f}. (H3): the certificate, withC_F = (C_1 + C_e)/(1 - y) + 1andalpha_1 < 1/5from1153by the wall. (H4): the two-step contraction,m_0 = 2andc_E < 0.7874. (H5): the units digit,kappa = 1andE_0 = b/phi(b). For the count of primes, the prime powers up toxweighO(x^(1/2) log x), below the error sinceA(x) >= (b-1)^(L-1) > (x/b)^(alpha_b)withalpha_b = log(b - 1)/log b > 1/2, so the sum oflog pover the primes ofR_bup toxisA(x)(1 + O(exp(-c sqrt(log x)))); partial summation againstA(t) = O(t^(alpha_b))gives the count. □ - What the theorem reads off
R_b. The certificate below1/5ats = 0for region A, at every shift and from every state for the hybrid bound,alpha_1 < 1/4for region B, the two-step contraction for C1, and the block counts(b-1)^jfor 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
1153the certificate does not reach1/5, and at base10it reads0.5155, so the primes ofR_10are 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 asabs(d_(i+1) - d_i) >= 2, once its certificate and contraction are supplied; none is computed here. Conjecture. At every baseb >= 3,psi_R(x)is asymptotic toA(x): the readings atb = 3, 4, 5, 7, 10atx = 10^8sit within0.0066of1, the farthest0.993479atb = 3, while at10^6base3reads1.0425(verbprimes).
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.0577atb = 3(level13),2.1360at4(level10),2.2055at5(level8),2.3108at7(level7) and2.4144at10(level6), against the certificate'sz/(b - 1)of4.17033,3.72150,3.52190,3.35411and3.27746: at base10the chain pays a factor1.36per digit. At every base the ratio drops at level4,3.0163, 2.8334, 2.4037, 2.3757, 2.4144at levels2..6at base10, five ratios and no settled value, and atb = 31and100the FFT reaches only levels4and3,2.6765and3.8378; nothing is read there about the rate near the wall (verbrate). - The prime count. Verified, as readings far below the wall. With prime powers,
psi_R(x)/A(x)reads1.0015,1.0004,0.9995atx = 10^6, 10^7, 10^8at base10, and1.0000,0.9991,0.9991at base7,Acounted exactly through the blocks,A(10^8) = 48427560at base10and26183346at base7; atb = 3, 4, 5the readings at10^8are0.993479,0.9978,1.0016. The constant1is read within0.001at bases7and10, where the one-missing-digit constant reads10/9or5/6at base10and7/6or35/36at base7: a falsification line forkappa_b, and no evidence for the theorem (verbprimes). - The meter. Verified, a sanity print. Over
R_10below10^8,M(10^8) = 4558againstA^(1/2) = 6959,abs(M)/A^(1/2) = 0.655, and the largestabs(M(n))up to10^8reads0.790ofA(10^8)^(1/2); the sieve meetspi(10^8) = 5761455and the Mertens valueM(10^8) = 1928(verbprimes, 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 scaleA(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
Lambdaover one missing digit at baseq > 2 * 10^6with a log-power error, which the text says holds uniformly when the excluded digit depends on the position;R_bexcludes 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 of15equal consecutive decimal digits, through a set missing digits at base10^8, a digit design at that base; among the theorems the search found, that bound on runs is the nearest toR_bthat places primes. Maynard 2019, read in its abstract, Theorem 1.1 and introduction, gives the order of magnitude at base10, and its survey Maynard 2019 survey, Theorem 2.3, at every baseb >= 10; neither treatsmu. - Digital functions along primes. Verified. Mauduit and Rivat 2015, read in its abstract and Sections 1 and 2, bound the sums of
Lambdaand ofmutwisted by a digital function of modulus1with 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 fore(alpha a(n))witha(n)block-additive,muincluded by its Remark 1.4. Its Section 7, Example III, read at source, takes fora(n)the number of words of one repeated letter of a fixed length, so at length2the number of equal adjacent pairs, and puts it under that theorem at every baseq >= 3, so the count is equidistributed modm'along the primes: the nearest result in print, a statement at positive density.R_bis the level seta(n) = 0, of density0, which an equidistribution statement fore(alpha a(n))does not reach at the scaleA(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 digit0; the completed automaton ofR_bhas a sink andR_bhas density0. Deshouillers, Drmota and Mullner 2015, read at the authors' text, prove the Sarnak conjecture for synchronizing automata, which coversR_bthrough the word00, with frequency0along the primes. Adamczewski, Drmota and Mullner 2022, read in its abstract, prove that the logarithmic densities along the primes exist,0here. - 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
mutwisted 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 a0/1transition matrixTand proves joint equidistribution modawhenTis irreducible, regular and has digitsd, d'withT(d, d) = T(d, d') = T(d', d) = 1;R_bis the caseT = J - I, whose diagonal is0, 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_bitself at every baseb >= 1153: the prime countA(x)/log xwith constant1, at the exponentlog(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 fromband an explicit least base. Infinitely many primes inR_bfollow from the tree's own prime count at every evenb >= 61270, through the embedded design of the first section at the lower exponentlog(b/2)/log b; the bases1153..61268and every odd baseb >= 1153are new here, and the asymptotic count and the Mobius bound are new at every baseb >= 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 formQ_bat 120 bits, the walls at1/5and1/4with their tails,C_1andC_e, the spread and the band near the cut.check: the full-block and long-run sums againstUandR_r, the grid sums against the certificate, the two-step rows,c_Eand the C1 bound.rate: the exact grid sums.primes: the prime count and the Mobius meter below10^8.