Stern polynomials - PDF Free Download (2024)

Advances in Applied Mathematics 39 (2007) 86–95 www.elsevier.com/locate/yaama

Stern polynomials ✩ Sandi Klavžar a,c,∗ , Uroš Milutinovi´c a,c , Ciril Petr b,c a Department of Mathematics and Computer Science, PeF, University of Maribor, Koroška cesta 160,

2000 Maribor, Slovenia b Iskratel Telecommunications Systems Ltd., Tržaška 37a, 2000 Maribor, Slovenia c Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia

Received 11 October 2005; accepted 4 January 2006 Available online 24 May 2006

Abstract Stern polynomials Bk (t), k 0, t ∈ R, are introduced in the following way: B0 (t) = 0, B1 (t) = 1, B2n (t) = tBn (t), and B2n+1 (t) = Bn+1 (t) + Bn (t). It is shown that Bn (t) has a simple explicit repre (0) equals the number of 1’s sentation in terms of the hyperbinary representations of n − 1 and that B2n−1 in the standard Gray code for n − 1. It is also proved that the degree of Bn (t) equals the difference between the length and the weight of the non-adjacent form of n. © 2006 Elsevier Inc. All rights reserved. MSC: 11B83 Keywords: Stern (diatomic) sequence; Stern polynomials; Hyperbinary representation; Standard Gray code; Non-adjacent form

1. Introduction Stern sequence [17] or, as it is often called, Stern diatomic series b(n) is defined recursively by b(0) = 0,

b(1) = 1,

✩

Work supported in part by the Ministry of Science of Slovenia and Iskratel Telecommunications Systems Ltd., Slovenia, under the Grant L1-5168-0101-03 and by the Ministry of Science of Slovenia under the Grant P1-0297. * Corresponding author. E-mail address: [emailprotected] (S. Klavžar). 0196-8858/$ – see front matter © 2006 Elsevier Inc. All rights reserved. doi:10.1016/j.aam.2006.01.003

S. Klavžar et al. / Advances in Applied Mathematics 39 (2007) 86–95

b(2n) = b(n),

n 1,

b(2n + 1) = b(n) + b(n + 1),

n 1.

The sequence thus starts as 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, . . . and can, for instance, be obtained as a one-dimensional extract of the so-called Stern–Brocot array. This sequence is A002487 in Sloane’s online database of integer sequences [16]. Stern sequence has been studied in several different fields of mathematics, as a sample of references we propose [9,11,12,15] and a comprehensive survey [18]. The sequence also appears in a very general theory of k-regular sequences due to Allouche and Shallit [1,2]. A nice application of the Stern sequence is given in [4], where Calkin and Wilf prove that the sequence defined by the quotients b(n)/b(n + 1), n 1, encounters every positive rational exactly once. The Calkin and Wilf encoding of positive rationals hence begins as: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 , , , , , , , , , , , , , , , , , , , .... 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 Motivated by the definition of the Stern sequence and the above application we now introduce Stern polynomials Bk (t), k 0, t ∈ R, in the following way. B0 (t) = 0,

B1 (t) = 1,

B2n (t) = tBn (t),

n 1,

B2n+1 (t) = Bn+1 (t) + Bn (t),

n 1.

The first few of them are: B0 (t) = 0, B1 (t) = 1, B2 (t) = t, B3 (t) = t + 1, B4 (t) = t 2 , B5 (t) = 2t + 1, B6 (t) = t 2 + t, B7 (t) = t 2 + t + 1, and B8 (t) = t 3 , see also Table 1. Note that Bn (1) = b(n),

n 0.

(1)

It is also interesting to observe that the sequence of natural numbers can be encoded as Bn (2) = n. Several well-known sequences of polynomials are defined in a way similar to the one in which we define the Stern polynomials. For instance, the Fibonacci polynomials Fn (t) are defined with F0 (t) = 0, F1 (t) = 1, and Fn (t) = tFn−1 (t) + Fn−2 (t), see, for example, [19,20]; for recent results on these polynomials cf. also [7,22]. Another such class is formed by the Lucas polynomials Ln (t) defined with L0 (t) = 2, L1 (t) = t, and Ln (t) = tLn−1 (t) + Ln−2 (t), see [19,21]. Analogously to (1), the Fibonacci numbers and the Lucas numbers are obtained as Fn (1) and Ln (1), respectively. It is interesting to add that Lucas and Fibonacci polynomials have several applications, even in mathematical physics [5]. The main purpose of this paper is to introduce Stern polynomials and to demonstrate that they have many appealing properties. We begin by showing that the polynomial Bn (t) has a simple explicit representation in terms of the hyperbinary representations of n. More precisely, n − 1 Bn (t) = t , 0

S. Klavžar et al. / Advances in Applied Mathematics 39 (2007) 86–95

Table 1 Polynomials Bn (t) obtained from hyperbinary representations of n − 1 n

H(n − 1)

Bn (t) n

(1011)[2] (211)[2]

(1100)[2] (1012)[2] (1020)[2] (212)[2] (220)[2]

(1101)[2] (1021)[2] (221)[2]

(1110)[2] (1102)[2] (1022)[2] (222)[2]

(1111)[2]

t3 + t2

2t 2 + 2t + 1

t3 + t2 + t

t3 + t2 + t + 1

where we use the symbol mk to denote the number of hyperbinary representations of m con taining exactly k digits 1. Then we prove that B2n−1 (0), n 1, equals the number of 1’s in the standard Gray code for n − 1. We conclude the paper by proving that the degree of Bn (t), deg(Bn (t)), equals the difference between the length and the weight of the non-adjacent form of n. 2. Explicit representation of Stern polynomials A hyperbinary representation of a non-negative integer n is a representation of n as a sum of powers of 2, each power being used at mosttwice. We will employ the notation (a1 a2 . . . am )[2] m−i , a ∈ {0, 1, 2}. Let H(n) denote the set to describe the hyperbinary representation m i i=1 ai 2 of all hyperbinary representations (a1 a2 . . . am )[2] of n, where any two representations of the same integer differing only in zeros on the left-hand side are identified. For instance, (1)[2] is the same representation of 1 as (01)[2] . It is well-known, see [4,15], that b(n) counts the number of hyperbinary representations of n − 1. Theorem 1. For any n ∈ N, b(n) = |H(n − 1)|. The idea of the proof for Theorem 1 is that the recursive formulas are established by noting that when n − 1 = (a1 a2 . . . am )[2] is odd, then am must be 1, and if n − 1 is even, am may be 0 or 2, but not 1. This theorem can be extended to the Stern polynomials in the following way. Theorem 2. For any n ∈ N, Bn (t) =

(a1 a2 ...am )[2] ∈H(n−1)

t |{i|ai =1}| .

S. Klavžar et al. / Advances in Applied Mathematics 39 (2007) 86–95

Proof. The assertion is easily verified to be true for small n. Suppose the result is true up to n − 1 for some n. Let n be even, say n = 2k, and consider an arbitrary hyperbinary representation n − 1 = (a1 a2 . . . am )[2] . Since n − 1 is odd, am = 1 by the observation before the theorem. As k − 1 = (a1 a2 . . . am−1 )[2] , the polynomial that counts the number of 1’s in the representation (a1 a2 . . . am )[2] is obtained from the polynomial for (a1 a2 . . . am−1 )[2] by multiplication by t. As B2k (t) = tBk (t), the result holds for n = 2k by the induction hypothesis. Suppose next that n is odd, say 2k + 1. Then n − 1 = (a1 a2 . . . am )[2] is even and am must be 0 or 2. Hence no multiplication by t based on counting the number of 1’s in (a1 a2 . . . am−1 )[2] appears. Now, if am = 0 then (a1 a2 . . . am−1 )[2] is a hyperbinary representation of k, and if am = 2, then (a1 a2 . . . am−1 )[2] is a hyperbinary representation of k − 1. Applying the recursive formula B2k+1 (t) = Bk+1 (t) + Bk (t) one gets the result for n = 2k + 1 by the induction hypothesis. 2 Theorem 2 is illustrated in Table 1 for n 16. Recall that by the symbol mk we denote the number of hyperbinary representations of m containing exactly k digits 1. Then Theorem 2 can be rewritten in the following way. Corollary 3. n − 1 Bn (t) = t . 0

We close this section by the following property of the Stern polynomials. Proposition 4. For any m 0 and any k 1, B2k−1 (2m+1) (t) =

1 B2k m (t) + B2k (m+1) (t) . t

Proof. Compute as follows: 1 1 B k (t) + B2k (m+1) (t) = t k Bm (t) + t k Bm+1 (t) t 2m t = t k−1 Bm (t) + Bm+1 (t) = t k−1 B2m+1 (t) = B2k−1 (2m+1) (t).

3. Stern polynomials and standard Gray code The standard Gray code of n is defined as the binary representation of g(n), where g : N −→ N is defined by g(0) = 0,

g 2p + j = 2 p + g 2 p − 1 − j

for 0 j < 2p ,

(2)

S. Klavžar et al. / Advances in Applied Mathematics 39 (2007) 86–95

Table 2 Standard Gray code g(n)(2) of n and the number of 1’s in it n

g(n)

g(n)(2)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25

00 000 00 001 00 011 00 010 00 110 00 111 00 101 00 100 0 1 100 0 1 101 0 1 111 0 1 110 0 1 010 0 1 011 0 1 001 0 1 000 11000 11001

0 = x(1) 1 = x(2) 2 = x(3) 1 = x(4) 2 = x(5) 3 = x(6) 2 = x(7) 1 = x(8) 2 = x(9) 3 = x(10) 4 = x(11) 3 = x(12) 2 = x(13) 3 = x(14) 2 = x(15) 1 = x(16) 2 = x(17) 3 = x(18)

see [6]. This looks like a complicated definition but the construction of the standard Gray code is simple. The first two words of the code are 0 and 1. Suppose that for some k 1, the first 2k words are already known, where every word is written using k digits. Then the next 2k words of the code are obtained by attaching 1 on the left of each of the first 2k words in the reverse order. See Table 2 where this construction is indicated for k = 4. The principal interest of the Gray code(s) is that the expansions of two consecutive integers differ at only one place. For some algorithmic aspects on the standard Gray code we refer to [10]. In this section we show that certain coefficients of the Stern polynomials are closely related to this Gray code. More precisely, let x(n) be the coefficient at t 1 of the polynomial B2n−1 (t), that is, (0). x(n) = B2n−1

(3)

The first few values of this sequence are shown in Table 2. To establish the connection between the sequence x(n) and the standard Gray code, we need the following auxiliary sequence. For n 0 let y(n) be the coefficient at t 1 of the polynomial B2n (t), that is, (0). y(n) = B2n

(4)

Lemma 5. For any n 0, y(n) = 0, if n is even, and y(n) = 1, if n is odd. (t) = tB (t) + B (t), Proof. It is easily seen that the lemma holds for small n. Then, using B2n n n we get y(2k) = B4k (0) = B2k (0) = 0 · Bk (0) = 0 and y(2k + 1) = B4k+2 (0) = B2k+1 (0) = Bk (0) + Bk+1 (0) = 1. (Here we use that {Bk (0), Bk+1 (0)} = {0, 1} which is easily proved by induction.) 2

S. Klavžar et al. / Advances in Applied Mathematics 39 (2007) 86–95

Lemma 6. For any 0, x(4) = x(2), x(4 + 1) = x(2 + 1), x(4 + 2) = x(2 + 1) + 1, x(4 + 3) = x(2 + 2) + 1. (t) = Bn (t) + Bn+1 (t) we compute as Proof. Applying Lemma 5 and having in mind that B2n+1 follows: (0) = B4−1 (0) + B4 (0) = x(2) + y(2) = x(2), x(4) = B8−1 (0) = B4 (0) + B4+1 (0) = y(2) + x(2 + 1) = x(2 + 1), x(4 + 1) = B8+1 (0) = B4+1 (0) + B4+2 (0) = x(2 + 1) + y(2 + 1) x(4 + 2) = B8+3

= x(2 + 1) + 1,

and

(0) = B4+2 (0) + B4+3 (0) = y(2 + 1) + x(2 + 2) x(4 + 3) = B8+5

= x(2 + 2) + 1.

We now prove that the sequence x(n) satisfies the following recursive formula: Lemma 7. x(1) = 0, x(2k + i) = x(2k − i + 1) + 1, for k 0 and 0 < i 2k . Proof. For k = 0, 1, 2 we easily check that x(2) = x(1) + 1, x(3) = x(2) + 1, x(4) = x(1) + 1, x(5) = x(4) + 1, x(6) = x(3) + 1, x(7) = x(2) + 1, x(8) = x(1) + 1. Suppose k 2. Then, using Lemma 6, we inductively get (for appropriate values of ): x 2k + 4 = x 2k−1 + 2 = x 2k−1 − 2 + 1 + 1 = x 2k − 4 + 1 + 1, x 2k + 4 + 1 = x 2k−1 + 2 + 1 = x 2k−1 − 2 + 1 = x 2k − 4 + 1, x 2k + 4 + 2 = x 2k−1 + 2 + 1 + 1 = x 2k−1 − 2 + 2 = x 2k − 4 − 1 + 1, x 2k + 4 + 3 = x 2k−1 + 2 + 2 + 1 = x 2k−1 − 2 − 1 + 2 = x 2k − 4 − 2 + 1. 2 Now everything is ready for the main result of this section. Theorem 8. For any n 1, x(n) equals the number of 1’s in the standard Gray code for n − 1. Proof. Compare Lemma 7 with (2) and keep in mind that 2p adds an additional digit 1 to the binary representation of the second summand of (2). (Beware of the 1-shift!) 2

S. Klavžar et al. / Advances in Applied Mathematics 39 (2007) 86–95

Corollary 9. The number of 1’s in the standard Gray code for n is the same as the number of hyperbinary representations of 2n containing exactly one digit 1. Proof. By Theorem 8, the number of 1’s in the standard Gray code for n equals x(n + 1), which by definition equals to the coefficient at t 1 of the polynomial B2n+1 (t), i.e. to 2n 1 , by Corollary 3. By definition the symbol is equal to the number of hyperbinary representations of 2n containing exactly one digit 1. 2 The sequence x(n) is A005811 from [16]. It appears under the name of Kuczma’s sequence in [2], where it is proved that x(n) is 2-regular. 4. Stern polynomials and the NAF A signed bit representation of a positive integer is a base 2 representation of the integer in which digits −1, 0, and 1 are allowed. A signed bit representation n = 0im si 2i = sm . . . s0 is called non-adjacent form, NAF for short, if sm = 0 and if si = 0 implies si−1 = 0 for i 1. It is well-known that every positive integer has a unique NAF, see [3,14]. The second column of Table 3 gives the NAFs for positive integers up to 17, where 1¯ stands for −1. NAF proved to be very useful in computer science, especially for fast computations and in coding theory, see [3,8,13]. This is related to the following well-known remarkable property: among all signed bit representations of an integer n, the NAF minimizes the weight, that is, the number of non-zero digits of a representation. This follows from the facts, that the operation of ¯ · · · 001 (as in 1111 = 10001¯ replacing any block of identical non-zero digits by 100 · · · 001¯ or 100 ¯ and 1¯ 1¯ = 101) applied to any signed bit representation does not increase its weight, and that the NAF can be obtained from any signed bit representation in finitely many applications of the replacement operation [3].

Table 3 The NAFs of n and z(n)—the number of 0’s in it n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

z(n) 1 10 101¯ 100 101 ¯ 1010 1001¯ 1000 1001 1010 ¯ 1¯ 1010 ¯ 10100 ¯ 10101 ¯ 10010 10001¯ 10000 10001

0 1 1 2 1 2 2 3 2 2 2 3 2 3 3 4 3

S. Klavžar et al. / Advances in Applied Mathematics 39 (2007) 86–95

The weight of the NAF of n is denoted by w(n). Let in addition the length (n) of the NAF of n be the number of digits in the NAF, that is, if sm . . . s0 is the NAF of n, then (n) = m + 1. Here is the main result of this section. Theorem 10. For any n 1, w(n) = (n) − deg Bn (t) . In the rest of the paper we prove Theorem 10. To shorten the notation set z(n) = deg(Bn (t)). For the proof it suffices to show that z(n) equals the number of zero digits in the NAF of n. From the definition of z(n) it follows that z(0) is not defined and that z(1) = 0, z(2n) = z(n) + 1, z(2n + 1) = max{z(n + 1), z(n)}, for n 1. The first few values of this sequence are presented in Table 3. Lemma 11. For any n > 1, z(n) + 1 max{z(n − 1), z(n + 1)}. Also, z(1) + 1 z(2). Proof. The claim obviously holds for small n. For the induction step we have z(2n + 1) + 1 = max z(n + 1), z(n) + 1 = max z(n + 1) + 1, z(n) + 1 = max z(2n), z(2n + 2) . For the even case we proceed as follows. From z(n + 1) + 1 max{z(n), z(n + 2)} it follows that z(n + 1) + 1 max z(n), z(n + 1), z(n + 2) = max max z(n), z(n + 1) , max z(n + 1), z(n + 2) , and thus z(2n + 2) max{z(2n + 1), z(2n + 3)}. It follows that z(2n + 2) + 1 > max z(2n + 1), z(2n + 3) .

Proposition 12. The sequence z(n), n 1, is defined recursively as follows: z(1) = 0, z(2n) = z(n) + 1, z(4n − 1) = z(n) + 1, z(4n + 1) = z(n) + 1, for n 1. Proof. Using Lemma 11, we get z(4n − 1) = max z(2n − 1), z(2n) = max max z(n − 1), z(n) , z(n) + 1 = z(n) + 1, as well as

S. Klavžar et al. / Advances in Applied Mathematics 39 (2007) 86–95

z(4n + 1) = max z(2n), z(2n + 1) = max z(n) + 1, max z(n), z(n + 1) , = z(n) + 1.

Proposition 12 and the definition of the sequence z(n) immediately imply the following recursive form. Corollary 13. The sequence z(n), n 1, is defined recursively as follows: z(1) = 0, z(2n) = z(n) + 1, z(4n + 1) = z(2n), z(4n + 3) = z(2n + 2), for n 1. From Corollary 13 it follows that z(m), m 1, counts the number of zero digits in the NAF of m. In other words, if m = si 2i is the NAF of m, then the digit s0 is 0 if and only if m is an even number, in which case the remaining digits coincide with the digits of m/2. (This corresponds to z(2n) = z(n) + 1.) In addition, the digit s0 of m = 4n + 1 is 1, and the remaining digits coincide with the digits of 2n. (This corresponds to z(4n + 1) = z(2n).) Finally, the digit s0 of m = 4n + 3 is −1, and the remaining digits coincide with the digits of 2n + 2. (This corresponds to z(4n + 3) = z(2n + 2).) The proof of Theorem 10 is complete. The sequence z(n), n 1, is the sequence A057526 from [16]. Acknowledgments We thank Daniele Parisse for several valuable comments on the manuscript. References [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17]

J.-P. Allouche, J. Shallit, The ring of k-regular sequences, Theoret. Comput. Sci. 98 (1992) 163–197. J.-P. Allouche, J. Shallit, The ring of k-regular sequences, II, Theoret. Comput. Sci. 307 (2003) 3–29. W. Bosma, Signed bits and fast exponentiation, J. Théor. Nombres Bordeaux 13 (2001) 27–41. N. Calkin, H.S. Wilf, Recounting the rationals, Amer. Math. Monthly 107 (2000) 360–363. A. Constandache, A. Das, F. Toppan, Lucas polynomials and a standard Lax representation for the polytropic gas dynamics, Lett. Math. Phys. 60 (2002) 197–209. P. Flajolet, L. Ramshaw, A note on Gray code and odd–even merge, SIAM J. Comput. 9 (1980) 142–158. J. Goldwasser, W. Klostermeyer, H. Ware, Fibonacci polynomials and parity domination in grid graphs, Graphs Combin. 18 (2002) 271–283. D.M. Gordon, A survey of fast exponentiation methods, J. Algorithms 27 (1998) 129–146. A.M. Hinz, S. Klavžar, U. Milutinovi´c, D. Parisse, C. Petr, Metric properties of the Tower of Hanoi graphs and Stern’s diatomic sequence, European J. Combin. 26 (2005) 693–708. D.L. Kreher, D.R. Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search, CRC Press, Boca Raton, 1999. D.H. Lehmer, On Stern’s diatomic series, Amer. Math. Monthly 36 (1929) 59–67. D.A. Lind, An extension of Stern’s diatomic series, Duke Math. J. 36 (1969) 55–60. F. Morain, J. Olivos, Speeding up the computations on an elliptic curve using addition-subtraction chains, RAIRO Inform. Théor. Appl. 24 (1990) 531–543. G.W. Reitwiesner, Binary arithmetic, in: Advances in Computers, vol. 1, Academic Press, New York, 1960, pp. 231– 308. B. Reznick, Some binary partition functions, in: Analytic Number Theory, Allerton Park, IL, 1989, in: Progr. Math., vol. 85, Birkhäuser Boston, Boston, MA, 1990, pp. 451–477. N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, 1996–2005, http://www.research.att.com/~njas/ sequences/. M.A. Stern, Ueber eine zahlentheoretische Funktion, J. Reine Angew. Math. 55 (1858) 193–220.

S. Klavžar et al. / Advances in Applied Mathematics 39 (2007) 86–95

[18] I. Urbiha, Some properties of a function studied by De Rham, Carlitz and Dijkstra and its relation to the (Eisenstein–) Stern’s diatomic sequence, Math. Commun. 6 (2001) 181–198. [19] J. Wang, On the kth derivative sequences of Fibonacci and Lucas polynomials, Fibonacci Quart. 33 (1995) 174–178. [20] E.W. Weisstein, Fibonacci polynomial, From MathWorld—A Wolfram Web Resource, http://mathworld.wolfram. com/FibonacciPolynomial.html. [21] E.W. Weisstein, Lucas polynomial, From MathWorld—A Wolfram Web Resource, http://mathworld.wolfram. com/LucasPolynomial.html. [22] Y. Yuan, W. Zhang, Some identities involving the Fibonacci polynomials, Fibonacci Quart. 40 (2002) 314–318.