×

Sumsets of Wythoff sequences, Fibonacci representation, and beyond. (English) Zbl 07479498

Summary: Let \(\alpha=(1+\sqrt{2})/2\) and define the lower and upper Wythoff sequences by \(ai = \lfloor{ i\alpha\rfloor},b_i=\lfloor i\alpha^2\rfloor\) for \(i\ge 1\). In a recent interesting paper, S. Kawsumarng et al. [Period. Math. Hung. 82, No. 1, 98–113 (2021; Zbl 1474.11033)] proved a number of results about numbers representable as sums of the form \(a_i +a_j\), \(b_i +b_j\), \(a_i +b_j\), and so forth. In this paper I show how to derive all of their results, using one simple idea and existing free software called Walnut. The key idea is that for each of their sumsets, there is a relatively small automaton accepting the Fibonacci representation of the numbers represented. I also show how the automaton approach can easily prove other results.

MSC:

11B13 Additive bases, including sumsets
68Q45 Formal languages and automata
68V15 Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.)

Citations:

Zbl 1474.11033

Software:

Walnut

References:

[1] Barbé, A.; von Haeseler, F., Limit sets of automatic sequences, Adv. Math., 175, 169-196 (2003) · Zbl 1050.11026 · doi:10.1016/S0001-8708(02)00043-9
[2] Bell, J.; Lidbetter, TF; Shallit, J.; Hoshi, M.; Seki, S., Additive number theory via approximation by regular languages, DLT 2018, 121-132 (2018), Berlin: Springer, Berlin · Zbl 1462.11014
[3] Carlitz, L.; Scoville, R.; Hoggatt, VE Jr, Fibonacci representations of higher order, Fibonacci Q., 10, 43-69 (1972) · Zbl 0236.05002
[4] Dekking, FM; Shallit, J.; Sloane, NJA, Queens in exile: non-attacking queens on infinite chess boards, Electron. J. Combin., 27, 1, 1-27 (2020) · Zbl 1435.91038 · doi:10.37236/8905
[5] Du, CF; Mousavi, H.; Rowland, E.; Schaeffer, L.; Shallit, J., Decision algorithms for Fibonacci-automatic words, II: related sequences and avoidability, Theor. Comput. Sci., 657, 146-162 (2017) · Zbl 1366.68223 · doi:10.1016/j.tcs.2016.10.005
[6] Du, CF; Mousavi, H.; Schaeffer, L.; Shallit, J., Decision algorithms for Fibonacci-automatic words, III: enumeration and abelian properties, Int. J. Found. Comput. Sci., 29, 8, 943-963 (2016) · Zbl 1366.68224 · doi:10.1142/S0129054116500386
[7] Feinberg, M., Fibonacci-Tribonacci, Fibonacci Q., 1, 3, 71-74 (1963)
[8] Hopcroft, JE; Ullman, JD, Introduction to Automata Theory, Languages, and Computation (1979), Boston: Addison-Wesley, Boston · Zbl 0426.68001
[9] Kawsumarng, S.; Khemaratchatakumthorn, T.; Noppakaew, P.; Pongsriiam, P., Sumsets associated with Wythoff sequences and Fibonacci numbers, Period. Math. Hung. (2020) · Zbl 1474.11033 · doi:10.1007/s10998-020-00343-0
[10] Lekkerkerker, CG, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin, 29, 190-195 (1952) · Zbl 0049.03101
[11] H. Mousavi, Automatic theorem proving in Walnut. Available at arXiv:1603.06017 (2016)
[12] Mousavi, H.; Schaeffer, L.; Shallit, J., Decision algorithms for Fibonacci-automatic words, I: basic results, RAIRO Inform. Théor. Appl., 50, 39-66 (2016) · Zbl 1366.68226 · doi:10.1051/ita/2016010
[13] Mousavi, H.; Shallit, J.; Manea, F.; Nowotka, D., Mechanical proofs of properties of the Tribonacci word, WORDS 2015, 1-21 (2015), Berlin: Springer, Berlin
[14] Petkovšek, M.; Wilf, HS; Zeilberger, D., A = B (1996), Natick: A. K. Peters, Natick · doi:10.1201/9781439864500
[15] Rajasekaran, A.; Shallit, J.; Smith, T., Additive number theory via automata theory, Theor. Comput. Syst., 64, 542-567 (2020) · Zbl 1475.11040 · doi:10.1007/s00224-019-09929-9
[16] Silber, R., A Fibonacci property of Wythoff pairs, Fibonacci Q., 14, 380-384 (1972) · Zbl 0361.10011
[17] N.J.A. Sloane, et al., The On-Line Encyclopedia of Integer Sequences. Available at https://oeis.org (2020) · Zbl 1044.11108
[18] Zeckendorf, E., Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. R. Liège, 41, 179-182 (1972) · Zbl 0252.10011
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.