Sequences using the floor function |_ z _|: Problem A: [GKP88, Exc. 3.23] and [Knu68, 1.2.4 Exc. 41], [???65] Show that the nth element of the sequence 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ... is x(n) = |_ sqrt(2n) + 1/2 _|. (The sequence contains exactly m occurences of m.) Problem B: Numbering the pairs of nonnegative integer by Cantor's diagonal scheme. 15 . . . . . . 10 14 . . . . . 6 9 13 . . . . 3 5 8 12 . . . 1 2 4 7 11 . . the corner is the point (0,0). At which point is label n? Hint: Use the result of problem A. The spiral numbering of all pair of integers is more cumbersome [GKP88, Exc. 3.40]. . . . . . . . . 12 11 10 9 . . . 13 2 1 8 . . . 14 3 0 7 . . the label 0 is at point (0,0). . 15 4 5 6 . . . 16 17 18 -> . . . . . . . . . Problem C: [BuC86], [GrR88], and more general [DoG84] (EIS sequence A005206) Define a sequence 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14, 14, 15, 16, 16, 17, 17, 18, ... as s(1) = 1 s(n) = n - s(s(n-1)) with n>=1 Show that s(n) = |_ (n+1)/tau _| with tau = (sqrt(5)+1)/2. No simple formular is know for the k-th composition generalization s(n) = n - s(s(...s(n-1))) analyzed in [KiZ92]. Problem C1: [Fin86] The recurrence relation G(n) = n - |_ G(G(n-1)) / r _| with boundary condition G(0) = 0 has the solution G(n)=|_ (n+1) a _| with a is the positive root of a^2 + r a - r = 0. Problem D: [GrP70], related to [GKP88, Exc. 3.46] Considere the sequence 1,2,3,4,6,9,13,19,27,38,54,77,... defined by the recurrence u(1) = 1 and u(n+1) = |_ sqrt(2)*(u(n) + (1/2)) _| for n>=1 Show that u(2n+1) - 2u(2n-1) is just the nth digit in the binary expansion of sqrt(2). Problem E: [Bro78], [GKP88, Exc. 3.28] Solve the recurrence a(0) = 1; a(n) = a(n-1) + |_ sqrt(a(n-1)) _| for n>0 Problem F: [Knu66] Considere the sequence 1,2,4,6,10,14,20,26,36,46,60,74,94,... defined by the recurrence bp(0) = 1 and bp(n) = bp(n-1) + bp( |_ n/2 _| ) for n>0 It count the number of binary partitions (partitions of 2n into powers of 2). Find an asymptotic expansion. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Solution A: First note that 1 + 2 + 3 + ... + m = m(m+1)/2 so the largest n with x(n) = m is m(m+1)/2. Let 0 < eps < 1 then x(n) = m <=> m(m-1)/2 < n <= m(m+1)/2 <=> m(m-1)/2 + eps < n < m(m+1)/2 + eps <=> m^2 - m + 2eps < 2n < m^2 + m + 2eps <=> m^2 - m + 1/4 < 2n - 2eps + 1/4 < m^2 + m + 1/4 <=> m - 1/2 < sqrt(2n + d) < m + 1/2 with -7/4 < d < 1/4 <=> sqrt(2n + d) - 1/2 < m < sqrt(2n + d) + 1/2 with -7/4 < d < 1/4 Hence x(n) is the nearest integer to sqrt(2n). _ _ x(n) = | sqrt(2n + d) - 1/2 | with -7/4 < d <= 1/4 and x(n) = |_sqrt(2n + d) + 1/2 _| with -7/4 <= d < 1/4. Note C: [Hof85] mentions the heap structure ._1 (the parent node of 1 is its left child) |/ \ 2 \ 3 A "Fibonacci Heap" / \ 4 5 / \ \ 6 7 8 / \ \ /\ 9 10 11 12 13 / \ \ / \ / \ \ 14 15 16 17 18 19 20 21 parent node: |_ (n+1)/tau _| left child: |_ tau*n _| right child: |_ tau*(n+1) _| - 1 Fibonacci Number System (Zeckendorf): Let >>_F be the right shift function in the Fibonacci Number System. s(n) = ( (n-1) >>_F 1 ) + 1 Using this "Fibonacci Heap" we can convert an integer into the Fibonacci Number System with the following Mathematica function: fns[n_Integer] := Map[#[[1]] - Floor[GoldenRatio (#[[2]]+1)] + 1 &, Partition[NestWhileList[Floor[(#+2)/GoldenRatio] - 1 &, n, Positive], 2, 1]] The data structure "Fibonacci Heap" of Fredman and Tarjan for a fast shortest path algorithms is unhappily something different. References: Bro78: Thomas C. Brown; Problem E2619: Squares in a recursuve sequence, American Mathematical Monthly 85 (1978) 52-53 BuC86: Robert P. Burton, Douglas M. Campbell; A curious recursive function, Int. J. Comput. Math. 19, No.3/4, 245-257 (1986) Zbl 654.90102 - solves the recurrence: g(n) = n - g(g(n-1)), g(0)=0. DoG84: Peter J. Downey, Ralph E. Griswold; On a Family of Nested Recurrences, Fibonacci Quarterly 22 (1984) 310-317 Zbl 547.10009 - solves the recurrence: g_k(n) = n - g_k(g_k(n-k)) with g_k(n)=0 for n <= 0 for a fixed positive integer k. g_k(n) = Sum_{i=0..k-1} [([(n+i)/k]+1)/tau] Fin86: N.J. Fine; An iterative recurrence formula. J. Math. Anal. Appl. 113, 185-187 (1986) Zbl 596.10011 The recurrence relation $G(n)=n-[(1/r)G(G(n-1))]$ with boundary condition $G(0)=0$ is shown to have the solution $G(n)=[(n+1)a]$ where a is the positive root of $a\sp 2+ra-r=0$. The case $r=1$ is mentioned on page 137 of ''Goedel, Escher, Bach'' (Basic Books, New York 1979; Penguin Books 1981; Zbl 457.03001) by {\it D. R. Hofstadter}. GaC88: D. Gault and M. Clint; "Curiouser and curiouser" said Alice. Further reflections on an interesting recursive function, Internat. J. Computer Math., 26 (1988), 35-43. Zbl 686.68012 GKH77: H. W. Gould, J. B. Kim and V. E. Hoggatt, Jr.; Sequences associated with t-ary coding of Fibonacci's rabbits, Fibonacci Quarterly 15 (1977), 311-318. GKP88: Ronald L. Graham, Donald E. Knuth, Oren Pataschnik; Concrete Mathematics, Addison Wessley, Reading (1994) 2nd Ed. Chap 3: Integer Functions Sect 3.1: Floors and Ceilings Sect 3.2: Floor/Ceiling Applications Sect 3.3: Floor/Ceiling Recurrences Sect 3.4: Mod: the Binary Operation Sect 3.5: Floor/Ceiling Sums GrP70: R. L. Graham, H. O. Pollak; Note on a nonlinear recurrence related to sqrt(2), Mathematics Magazine: Volume 43, Number ?, Pages: 143-145, 1970 Zbl 201.04705 In this note an elementary proof of the following result is given: Theorem i. For a fixed positive integer m, define the integer sequence a_n by: a_1 = m and a_{n+1} = \lfloor sqrt{2*a_n*(a_n + 1)} \rfloor, n \geq 1. Then a_n is given explicitly by a_n = \lfloor tau_m (2^{(n-1)/2} + 2^{(n-2)/2}) \rfloor where tau_m is the m-th smallest element of the set \{1, 2, 3, ... \} \cup \{ sqrt{2}, 2sqrt{2}, 3sqrt{2}, ... \}. For m=1 it follows as a curious corollary that a_{2n+1} - 2a_{2n-1} is exactly the n-th digit in the base 2 expansion of sqrt{2}. GrR88: Vincent Granville, Jean Paul Rasson; A Strange Recursive Relation, Journal of Number Theory 30 (1988) 238-241 - solves the recurrence: g(n) = n - g(g(n-1)), g(0)=0. Hof85: Hofstadter; Bach, Escher, G\"odel, Intereditions, 1985 - p151-154 (Fibonacci Numbers) the recurrence: g(n) = n - g(g(n-1)), g(1)=1, and the heap structure KiZ92: Peter Kiss, Bela Zay; On a Generalization of a Recursive Sequence, Fibonacci Quarterly 30:2 (May 1992) 103-109 Zbl 751.11011 Knu66: Donald E. Knuth; An almost linear recurrence, Fibonacci Quarterly 4 (1966) 117-128 Knu68: Donald E. Knuth; The Art of Computer Programming Vol. 1, Fundamental Algorithms, Addison Wessley, Reading (1973) 2nd Ed. Chap. 1.2.4: Integer Functions and Elementary Number Theory RaG91: Stanley Rabinowitz and Peter Gilbert; A Nonlinear Recurrence Yielding Binary Digits, Mathematics Magazine: Volume 64, Number 3, Pages: 168-171, 1991 First Paragraph: Graham and Pollak considered the sequence 1,2,3,4,6,9,13,19,27,38,54,77,... defined by the recurrence u_1=1, u_{n+1} = \lfloor sqrt{2}*(u_n+(1/2)) \rfloor, n \geq 1, where \lfloor x \rfloor denotes the floor of x, the largest integer not larger than x. They discovered the unusual property that u_{2n+1} - 2u_{2n-1} is just the nth digit in the binary expansion of sqrt{2}. In discussing this result, Erd\Hos and Graham say, "It seems clear that there must be similar results for sqrt{m} and other algebraic numbers, but we have no idea what they are." In this paper, we give a generalization of this result and obtain a recurrence relation that yields, in a similar manner, the nth digit in the binary expansion of any positive real number. Reviewer: Nathan Jakubiak ???65: Cantor diagonal procedure, Mathematics Magazine 38 (1965) 185-187 (problem A) x(n) = |_ (1 + |_sqrt(8n-7)_|)/2 _| -- mailto:Torsten.Sillke@uni-bielefeld.de http://www.mathematik.uni-bielefeld.de/~sillke/