DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2021.10

Computational Fun with Sturdy and Flimsy Numbers

Authors: Trevor Clokie, Thomas F. Lidbetter, Antonio J. Molina Lovett, Jeffrey Shallit, and Leon Witzman

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

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.

Cite as

Trevor Clokie, Thomas F. Lidbetter, Antonio J. Molina Lovett, Jeffrey Shallit, and Leon Witzman. Computational Fun with Sturdy and Flimsy Numbers. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{clokie_et_al:LIPIcs.FUN.2021.10,
  author =	{Clokie, Trevor and Lidbetter, Thomas F. and Molina Lovett, Antonio J. and Shallit, Jeffrey and Witzman, Leon},
  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 =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.10},
  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}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2020.12

A Simple Algorithm for Minimum Cuts in Near-Linear Time

Authors: Nalin Bhardwaj, Antonio J. Molina Lovett, and Bryce Sandlund

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract

We consider the minimum cut problem in undirected, weighted graphs. We give a simple algorithm to find a minimum cut that 2-respects (cuts two edges of) a spanning tree T of a graph G. This procedure can be used in place of the complicated subroutine given in Karger’s near-linear time minimum cut algorithm [Karger, 2000]. We give a self-contained version of Karger’s algorithm with the new procedure, which is easy to state and relatively simple to implement. It produces a minimum cut on an m-edge, n-vertex graph in O(m log³ n) time with high probability, matching the complexity of Karger’s approach.

Cite as

Nalin Bhardwaj, Antonio J. Molina Lovett, and Bryce Sandlund. A Simple Algorithm for Minimum Cuts in Near-Linear Time. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhardwaj_et_al:LIPIcs.SWAT.2020.12,
  author =	{Bhardwaj, Nalin and Molina Lovett, Antonio J. and Sandlund, Bryce},
  title =	{{A Simple Algorithm for Minimum Cuts in Near-Linear Time}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.12},
  URN =		{urn:nbn:de:0030-drops-122594},
  doi =		{10.4230/LIPIcs.SWAT.2020.12},
  annote =	{Keywords: minimum cut, sparsification, near-linear time, packing}
}

Search Results

Documents authored by Molina Lovett, Antonio J.

Computational Fun with Sturdy and Flimsy Numbers

Abstract

Cite as

A Simple Algorithm for Minimum Cuts in Near-Linear Time

Abstract

Cite as

Thanks for your feedback!

Could not send message