{'fraction_non_alphanumeric': 0.04844846034954227, 'fraction_numerical': 0.0241945071929616, 'mean_word_length': 3.6872387851769295, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 3, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computational Aspects of Sturdy and Flimsy Numbers

Following Stolarsky, we say that a natural number n is flimsy in base b if some positive multiple of n has smaller digit sum in base b than n does; otherwise it is sturdy. We develop algorithmic methods for the study of sturdy and flimsy numbers. We provide some criteria for determining whether a number is sturdy. Focusing on the case of base b = 2, we study the computational problem of checking whether a given number is sturdy, giving several algorithms for the problem. We find two additional, previously unknown sturdy primes. We develop a method for determining which numbers with a fixed number of 0's in binary are flimsy. Finally, we develop a method that allows us to estimate the number of k-flimsy numbers with n bits, and we provide explicit results for k = 3 and k = 5. Our results demonstrate the utility (and fun) of creating algorithms for number theory problems, based on methods of automata theory.


Introduction
Let s b (n) denote the sum of the digits of n, when expressed in base b. Thus, for example, s 2 (9) = 2. A number n is said to be k-flimsy in base b if there exists a positive integer k such 4. Given that n is flimsy, determine mfw b (n) := min{k : s b (kn) < s b (n)}. This is the minimal flimsy witness.
A table of these functions is given in Appendix C. In Sections 4-7, we discuss algorithms to solve these problems. The fastest, based on automata theory, shows that we can check whether a number n is sturdy in O(n) time. Section 10 gives our computational results achieved with our algorithms. In Section 11 we give an application of automata to help characterize the flimsy numbers with a fixed number of 0's.
Finally, in Section 12, we turn to estimating the number of k-flimsy numbers with n bits. We use techniques from formal language theory to solve the problem.

Basic properties
In this section, we prove some of the basic properties of digit sums of multiples. We start with some notation. For n ≥ 0, we define (n) b to be the base-b representation of n, starting with the most significant digit. If x is a string, we define [x] b to be the integer that x represents when interpreted in base b. If b is fixed, we define x to be the base-b complement of x, that is, the string where each digit d in x is replaced by b − 1 − d. Proof. For one direction, take k = j and t = 1.
For the other direction, assume that there exists j ≥ 1 such that s b (jn) = r. Let k = bj/t. Then s b (ktn) = s b (bjn) = s b (jn) = r.
We now show that in order to compute swm b , it suffices to consider only those arguments relatively prime to b.
Corollary 2. Write the prime factorization of n as 1≤i≤t p e i i , and define g = p i |b p e i i . Then swm b (n) = swm(n/g), and gcd(b, n/g) = 1.
Proof. Let p be any prime dividing both b and n. From Theorem 1, we see that swm b (n) = swm b (n/p). By repeatedly applying this observation, and replacing n with n/p, we can remove from n all primes dividing both b and n, while maintaining the same value of swm b . At the end, the resulting n/g is relatively prime to b. Theorem 3. There exists j ≥ 1 such that s b (jn) = t if and only if there exist t distinct powers of b that sum to a multiple of n.
Proof. By Corollary 2, we may assume that n is coprime with b.
In such cases, b has finite order, say ν, modulo n. Suppose ν−1 i=0 c i b i ≡ 0 (mod n) where each c i ≥ 0 and ν−1 i=0 c i = t. Then ν−1 i=0 c i −1 j=0 b jν+i ≡ 0 (mod n), and this sum consists of distinct powers of b.
Empirical evidence suggests that if b = 2 and swm b (n) = t, then for all i ≥ 0, some multiple of n has digit sum t + i. However, the analogous result is false for b = 3. For example, swm 3 (13) = 3, but no multiple of 13 has digit sum 4. These observations are explained in the following theorem. Proof. Assume s b (jn) = t for some t ≥ 1. Then from Theorem 3 we know that t i=1 b m i ≡ 0 (mod n) for some strictly increasing m i and (replacing j by bj if needed) we can assume m t ≥ 1. Now replace the high-order bit b mt in this sum with the sum of b terms b ν+mt−1 + b 2ν+mt−1 +· · ·+b (b−1)ν+mt−1 , where ν is the order of b, modulo n. This has the effect removing 1 bit, while adding b additional bits, and each of the b new terms is congruent to b mt−1 (mod n). So we have found another multiple of n with digit sum t + b − 1. We can repeat this transformation any number of times.

Infinite classes of sturdy numbers
We first give a criterion for deciding whether a number is flimsy. This shows that Problem 1 on our list, determining whether a given positive integer is sturdy, is decidable.
For the other direction, suppose n is flimsy, but s b (kn) ≥ s b (n) for all k with 1 ≤ k ≤ b j −1 n . Let k be the smallest positive integer such that s b (k n) < s b (n). By assumption k n ≥ b j , and so we can write k n = cb j + d for uniquely-determined c ≥ 1 and 0 Remark 6. Since j ≤ ϕ(n), this together with Theorem 1 shows that sturdiness is reduced to a finite search. The result for b = 10 was observed by Phedotov [20].
We applied Theorem 5 to known prime factors of composite Mersenne numbers [29] and found 57912614113275649087721 = 2 83 − 1 167 and 10350794431055162386718619237468234569 = 2 131 − 1 263 as previously unknown sturdy primes in base 2. Proof. Let k be an integer with 1 ≤ k ≤ m. Then we have where we have used the fact that k ≤ m. The result now follows by Theorem 5.
We can also get a generalization of a theorem of Stolarsky [28, Thm. 2.1].
Corollary 8. Let b ≥ 2, and let r, e be integers. Define n = b re −1 b e −1 . Then n is sturdy in base b.
Proof. Observe that (n) b = (1 0 e−1 ) r−1 1, and so s b (n) = r. On the other hand, if 1 ≤ k ≤ b e−1 , then (kn) b consists of r copies of (k) b , concatenated, separated by some number of 0's. So s b (kn) = rs b (k) ≥ r. The result now follows by Theorem 5.
The next theorem gives an infinite class of sturdy numbers.
Theorem 9. Fix b ≥ 2. Let n be a positive integer, and x be the base-b representation of n. Then every integer with base-b representation of the form . By Corollary 7 it follows that By Corollary 7 it follows that b |x|+i − 1 is sturdy in base b, and hence y is.
Corollary 10. Let b ≥ 2 be an integer, and m be an integer such that m 2 divides b − 1.
Then by Theorem 9, the number is sturdy.
In the rest of this paper we are almost exclusively concerned with the case b = 2, and so from now on we omit the subscripts on the functions msw, swm, mfw, and use the terms flimsy or sturdy without further elaboration. In this case s 2 (n) equals the number of 1's in the binary representation of n, also known as the Hamming weight of n.
Theorem 11. Let r, e be positive integers. Every integer with base-2 representation (1 e 0 e ) r 1 e is sturdy in base 2.

Algorithms when swm(n) is small
As we will see in Section 5, for general n we can determine whether n is sturdy in O(n) time. We call this a linear-time algorithm. 1 Therefore, it is of interest to see when this can be improved. If swm(n) is small, this fact can be verified efficiently in some cases. This is particularly relevant in the case where n is prime because, according to a recent result of Elsholtz [11], almost all primes p have swm(p) ≤ 7. Furthermore, we know from results of Hasse [14] and Odoni [18] that a positive proportion of all primes satisfy swm(p) = 2; asymptotically, this fraction is 17/24. For general n, however, the situation is different: the set of n for which swm(n) = 2 has density 0; see the results of Moree in [21, Appendix B].

The case swm(n) = 2
If swm(n) = 2, then n · msw(n) = 2 k + 1 for some integer k ≥ 1. Hence n | 2 k + 1, and so −1 belongs to the subgroup generated by 2 (mod n). We can decide if −1 belongs to the subgroup generated by 2 (mod n) by using an algorithm for the discrete logarithm problem. For example, the baby-step giant-step algorithm can be used to find k such that 2 k ≡ −1 (mod n), if such a k exists, with time complexity O( √ n log n) [26]. If the factorization of n is known, this running time can be substantially improved.

The case swm(n) = 3
If swm(n) = 3, then n · msw(n) = 2 k + 2 + 1 for some integers k > l ≥ 1. It follows that 2 k + 2 l ≡ −1 (mod n), which means that we are dealing with a 2-SUM problem. This can be solved in O(n log n) time using sorting and binary search. (Briefly, compute a table of powers of 2, mod n; sort them in ascending order, and then for each power 2 k use binary search to see if there is an such that 2 l ≡ −1 − 2 k (mod n).) Although this does not beat our O(n) algorithm given below asymptotically, in many cases it will run more quickly because of the simplicity of the operations. This is particularly true if the subgroup generated by 2 (mod n) is small.

A dynamic programming algorithm
In this section we show how to check whether n is sturdy using dynamic programming.
By Corollary 2, we can restrict our attention to the case where n is odd. In this case, the powers of two P n = {2 i : i ≥ 0} form a cyclic subgroup of (Z/(n)) * , the multiplicative group of integers relatively prime to n. Define ν = ord 2 n = |P n |, the order of 2 in the group (Z/(n)) * . Hence, to find a positive multiple of n whose binary expansion contains exactly k 1's, it suffices to find an appropriate linear combination of k elements of P n (counted with repetition) that sums to 0 (mod n). More precisely, we need to find non-negative integers a 1 , a 2 , . . . , a i and distinct elements e 1 , e 2 , . . . , e i ∈ P n such that a 1 e 1 + · · · + a i e i ≡ 0 (mod n) a 1 + a 2 + · · · + a i = k, for integers k ≥ 1. This is the kind of problem that dynamic programming is well-suited for. To restrict the amount of work required in a dynamic programming algorithm for this we make use of the following lemma.
Lemma 12. For an integer base b ≥ 2 let P b,n = {b i mod n : i ∈ N} and suppose that e 1 , e 2 , . . . , e m are the distinct elements of P b,n . If there exist non-negative integers a 1 , a 2 , . . . , a m such that a 1 e 1 +a 2 e 2 +· · ·+a m e m ≡ 0 (mod n) and a 1 +· · ·+a m = k, then there exist non-negative integers c 1 , c 2 , . . . , c m < b and l ≤ k such that c 1 e 1 + c 2 e 2 + · · · + c m e m ≡ 0 (mod n) and c 1 + · · · + c m = l.
Proof. Suppose we have non-negative integers a 1 , a 2 , . . . , a m such that a 1 e 1 + a 2 e 2 + · · · + a m e m ≡ 0 (mod n) and a 1 + · · · + a m = k. If we have a 1 , a 2 , . . . , a m < b then we are done. So suppose that there is some i such that a i ≥ b. Let j be the integer such that be i ≡ e j (mod n). Then we can take m r=1,r =i,r =j Setting a i := a i − b and a j := a j + 1 and k := k − b + 1, we can repeat this argument until a 1 , . . . , a m < b.
Let us start with determining whether n is sturdy. It suffices to solve the problem of the previous paragraph for 1 ≤ k < s 2 (n). The idea is that we will fill in the entries of a 3-dimensional boolean array x with the following meaning: the entry x[i, j, r] is true if and only if the integer j has a representation as a sum of i ≥ 1 powers of 2, using as summands only the first r elements of the set P n without repetition. We fill in the array x in increasing order of r.
For initialization, we set all elements of x to false, except that we set x[0, 0, r] to true for 0 ≤ r ≤ ν.
To solve the remaining three problems, we need to record more information than just the ability to represent j as a sum of powers of 2. The integer array y[i, j, r] is used to record the smallest integer congruent to j (mod n) that is the sum of exactly i powers of 2 (without repetition), using only the first r elements of the set P n .
The complete algorithm is given in Appendix A. Our dynamic programming algorithm has three nested loops, which gives a running time of O(ν · n · s 2 (n)). Since ν = ord n 2 could be as large as n − 1, and s 2 (n) could be as big as log 2 n, this gives a worst-case running time of O(n 2 log n), where we are measuring the run time in terms of RAM operations on integers of size about n. This means that this algorithm will only be feasible for integers smaller than about 10 7 .

An algorithm based on finite automata
In this section we provide a different, much faster algorithm for checking sturdiness, based on finite automata.
The idea is simple. It is easy to create a deterministic finite automaton (DFA) accepting the binary representations of the positive integers divisible by n. Such an automaton has n states [1] and exactly one final state. Next, we can easily construct a DFA A t accepting those strings starting with a 1 and having at most t ones. Using the standard "direct product" construction [15, pp. 59-60], we can construct a DFA M t of (t + 2)n states for the intersection of these two languages; it has exactly t+1 final states f 0 , f 1 , . . . , f t corresponding to positive integers divisible by n with 0, 1, . . . , t 1's respectively. Then some multiple of n has at most t 1's iff M t accepts at least one string. We can test this condition (and even find the lexicographically least string accepted) using breadth-first search to decide if some By choosing t = s 2 (n) − 1 we can determine if n is sturdy in O(n log n) steps. Similarly, by allowing the breadth-first search to run to completion and keeping track of the least string in radix order used to reach each state, we can recover swm(n), msw(n), and mfw(n) by examining each of the final states for whether or not they were visited in the search and looking at the least string in radix order used in each case. More precisely, the value of swm(n) is the least integer i such that final state f i in M t is reached in the breadth-first search, or s 2 (n) if no final state is reached. The value of msw(n) is the least string in radix order used to reach f swm(n) interpreted as an integer and divided by n, or 1 if n is sturdy. The value of mfw(n), if it is defined, is the least string in radix order among all such strings used to reach a final state, interpreted as an integer and divided by n. To avoid needing to store the representation of large integers, we instead store the exponents of the current power of 2 and a pointer to the previous power. From this linked list we can reconstruct the appropriate number.
Theorem 13. We can decide whether n is sturdy O(n log n) steps. In the same time bound we can compute swm(n) and msw(n). If n is flimsy, we can compute mfw(n) in the same time bound.
This algorithm is practical for n up to about 10 10 . The main constraint is likely to be space and not time.

Improving the automaton-based algorithm
With a small modification to this idea of using a breadth-first search on the graph defined by automaton M , we can make further improvements to the time complexity. Consider the deterministic finite automaton M n accepting the binary representations of the positive integers divisible by n. We then define a directed graph G n with vertices given by the states of M n and directed, weighted edges given by the transitions of M n where transitions on the symbol 0 are given an edge weight of 0 in G n and transitions on the symbol 1 are given an edge weight of 1 in G n . We augment G n with one additional vertex, v s , with a single outgoing edge of weight 1 to the vertex corresponding to the state reached when M n reads any input of the form 0 * 1. If v f is the vertex corresponding to the accepting state in M n , then there is a path from v s to v f of weight k if and only if there is a non-zero multiple of n with Hamming weight k. The shortest path problem on a graph G = (V, E) with edge weights in {0, 1} can be solved in time O(|V | + |E|) using a variation of the breadth-first search algorithm. In place of the queue used in a standard breadth-first search, we use a double ended queue.
We process a node by traversing incident edges of weight 0 and pushing the nodes reached to the front of the queue if they have not been processed already. Edges of weight 1 are also traversed, but the nodes reached are pushed to the back of the queue provided that they have not been processed already. After a node has been processed, the next node at the front of the queue is dequeued and processed if it has not been processed already, otherwise it is just discarded. The depth of the search can be tracked as in a standard breadth-first search. Thus we achieve the following improvement.
From this approach we are still able to construct an example of a multiple of n achieving the minimum Hamming weight over all multiples of n. It is simply a matter of maintaining the path used in the breadth-first search algorithm finding the shortest path from v s to v f in G n . However, there is no guarantee that this is the least multiple of n with this property. To find the least multiple we can use the linear-time algorithm to first determine the minimum Hamming weight. For minimum Hamming weight k, we take the direct product of automaton M n accepting the base-2 representations of all multiples of n and the automaton accepting all binary strings with exactly k 1's. A breadth-first search on this product automaton gives the least non-zero multiple of n with Hamming weight k. This second breadth-first search has worst case time complexity O(n log n), giving overall complexity O(n log n) for finding the least non-zero multiple of n having the minimum Hamming weight over all non-zero multiples of n.

Another breadth-first search approach
We can take advantage of Lemma 12 to evaluate sturdiness and compute swm and msw using a breadth-first search on a different graph structure. As before, to test the sturdiness of an integer n ≥ 3, we construct an (n + 1)-vertex graph with n of the vertices representing the distinct residue classes modulo n, which we will refer to as [0], [1], . . . , [n − 1], and one special vertex, v 0 , corresponding to the number 0. The graph contains a directed edge from vertex [x] to vertex [y] if and only if x + 2 j ≡ y (mod n) for some integer j ≥ 0. Similarly, there is an edge from v 0 to [y] if and only if 2 j ≡ y (mod n). Hence each vertex has out-degree ν = ord n 2. The idea of this construction is to treat traversing an edge from [x] to [x + 2 j ] as choosing to use the jth power of 2 as a summand in a summation to a value congruent to 0 modulo n. Thus, to compute swm(n) we are looking for the length of the shortest path from v 0 to [0] and this can be found via a breadth-first search. Furthermore, by keeping track of the smallest sum required to reach each state, we can also recover msw(n) from such a breadth-first search. Rather than running the breadth-first search to completion, we can terminate as soon as we reach a depth equal to s 2 (n), as we will know by then whether or not n is sturdy.
With this approach we can take advantage of the structure of the graph to speed up testing for sturdiness. If during the breadth first search we visit a node [x] such that [n − x] has already been visited, then since the length of the shortest path from [x] to [0] is equal to the length of the shortest path from v 0 to [n − x] either we will know that n is not sturdy, or that it is not necessary to continue searching from [x]. This greatly, improves the efficiency of the testing for sturdiness.
The complexity of this approach, for evaluating sturdiness, and computing swm(n) and msw(n) is O(n 2 ) since we are performing a breadth-first search on a graph with n+1 vertices each with ν = O(n) outgoing edges. In practice this approach seems to perform much better than our naive O(n 2 ) upper bound would suggest, especially in testing for sturdiness, due to the early exit conditions.

Running time comparison
To demonstrate how these algorithms behave in practice, we compiled timing information for each of the approaches and each of the four functions of interest for consecutive integers starting from 1. Each of the algorithms are implemented as described above. However, before applying each algorithm the baby-step giant-step algorithm, as in Section 4.1, is used to exit faster in those cases where swm(n) = 2. Running times for the mfw function with the order deg bfs algorithm are not given because there does not seem to be a natural approach for using this idea to evaluate mfw. The computations producing the given running times were performed on macOS Catalina version 10.15.2 on a 2.3 GHz Intel Core i5 processor. Implementations of our algorithms can be found in the Github repository https://github.com/FinnLidbetter/sturdy-numbers . In the tables below, the algorithmic approaches are named according to the commands used in the program-runner in the Github repository. Here, the dp algorithm refers to the dynamic programming approach described in Section 5, the aut algorithm refers to the automaton-based approach described in Section 6, the bfs01 algorithm refers to the improved automaton-based approach described in Section 7, and the order deg bfs algorithm refers to the alternative breadth-first search approach described in Section 8.  and mentions 616318177 as an additional sturdy prime, although it was not known if this was the next sturdy prime to occur in the sequence. Using our methods, we checked all primes p < 2 32 . We confirmed the results in the OEIS and found that 616318177 and 2147483647 are the only remaining sturdy primes in that range. The computation took approximately 23 hours on a laptop. We also computed frequency counts for the values of swm for odd n > 1, not just primes, and they are given in Table 10. swm(n) n < 2 20 2 20 < n < 2 21 2 21 < n < 2 22 2 22 < n < 2 23 2  115931  107650  208333  403823  3  286681  294938  596522  1205753  4  83895  83958  168138  336448  5  19287  19242  38566  77071  6  9903  9892  19812  39635  7  4246  4265  8510  17023  8  2274  2269  4548  9104  9 1027  We also computed counts of sturdy numbers up to 10 i for i = 1, 2, 3, 4, 5, 6, and they are given below: i Number of sturdy numbers < 10 i

Numbers with few 0's
We can also use finite automata to determine when numbers with few 0's are flimsy. More precisely, for each pair of integers j, k we can build a DFA M 2 (j, k) accepting those (n) 2 for which (n) 2 has j 0's and (kn) 2 has more than j + t 0's, where t = |(kn) 2 | − |(n) 2 |. Such an n is guaranteed to be flimsy. We can determine t by reading the input n, least significant digit first, and computing (kn) 2 on the fly, keeping track of the carries. Let j be a fixed natural number. By choosing an appropriate set of flimsy witnesses k (which can be guessed empirically), we can determine all flimsy numbers having exactly j 0's in their binary representation. We do this by computing the DFA's M 2 (j, k) and unioning them together to get a final automaton M j . We expect there to be a finite set of "sporadic" sturdy exceptions, and (according to Theorem 9) an infinite set of sturdy exceptions consisting of those numbers with binary representation of the form s1 i s, where s begins with 1 and ends with 0. This expectation can then be verified by considering the language accepted by M j ; the finite set of sturdy exceptions can be tested using our algorithms previously discussed. The multipliers we used in constructing M j are the odd numbers ≤ 2 j+1 + 1.
With these ideas we can prove the following theorem.
Theorem 15.    Based on this theorem, we make the following conjecture.
Conjecture 16. Every number with j 0's is flimsy, with exceptions of the form s1 i s, i ≥ 0, where |s| = j and s begins with 1 and ends with 0, and only finitely many additional exceptions.

The k-flimsy numbers via formal language theory
In this section we describe a new approach, based on formal language theory, for understanding the distribution of the k-flimsy numbers. Recall these are the numbers The majority of the results in this section are about the case k = 3, although in principle our technique can be applied to any odd k.
Kátai [16] studied the difference s 2 (3n)−s 2 (n), and proved that this quantity is essentially normally distributed, in a certain sense. Stolarsky [28] conjectured that the natural density of the k-flimsy numbers is 1/2 for all odd k. His conjecture was later proved by W. M. Schmidt [25] and J. Schmid [24]. All these results use rather sophisticated tools of number theory and probability.
In contrast, in this section we obtain rather detailed results on the distribution of 3-flimsy numbers through a (more or less) purely mechanical approach based on formal language theory. The main result of this section is the following: where c = 7 Our method starts with a pushdown automaton (PDA) recognizing the k-flimsy numbers, and by a series of steps, it is converted into an asymptotic series expansion for the number of k-flimsy numbers with N bits. Previously, the basic approach has been used for a wide variety of combinatorial enumerations; see, for example, [4,5,2,3]. We have implemented all the steps, and the flow of control is explained in the diagram below. We now explain briefly what each box in the diagram does, with more detailed explanation to follow. For all undefined terms, see any textbook on automata theory or formal languages, such as [15].
First, given an odd integer k ≥ 3, we build an unambiguous pushdown automaton (PDA) M k that recognizes the base-2 representation of elements of F k ; more precisely, M k recognizes the language (F k ) R 2 . The length-N strings in (F k ) R 2 are in 1-1 correspondence with the flimsy numbers in the half-open interval [2 N −1 , 2 N ), so our goal is to estimate the cardinality of (F k ) R 2 ∩ {0, 1} N as precisely as possible. Second, we convert M k to an unambiguous context-free grammar G k generating (F k ) R 2 . We simplify this context-free grammar by deleting useless symbols (those symbols that do not participate in the derivation of any terminal string, or are not reachable from the start variable), obtaining a new CFG G k .
Third, we convert G k to a system of equations in the variables of G k . These variables represent formal power series, with the property that the number of length-N strings generated by a variable A is given by [x N ]A(x), the coefficient of x N in the power series A.
Fourth, using Gröbner bases, we solve this system of equations, obtaining an algebraic equation satisfied by the formal power series S(x), where S is the start variable of the grammar G k .
Finally, using Bruno Salvy's gdev package, written in Maple, we can determine the asymptotic behavior of [x N ]S(x) using the saddle-point method (as discussed by, e.g., Flajolet and Sedgewick [12]). In principle, we can obtain as many terms as we wish of the asymptotic expansion.
Theorem 17 now follows by performing each of these steps. The first four steps are done with original code written by the first author in Python, and the last two steps are done with Maple. The code for each step is available at https://github.com/FinnLidbetter/sturdy-numbers . We now give more complete details of some of the steps.

Constructing the PDA M k
The general idea is as follows: we create a PDA accepting the base-2 representation of kflimsy numbers n. We use the stack of the PDA to record the absolute value of s 2 (n)−s 2 (kn), and we use the state to record both the carry needed when multiplying input by k, and the sign of s 2 (n) − s 2 (kn). We accept the input if the carry is 0, the sign of s 2 (n) − s 2 (kn) is positive, and the stack has at least one counter.
Our PDA is assumed to begin its computation with a special symbol, Z, on top of the stack, and if the input is accepted, to end its computation when the stack becomes empty.
The sketch above is not quite enough because of two technical issues. First, (a) in some cases this approach requires reading extra leading zeroes (which, because we are representing numbers starting with the least significant digit first, would be at the end of the input), in order to guarantee that the carry for s 2 (kn) was taken into account and (b) we must have that the leading bit of the input is 1, to avoid incorrectly counting smaller numbers as having n bits.
To handle both these issues, we slightly modify the construction in several ways. First, if the state has a minus sign, then the stack holds |y| 1 − |x| 1 X's, where x is the input seen so far and y is the |x| least significant bits of k(x) R 2 . On the other hand, if the state has a positive sign, then the stack holds |x| 1 − |y| 1 − 1 X's.
Second, to simulate the needed leading zeroes required to handle the carry, without actually reading them, we use a special series of log 2 k states to pop X's from the stack.
Finally, we have a special state used to empty the stack when acceptance is detected. The total number of states is therefore at most 2k + log 2 k.
The resulting PDA M 3 is depicted in Figure 12.1. One important property of our construction is that our PDA M k is unambiguous. By this we mean that every accepted word has exactly one accepting computational path.

Converting the PDA to a CFG
We can convert M k to an equivalent context-free grammar G k using a standard technique called the "triple construction" [15, pp. 115-119]. This gives us a grammar G k with O(k 2 ) variables and O(k 3 ) productions. Now we use the fact, proved in [13,Thm. 5.4.3,p. 151], that performing the triple construction on an unambiguous PDA gives us an unambiguous grammar.

Cleaning the CFG
We can remove useless symbols from our grammar G k by removing all variables that do not derive a terminal string, then removing all productions containing these removed variables, and then removing all variables and terminals that are not reachable from the start variable. This is a standard procedure, and is described in greater detail in [15, pp. 88-90].
Once this is complete, it may be found that there is a variable X that has only one production X → α. If X is not the start variable, then it can be deleted from the set of variables, and all instances of X in production rules can be replaced with α.
For example, when we convert our PDA M 3 , we get an unambiguous grammar G 3 ; cleaning G 3 using this procedure gives us the following grammar G 3 :

Converting the CFG to a system of equations
This transformation was discussed in [9]. It suffices to replace, in each set of productions A → α 1 | α 2 | . . . | α i of a grammar G, each terminal symbol by the indeterminate x, each | symbol by a plus sign, and the → with an equals sign. For a proof of correctness, see [17,19].
Performing this transformation on G 3 gives us the following system of equations:

Solving the system
We can now solve the resulting system of equations for S, obtaining an algebraic equation for which S is the root. The main tool is Groebner bases, for which a helpful package already exists in Maple.
Using the code given in Appendix B, we find the following quadratic equation for S in the case k = 3.
Solving this quadratic for S gives Since the grammar G 3 is unambiguous, the formal power series S(x) is the census generating function for the set (F 3 ) R 2 . In particular, this means that [

Asymptotic expansion of the coefficients of the power series
Finally, we use Flajolet-Sedgewick-style asymptotic analysis [12, §VII. 7.1] to determine an asymptotic formula for the N 'th coefficient of the power series expansion for S(x). Conveniently, there is a Maple package algolib, written by Bruno Salvy [23], to accomplish this. When we run this on our formula for S(x), we get our desired result.
This completes our discussion of the proof of Theorem 17.
Remark 18. We could easily determine more terms in the asymptotic expansion, if we wanted, using the same ideas. For example, we can find that the number of 3-flimsy numbers in the interval [2 N −1 , 2 N ) is Corollary 19. The number of 3-flimsy numbers Proof. For any real number a > 0 we have Summing (1) and applying the inequalities above gives the desired result.
Theorem 20. The number of 5-flimsy numbers in the interval [2 N −1 , 2 N ) is where c = 3 Proof. This is determined using the same method as the proof for Theorem 17. In this process, we compute the unambiguous PDA M 5 , depicted in Figure 12.6. From M 5 we construct the (simplified) unambiguous grammar G 5 as follows: This gives us the system of equations: Finally, we employ the same methods and Maple packages used in Sections 12.5 and 12.6, which give us our desired result.
We can also use the same ideas to compute the distribution of flimsy numbers in other bases. As an example we proved Theorem 21. The number of integers in the range [3 N −1 , 3 N ) that are 2-flimsy in base 3 is .
Proof. As before. We omit the details.

The k-equal numbers via formal language theory
Another quantity of interest is the number of n for which s 2 (n) = s 2 (kn). We call such n k-equal. By generalizing the approach used in Section 12, we can compute how many integers n ∈ [2 N −1 , 2 N ) are k-equal.
In particular, we modify PDA M k by changing the transitions to the END states. Whereas M k transitions to END when reading a 1 if following that 1 with sufficiently many zeros would reach the state (+, 0), instead we want such an input to reach the state (−, 0) with no counters on the stack.
This modification gives us the following unambiguous PDAs M k that recognize the kequal numbers for k = 3, 5:  Following the same procedure described in Theorem 17 of converting M 3 and M 5 into unambiguous CFGs and simplifying them gives us the following: The unambiguous CFG for 3-equal numbers: The unambiguous CFG for 5-equal numbers: Finally, converting these grammars into systems of equations, solving, and finding the asymptotics gives us the following results.