Computational aspects of sturdy and flimsy numbers. (English) Zbl 1537.11039
Summary: 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. When \(n\) is proven flimsy by multiplier \(k\), we say \(n\) is k-flimsy. We study computational aspects of sturdy and flimsy numbers. We provide some criteria for determining whether a number is sturdy. We study the computational problem of checking whether a given number is sturdy, giving several algorithms for the problem, focusing particularly on the case \(b = 2\). 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.
MSC:
| 11B85 | Automata sequences |
| 11A63 | Radix representation; digital problems |
| 11Y16 | Number-theoretic algorithms; complexity |
| 68Q42 | Grammars and rewriting systems |
| 68Q45 | Formal languages and automata |
Online Encyclopedia of Integer Sequences:
Decimal sturdy numbers: positive integers m such that sum of digits of k * m for any positive integer k is at least the sum of digits of m.Decimal sturdy primes: primes p such that sum of digits of k*p for any positive integer k is at least the sum of digits of p.
References:
| [1] | Alexeev, B., Minimal DFAs for testing divisibility, J. Comput. Syst. Sci., 69, 235-243 (2004) · Zbl 1076.68038 |
| [2] | Asinowski, A.; Bacher, A.; Banderier, C.; Gittenberger, B., Analytic combinatorics of lattice paths with forbidden patterns: enumerative aspects, (Klein, S. T.; etal., LATA 2018. LATA 2018, Lecture Notes in Computer Science, vol. 10792 (2018), Springer-Verlag), 195-206 · Zbl 1437.68090 |
| [3] | Asinowski, A.; Bacher, A.; Banderier, C.; Gittenberger, B., Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Algorithmica, 82, 386-428 (2020) · Zbl 1437.68091 |
| [4] | Banderier, C.; Drmota, M., Coefficients of algebraic functions: formulae and asymptotics, (Pilaud, V., FPSAC 2013. FPSAC 2013, DMTCS Proc., vol. AS (2013), DMTCS), 1065-1076 · Zbl 1294.05011 |
| [5] | Banderier, C.; Drmota, M., Formulae and asymptotics for coefficients of algebraic functions, Comb. Probab. Comput., 24, 1-53 (2015) · Zbl 1371.05009 |
| [6] | Bašić, B., The existence of n-flimsy numbers in a given base, Ramanujan J., 43, 359-369 (2017) · Zbl 1421.11011 |
| [7] | Bell, J.; Hare, K.; Shallit, J., When is an automatic set an additive basis?, Proc. Am. Math. Soc. Ser. B, 5, 50-63 (2018) · Zbl 1437.11017 |
| [8] | Chen, L. H.Y.; Hwang, H.-K.; Zacharovas, V., Distribution of the sum-of-digits function of random integers: a survey, Probab. Surv., 11, 177-236 (2014) · Zbl 1327.60029 |
| [9] | Chomsky, N.; Schützenberger, M. P., The algebraic theory of context-free languages, (Braffort, P.; Hirschberg, D., Computer Programming and Formal Systems (1963), North Holland: North Holland Amsterdam), 118-161 · Zbl 0148.00804 |
| [10] | Clokie, T.; Lidbetter, T. F.; Molina Lovett, A.; Shallit, J.; Witzman, L., Computational fun with sturdy and flimsy numbers, (Farach-Colton, M.; Prencipe, G.; Uehara, R., FUN 2021. FUN 2021, LIPIcs, vol. 157 (2021), Schloss Dagstuhl—Leibniz-Zentrum für Informatik), 10:1-10:21 · Zbl 1515.68160 |
| [11] | Dartyge, C.; Luca, F.; Stănică, P., On digit sums of multiples of an integer, J. Number Theory, 129, 2820-2830 (2009) · Zbl 1241.11113 |
| [12] | Elsholtz, C., Almost all primes have a multiple of small Hamming weight, Bull. Aust. Math. Soc., 94, 224-235 (2016) · Zbl 1388.11069 |
| [13] | Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press · Zbl 1165.05001 |
| [14] | Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1985), Oxford University Press |
| [15] | Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley · Zbl 0411.68058 |
| [16] | Hasse, H., Über die Dichte der Primzahlen p, für die einevorgegebene ganz rationale Zahl \(a \neq 0\) von gerader bzw. ungerader Ordnung mod p ist, Math. Ann., 166, 19-23 (1966) · Zbl 0139.27501 |
| [17] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley · Zbl 0426.68001 |
| [18] | Kátai, I., Change of the sum of digits by multiplication, Acta Sci. Math. (Szeged), 39, 319-328 (1977) · Zbl 0336.10051 |
| [19] | Kuich, W.; Salomaa, A., Semirings, Automata, Languages (1986), Springer-Verlag · Zbl 0582.68002 |
| [20] | Odoni, R. W.K., A conjecture of Krishnamurthy on decimal periods and some allied problems, J. Number Theory, 13, 303-319 (1981) · Zbl 0471.10031 |
| [21] | Panholzer, A., Gröbner bases and the defining polynomial of a context-free grammar generating function, J. Autom. Lang. Comb., 10, 79-97 (2005) · Zbl 1087.68046 |
| [22] | Phedotov, Pavel V., Sum of digits of a multiple of a given number (2002), (in Russian), Available at |
| [23] | Pless, V.; Solé, P.; Qian, Z., Cyclic self-dual \(Z_4\)-codes, Finite Fields Appl., 3, 48-69 (1997) · Zbl 1053.94573 |
| [24] | Rajasekaran, A.; Shallit, J.; Smith, T., Additive number theory via automata theory, ACM Trans. Comput. Syst., 64, 542-567 (2020) · Zbl 1475.11040 |
| [25] | Salvy, B., gdev package of algolib version 17.0 (2013), Available at |
| [26] | Schmid, J., The joint distribution of the binary digits of integer multiples, Acta Arith., 43, 391-415 (1984) · Zbl 0489.10008 |
| [27] | Schmidt, W. M., The joint distributions of the digits of certain integer s-tuples, (Erdős, P., Studies in Pure Mathematics to the Memory of Paul Turán (1983), Birkhäuser), 605-622 · Zbl 0523.10030 |
| [28] | Shanks, D., Class number, a theory of factorization and genera, (Proc. Sympos. Pure Math., vol. 20 (1969)), 415-440 · Zbl 0223.12006 |
| [29] | Sloane, N. J.A., The on-line encyclopedia of integer sequences (2022), Available at · Zbl 1044.11108 |
| [30] | Stolarsky, K. B., Integers whose multiples have anomalous digital frequencies, Acta Arith., 38, 117-128 (1980/81) · Zbl 0448.10010 |
| [31] | Wagstaff, S. S., The Cunningham project (2019), Available at · Zbl 1095.11056 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
