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/