Master’s Thesis Presentation • Algorithms and Complexity — Counting Flimsy Numbers via Formal Language TheoryExport this event to calendar

Monday, January 25, 2021 — 4:00 PM EST

Please note: This master’s thesis presentation will be given online.

Trevor Clokie, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Jeffrey Shallit

Let s_2(n) be the sum of the digits of n when expressed in base 2. For integers n and k, Stolarsky defined n to be k-flimsy if s_2(kn) < s_2(n). In this paper, we generalize the definition of k-flimsy numbers to all bases b, and provide a method to construct a pushdown automaton recognizing the k-flimsy base-b numbers. Using the tools of context-free languages and analytic combinatorics, we use this automaton to determine precise asymptotics for the number of k-flimsy N-digit numbers in base b. Lastly, using the results we obtained, we discuss the natural densities of k-flimsy numbers in base b for all values k and b.

Our main results can be found in Theorems 2, 3, 8, and 9.


To joint this master’s thesis presentation on Zoom, please go to https://us02web.zoom.us/j/88171362356?pwd=L2hNN3hUN3BGMTdoYUI4ZlVNNTdsQT09

Location 
Online presentation
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
28
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
  1. 2021 (45)
    1. May (1)
    2. April (1)
    3. March (11)
    4. February (13)
    5. January (19)
  2. 2020 (217)
    1. December (18)
    2. November (12)
    3. October (7)
    4. September (21)
    5. August (28)
    6. July (14)
    7. June (18)
    8. May (16)
    9. April (20)
    10. March (16)
    11. February (25)
    12. January (22)
  3. 2019 (255)
  4. 2018 (217)
  5. 2017 (36)
  6. 2016 (21)
  7. 2015 (36)
  8. 2014 (33)
  9. 2013 (23)
  10. 2012 (4)
  11. 2011 (1)
  12. 2010 (1)
  13. 2009 (1)
  14. 2008 (1)