×

The ring of \(k\)-regular sequences. II. (English) Zbl 1058.68066

Summary: We continue our study of \(k\)-regular sequences begun in 1992 [see ibid. 98, 163–197 (1992; Zbl 0774.68072)]. We prove some new results, give many new examples from the literature, and state some open problems.

MSC:

68Q45 Formal languages and automata
11B83 Special sequences and polynomials
11B85 Automata sequences
68R15 Combinatorics on words

Citations:

Zbl 0774.68072

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Odious numbers: numbers with an odd number of 1’s in their binary expansion.
Stern’s diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1).
Sum of squares of digits of n.
Kimberling’s paraphrases: if n = (2k-1)*2^m then a(n) = k.
Table of n XOR m (or Nim-sum of n and m) read by antidiagonals with m>=0, n>=0.
a(0) = 0; thereafter a(2n) = n - a(n) - a(n-1), a(2n+1) = n - 2a(n) + 1.
a(0)=0, a(1)=a(2)=1; for n >= 1, a(3n+2) = 2a(n+1) + a(n), a(3n+1) = a(n+1) + 2a(n), a(3n) = 3a(n).
Josephus problem: a(2*n) = 2*a(n)-1, a(2*n+1) = 2*a(n)+1.
Numbers n with an even number of 1’s in binary, ignoring last bit.
Length of longest chain of subgroups in S_n.
Optimal cost function between two processors at distance n.
Number of overlap-free binary words of length n.
Thue-Morse sequence: let A_k denote the first 2^k terms; then A_0 = 0 and for k >= 0, A_{k+1} = A_k B_k, where B_k is obtained from A_k by interchanging 0’s and 1’s.
Write n in binary, interchange 0’s and 1’s, convert back to decimal.
Number of blocks of {1, 0, 1} in binary expansion of n.
Alternating bit sum for n: replace 2^k with (-1)^k in binary expansion of n.
Exponent of highest power of 3 dividing sum(0<=k<n, C(2n,n)).
a(n) = f(f(n)), where f() = A035327().
Random Fibonacci tree defined with the pair(1,1).
a(2n) = a(n) + a(n+1) + n (n > 1), a(2n+1) = a(n) + a(n-1) + 1 (n >= 1) with a(0) = a(1) = 1 and a(2) = 2.

References:

[1] Allouche, J.-P.; Baake, M.; Cassaigne, J.; Damanik, D., Palindrome complexity, Theoret. Comput. Sci., 292, 9-31 (2003) · Zbl 1064.68074
[2] Allouche, J.-P.; Shallit, J. O., The ring of \(k\)-regular sequences, Theoret. Comput. Sci., 98, 163-197 (1992) · Zbl 0774.68072
[3] Allouche, J.-P.; Shallit, J. O., The ubiquitous Prouhet-Thue-Morse sequence, (Ding, C.; Helleseth, T.; Niederreiter, H., Sequences and Their Applications, Proc. SETA ’98 (1999), Springer: Springer Berlin), 1-16 · Zbl 1005.11005
[4] J.-P. Allouche, J.O. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, Cambridge, 2003, to appear.; J.-P. Allouche, J.O. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, Cambridge, 2003, to appear. · Zbl 1086.11015
[5] J.-P. Allouche, N. Rampersad, J. Shallit, On integer sequences whose first iterates are linear, submitted for publication, 2003.; J.-P. Allouche, N. Rampersad, J. Shallit, On integer sequences whose first iterates are linear, submitted for publication, 2003.
[6] Arkin, J.; Arney, D. C.; Dewald, L. S.; Ebel, W. E., Families of recursive sequences, J. Recreational Math., 22, 85-94 (1990) · Zbl 0703.11009
[7] Babai, L., On the length of subgroup chains in the symmetric group, Comm. Algebra, 14, 1729-1736 (1986) · Zbl 0604.20004
[8] E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, Academic Press, Toronto, 1982.; E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, Academic Press, Toronto, 1982. · Zbl 0485.00025
[9] Cameron, P. J.; Solomon, R.; Turull, A., Chains of subgroups in symmetric groups, J. Algebra, 127, 340-352 (1989) · Zbl 0683.20004
[10] Carlitz, L., Single variable Bell polynomials, Collect. Math., 14, 13-25 (1962) · Zbl 0109.02906
[11] Carlitz, L., A problem in partitions related to the Stirling numbers, Bull. Amer. Math. Soc., 70, 275-278 (1964) · Zbl 0123.25505
[12] Carlitz, L., Some partition problems related to the Stirling numbers of the second kind, Acta Arith., 10, 409-422 (1965) · Zbl 0151.02601
[13] J. Cassaigne, Counting overlap-free binary words, in: P. Enjalbert, A. Finkel, K.W. Wagner (Eds.), STACS 93, Proc. 10th Symp. Theoretical Aspects of Computer Science, Vol. 665, Lecture Notes in Computer Science, Springer, Berlin, 1993, pp. 216-225.; J. Cassaigne, Counting overlap-free binary words, in: P. Enjalbert, A. Finkel, K.W. Wagner (Eds.), STACS 93, Proc. 10th Symp. Theoretical Aspects of Computer Science, Vol. 665, Lecture Notes in Computer Science, Springer, Berlin, 1993, pp. 216-225. · Zbl 0799.68153
[14] Chang, K.-N.; Tsai, S.-C., Exact solution of a minimal recurrence, Inform. Process. Lett., 75, 61-64 (2000) · Zbl 1339.68112
[15] Cobham, A., On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory, 3, 186-192 (1969) · Zbl 0179.02501
[16] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[17] Conway, J. H., On Numbers and Games (1976), Academic Press: Academic Press New York · Zbl 0334.00004
[18] P. Dumas, Récurrences Mahlériennes, Suites Automatiques, Études Asymptotiques, Thèse de Doctorat, Université Bordeaux I, 1993. INRIA Rapport 952, available from; P. Dumas, Récurrences Mahlériennes, Suites Automatiques, Études Asymptotiques, Thèse de Doctorat, Université Bordeaux I, 1993. INRIA Rapport 952, available from
[19] S. Eilenberg, Automata, Languages, and Machines, Vol. A, Academic Press, New York, 1974.; S. Eilenberg, Automata, Languages, and Machines, Vol. A, Academic Press, New York, 1974. · Zbl 0317.94045
[20] K.B. Ellul, J. Shallit, M.w. Wang, Regular expressions: new results and open problems, in: J. Dassow, M. Hoeberechts, H. Jürgensen, D. Wotschke (Eds.), Descriptional Complexity of Formal Systems (DCFS), Pre-Proceedings, 2002, pp. 17-34; Tech. Report No. 586, University of Western Ontario.; K.B. Ellul, J. Shallit, M.w. Wang, Regular expressions: new results and open problems, in: J. Dassow, M. Hoeberechts, H. Jürgensen, D. Wotschke (Eds.), Descriptional Complexity of Formal Systems (DCFS), Pre-Proceedings, 2002, pp. 17-34; Tech. Report No. 586, University of Western Ontario. · Zbl 1098.68069
[21] Graham, R.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1989), Addison-Wesley: Addison-Wesley Reading, MA
[22] R.K. Guy, Impartial games, in: R.K. Guy (Ed.), Combinatorial Games, Proc. Symp. Applied Mathematics, vol. 43, American Mathematical Society, Providence, RI, 1991, pp. 35-55.; R.K. Guy, Impartial games, in: R.K. Guy (Ed.), Combinatorial Games, Proc. Symp. Applied Mathematics, vol. 43, American Mathematical Society, Providence, RI, 1991, pp. 35-55. · Zbl 0739.90087
[23] Honsberger, R., Mathematical Gems III (1985), Mathematical Association of America: Mathematical Association of America Washington, DC · Zbl 0568.00001
[24] Kimberling, C., Numeration systems and fractal sequences, Acta Arith., 73, 103-117 (1995) · Zbl 0834.11010
[25] Kuczma, M. E., Problem 1922, Crux Math., 20, 74 (1994), (Solution in 21 (1995) 62-64)
[26] E. Kullberg, Beyond infinity: on the infinity series—the DNA of hierarchical music, in: A. Beyer (Ed.), The Music of Per \(Nø\); E. Kullberg, Beyond infinity: on the infinity series—the DNA of hierarchical music, in: A. Beyer (Ed.), The Music of Per \(Nø\)
[27] Lam, T. Y., The Algebraic Theory of Quadratic Forms (1973), Benjamin: Benjamin New York · Zbl 0259.10019
[28] Lambek, J.; Moser, L., On some two way classifications of integers, Canad. Math. Bull., 2, 85-89 (1959) · Zbl 0089.26601
[29] Mahler, K., The spectrum of an array and its application to the study of the translation properties of a simple class of arithmetic functions. Part Twoon the translation properties of a simple class of arithmetic functions, J. Math. Phys., 6, 158-163 (1927) · JFM 53.0265.03
[30] Morton, P.; Mourant, W., Paper folding, digit patterns, and groups of arithmetic fractals, Proc. London Math. Soc., 59, 253-293 (1989) · Zbl 0694.10009
[31] Morton, P.; Mourant, W. J., Digit patterns and transcendental numbers, J. Austral. Math. Soc. Ser. A, 51, 216-236 (1991) · Zbl 0746.11029
[32] Mossé, B., Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France, 124, 329-346 (1996) · Zbl 0855.68072
[33] Patruno, G., Solution to problem proposal 474, Crux Math., 6, 198 (1980)
[34] Pfister, A., Zur Darstellung von −1 als Summe von Quadraten in einem Körper, J. London Math. Soc., 40, 159-165 (1965) · Zbl 0131.25002
[35] Pfister, A., Quadratische Formen in beliebigen Körpern, Invent. Math., 1, 116-132 (1966) · Zbl 0142.27203
[36] Porges, A., A set of eight numbers, Amer. Math. Monthly, 52, 379-382 (1945) · Zbl 0060.08604
[37] Propp, J., Problem proposal 474, Crux Math., 5, 229 (1979)
[38] Roberts, J., Lure of the Integers (1992), Mathematical Association of America
[39] R. Rumely, Notes on van der Poorten’s proof of the Hadamard quotient theorem: Part I, in: Séminaire de Théorie des Nombres, Paris, 1986-1987, Progress in Mathematics, Vol. 75, Birkhäuser, Boston, 1989, pp. 349-382.; R. Rumely, Notes on van der Poorten’s proof of the Hadamard quotient theorem: Part I, in: Séminaire de Théorie des Nombres, Paris, 1986-1987, Progress in Mathematics, Vol. 75, Birkhäuser, Boston, 1989, pp. 349-382.
[40] R. Rumely, Notes on van der Poorten’s proof of the Hadamard quotient theorem: Part II, in: Séminaire de Théorie des Nombres, Paris, 1986-1987, Progress in Mathematics, Vol. 75, Birkhäuser, Boston, 1989, pp. 383-409.; R. Rumely, Notes on van der Poorten’s proof of the Hadamard quotient theorem: Part II, in: Séminaire de Théorie des Nombres, Paris, 1986-1987, Progress in Mathematics, Vol. 75, Birkhäuser, Boston, 1989, pp. 383-409.
[41] O. Salon, Propriétés arithmétiques des automates multidimensionnels, Thèse, Université Bordeaux I, 1989.; O. Salon, Propriétés arithmétiques des automates multidimensionnels, Thèse, Université Bordeaux I, 1989.
[42] J. Shallit, The mathematics of Per \(Nø\); J. Shallit, The mathematics of Per \(Nø\)
[43] Shapiro, D. B., Products of sums of squares, Exposition. Math., 2, 235-261 (1984) · Zbl 0541.10025
[44] N.J.A. Sloane, The on-line encyclopedia of integer sequences, 2002.; N.J.A. Sloane, The on-line encyclopedia of integer sequences, 2002. · Zbl 1274.11001
[45] Sloane, N. J.A.; Plouffe, S., The Encyclopedia of Integer Sequences (1995), Academic Press: Academic Press New York · Zbl 0845.11001
[46] R.G. Stanton, W.L. Kocay, P.H. Dirksen, Computation of a combinatorial function, in: C.St.J.A. Nash-Williams, J. Sheehan (Eds.), Proc. 5th British Combinatorial Conf. (= Congressus Numerantium, Vol. 15), 1975, pp. 569-578.; R.G. Stanton, W.L. Kocay, P.H. Dirksen, Computation of a combinatorial function, in: C.St.J.A. Nash-Williams, J. Sheehan (Eds.), Proc. 5th British Combinatorial Conf. (= Congressus Numerantium, Vol. 15), 1975, pp. 569-578. · Zbl 0335.05008
[47] Stewart, C., Sums of functions of digits, Canad. J. Math., 12, 374-389 (1960) · Zbl 0098.26202
[48] Strauss, N.; Shallit, J., Advanced problem 6625, Amer. Math. Monthly, 97, 252 (1990)
[49] A. Weitzman, Transformation of parallel programs guided by micro-analysis, in: B. Salvy (Ed.), Algorithms Seminar, 1992-1993, Institut National de Recherche en Informatique et en Automatique, France, December 1993, pp. 155-159, Rapport de Recherche, No. 2130.; A. Weitzman, Transformation of parallel programs guided by micro-analysis, in: B. Salvy (Ed.), Algorithms Seminar, 1992-1993, Institut National de Recherche en Informatique et en Automatique, France, December 1993, pp. 155-159, Rapport de Recherche, No. 2130.
[50] A.M. Yaglom, I.M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, Vol. II. Holden-Day, San Francisco, CA, 1967 (Translated by J. McCawley).; A.M. Yaglom, I.M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, Vol. II. Holden-Day, San Francisco, CA, 1967 (Translated by J. McCawley). · Zbl 0147.00102
[51] Zagier, D., Solution to advanced problem 6625, Amer. Math. Monthly, 99, 66-69 (1992)
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.