License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2021.10
URN: urn:nbn:de:0030-drops-127715
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12771/
Go to the corresponding LIPIcs Volume Portal

Clokie, Trevor ; Lidbetter, Thomas F. ; Molina Lovett, Antonio J. ; Shallit, Jeffrey ; Witzman, Leon

Computational Fun with Sturdy and Flimsy Numbers

pdf-format:
LIPIcs-FUN-2021-10.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{clokie_et_al:LIPIcs:2020:12771,
  author =	{Trevor Clokie and Thomas F. Lidbetter and Antonio J. Molina Lovett and Jeffrey Shallit and Leon Witzman},
  title =	{{Computational Fun with Sturdy and Flimsy Numbers}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Martin Farach-Colton and Giuseppe Prencipe and Ryuhei Uehara},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12771},
  URN =		{urn:nbn:de:0030-drops-127715},
  doi =		{10.4230/LIPIcs.FUN.2021.10},
  annote =	{Keywords: sturdy number, flimsy number, context-free grammar, finite automaton, enumeration}
}

Keywords: sturdy number, flimsy number, context-free grammar, finite automaton, enumeration
Collection: 10th International Conference on Fun with Algorithms (FUN 2021)
Issue Date: 2020
Date of publication: 16.09.2020
Supplementary Material: Implementations of our algorithms can be found in the GitHub repository https://github.com/FinnLidbetter/sturdy-numbers.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI