From and.Princeton.EDU!conway Sat Nov 23 13:59 EST 1996
Return-Path:
Date: Sat, 23 Nov 1996 13:43:37 -0500 (EST)
From: John Conway
Subject: Re: parFibs.
To: njas@research.att.com
In-Reply-To: <199611221536.KAA28194@and.Princeton.EDU>
Will you please put the name "para-Fibonacci sequence"
in the entry for my version? Correspondingly, perhaps
something like "Fibonacci paraphrase" should be in Kimberling's.
I've been continuing my study of these matters, and thinking
about the terminology, the most important new pieces of which are
the word "parameter" for the index of a sequence, and (Fibonacci)
"successor" for the number Sn you get from a given n by bumping
up all terms of its Zeckendorff expansion. Thus the sequence
with parameter i can be started from
i 1+Si
and after that has the shape
j Sj SSj SSSj SSSSj ...
where j = i + 1 + Si.
On Fri, 22 Nov 1996 njas@research.att.com wrote:
> >From njas Fri Nov 22 10:31 EST 1996
> To: ck6@cedar.evansville.edu
> Cc: njas@research.att.com
> Status: R
>
> hi! some time ago you sent me a paper with the following sequence in it:
>
> %I A003603 M0138
> %S A003603 1,1,1,2,1,3,2,1,4,3,2,5,1,6,4,3,7,2,8,5,1,9,6,4,10,3,11,7,2,12,8,5,13,1,
> %T A003603 14,9,6,15,4,16,10,3,17,11,7,18,2,19,12,8,20,5,21,13,1,22,14,9,23,6,24
> %N A003603 Fractal sequence obtained from Fibonacci numbers.
> %R A003603 Kimb94a.
> %O A003603 0,4
From and.Princeton.EDU!conway Sun Nov 24 15:41 EST 1996
Return-Path:
Date: Sun, 24 Nov 1996 15:13:11 -0500 (EST)
From: John Conway
Subject: Re: your mail
To: njas@research.att.com
In-Reply-To: <199611240009.TAA17271@and.Princeton.EDU>
On Sat, 23 Nov 1996 njas@research.att.com wrote:
> its 7pm saturday, can you give me a call?
I've been thinking further about Fibs and Buds.
1) numeration: It seems to me that the columns of Kimberling's
array should be numbered as in:-
-1 0| 1 2 3 4 5
--------------------
0 1| 1 2 3 5 8
1 3| 4 7 11 18 29
2 4| 6 10 16
3 6| 9 15
4 8|12 20
5 9|14 23
and that the row with parameter i should be called the
ith extra Fibonacci (or extra-Fibonacci) sequence, the numbers
after the bar being the ith extraFib numbers. Idea - these
sequences (for i > 0) are indeed "extra" Fibonacci sequences,
and their terms (after the bar) are "extra-Fibonacci" - that is,
outside the Fibonacci sequence.
Now I want to point out the relationship with the budding sequences.
The table shows n followed by the nth terms of the paraFib sequence Pn
and the Left and Right budding sequences Ln and Rn:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Pn 0 0 0 1 0 2 1 0 3 2 1 4 0 5 3 2 6 1 7 4 0 8 5 3
Ln 1 1 3 2 1 5 3 8 5 2 9 5 1 10 5 15 9 3 15 8 21 13 5 20
Rn 1 2 1 3 5 2 5 1 5 9 3 8 13 5 11 2 9 16 5 13 1 10 19 5
Xn 1 1 1 3 1 2 3 1 5 2 3 8 1 5 5 2 9 3 5 8 1 10 5 5
The number Xn is Ln or Rn if Pn is occurring for the kth time and
k is respectively odd or even, and you see that Xn is a function of Pn,
namely
Xn = 1 3 2 5 8 5 9 5 10 15 9 15 21 13 20 ... (***)
for Pn = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
I found a recursion for this sequence (***), but am scared of writing it
down wrongly, so will stop for now. It's easy to see that each of the
budding sequences Ln and Rn consists of the values of (***) repeated
in finitely often in a certain way.
J
WYTHOFF ARRAY
From cs.arizona.edu!rcs Mon Nov 25 16:29 EST 1996
Date: Mon, 25 Nov 1996 14:20:11 MST
From: "Richard Schroeppel"
To: math-fun@cs.arizona.edu
Subject: Fibonacci note from Conway
This came up on another list. I think it's of more interest here on Math-Fun.
My apologies to the common membership for a double-post. --Rich
----------------------
From: John Conway
Subject: Re: Fibonacci correction from Achim
Date: Mon, 25 Nov 1996 12:51:57 -0500 (EST)
This mention of Fibonacci counting prompts me to pass
on something about the Fibonacci's that very much excited
me when I found it about a week ago. I've since learned
that Clark Kimberling found the essential point about 20
years ago.
I start with the Zeckendorff expansion of a positive integer,
obtained by repeatedly subtracting the largest Fibonacci number
you can until nothing remains, for example
100 = 89 + 8 + 3.
By replacing each Fib in the Zeckendorff expansion of n,
you get what I'll call the Fibonacci successor Sn, eg.:
S100 = 144 + 13 + 5 = 162.
Now the positive integers are linked by this function into
an infinity of sequences each satisfying the Fibonacci recursion,
namely those after the bar in the table below, which covers all
numbers below 100:
0 1| 1 2 3 5 8 13 21 34 55 89
1 3| 4 7 11 18 29 47 76
2 4| 6 10 16 26 42 68
3 6| 9 15 24 39 63
4 8|12 20 32 52 84
5 9|14 23 37 60 97
6 11|17 28 45 73
7 12|19 31 50 81
8 14|22 36 58 94
9 16|25 41 66
10 17|27 44 71
11 19|30 49 79
12 21|33 54 87
13 22|35 57 92
14 24|38 62
15 25|40 65
16 27|43 70
17 29|46 75
18 30|48 78
19 32|51 83
20 33|53 86
21 35|56 91
22 37|59 96
23 38|61 99
24 40|64
25 42|67
26 43|69
27 45|72
28 46|74
29 48|77
30 50|80
31 51|82
32 53|85
33 55|88
34 56|90
35 58|93
36 59|95
37 61|98
38 63|
The topmost series is the Fibonacci series itself: I call the n'th
one beneath it the n'th extra Fibonacci sequence. It occurs to me that
"n'th higher Fibonacci sequence" might be better. The 0'th higher
Fib sequence is of course the Fib sequence itself.
Of course each of these sequences can be continued indefinitely far
to the left, and I continued them two places left in the table, because
then, as you can see, the leftmost column contains the parameter n
just defined.
It's a very nice fact that EVERY sequence that satisfies the
Fibonacci recurrence and ends up with positive integers is one of
this neatly-parameterized family. This leads us to what I call
the "para-Fibonacci sequence), which for every positive integer
gives the parameter of the Fib-sequence that contains that integer
(after the bar):
(A019586)
0 0 0 1 0 2 1 0 3 2 1 4 0 5 3 2 6 1 7 4 0 8 5 3 9 2 10 6 1 11 7 4 12 0 13
0,0,0,1,0,2,1,0,3,2,1,4,0,5,3,2,6,1,7,4,0,8,5,3,9,2,10,6,1,11,7,4,12,0,13
Kimberling called the sequence whose terms are 1 larger than these
"the paraphrase of the Fibonnaci numeration system". (A003603)
This (A019586) has very nice properties - for example between any two 0's
we see a permutation of the first few positive integers, and these
nest, so we can read the paraFib sequence from:
0
0
0 1
0 2 1
0 3 2 1 4
0 5 3 2 6 1 7 4
0 8 5 3 9 2 10 6 1 11 7 4 12
Also - if you delete the first occurrence of each number [from A019586], the
sequence is unchanged.
There are many intriguing problems here, of which I'll mention
just two:
1) Reading the nth sequence backwards, we obtain the negative
of another. Which?
2) Multiplying the terms of the nth sequence by some positive
integer d, we obtain those of another. Which? (The reason I
prefer my version to Kimberling's is that the answer to this
must be some multiple of d.)
I only just thought of 1). About 2) I note that multiplying
the Fib sequence by 2,3,4, 5, 6, 7, 8, 9,10,11 we get sequences
numbers 2,3,4,15,18,21,24,27,30,33, A269725
and that the double of the 7th sequence comes before that of the 5th.
I have long been interested in what I call the "budding sequences",
which tell you where the successive buds on suitable kinds of plant
are located. The paraFib sequence helps to explain many properties
of these, and shows that they each consist of the terms of the rather
mysterious sequence
1, 3, 2, 5, 8, 5, 9, 5, 10, 15, 9, 15, 21, 13, 20, ...
repeated infinitely often in systematic ways. However, to explain
these matters here would take me as much time again, and I want to
have some lunch now!
John Conway
From and.Princeton.EDU!conway Mon Dec 2 17:02 EST 1996
Return-Path:
Date: Mon, 2 Dec 1996 15:52:17 -0500 (EST)
From: John Conway
Subject: Fibs and postFibs
To: Allan Wechsler
Cc: math-fun@cs.arizona.edu
[For new readers: this is about a remarkable parametrization of
all the sequences of integers satisfying the Fibonacci recurrence
and tending to infinity. To be precise, the ith "post-Fibonacci
sequence" Fi has i and S(i) + 1, where to get S(i) you express i
as a sum of minimally many Fibonacci numbers, and then replace each
of these by the next higher one. For instance, 10 = 8+2, and
so S(10) = 13+3 = 16, and so the 10th postFib sequence F10 is
... 11, -6, 5, -1, 4, 3, 7, 10, 17, 27 44, 71, 115, 186, ...
^^^^^^
obtained from the underlined terms 10, S(10)+1. I raised two
questions:
1) For any m, we obtain a postFib sequence by multiplying Fi
by m. What is the rule governing the parameters of these?
Thus on multiplying the standard Fib sequence F0 by
1 2 3 4 5 6 7 8 9 10 11 12 13
we get
F0, F2, F3, F4, F15, F18, F21, F24, F27, F30, F33, F96, F104,...
and in a similar way we get
F1 F8 F12 F44 F55 F66 F77 F88 F261 F290 F319 F348 F377
1,8,12,44,55,66,77,88,261,290,319,348,377 A269726.
from the Lucas sequence F1.
2) If we reverse Fi and negate alternate terms we again
get some postFib sequence Fj. How does j relate to i?]
Now read on:
About the sequence mFi = FM. In the two examples, we see that
M is always a multiple of m, namely M/m =
0 1 1 1 3 3 3 3 3 3 3 8 8 ...
for the Fib sequence, and
1 4 4 11 11 11 11 11 29 29 29 29 29 ...
for the Lucas sequence. More generally, we can prove that in
general when we write mFi = FM, for some M = M(i,m), then
always M/m will be a member of the Fi sequence, that only
alternate terms of the Fi sequence are so used, and that M/m
stays constant for longer and longer stretches.
This follows by thinking about the diagram whose (x,y)
entry is the parameter of the postFib sequence defined by the
two consecutive terms x, y :-
>88
>77
>66
0 5 10 15 20/ 9 11 13 15/ 6 7/(0) 5/15 16 17/49 52>55 58 61 64 67/
2 7/ 4 6 8 10/ 4 5/ 2( 1) 4/13 14/41>44 47 50 53 56 59/
1 3 5 7/ 3/ 1( 0) 3/10 11>12/36 39 42 45 48 51/
5,8 0 2/ 1 2/(0) 2/ 7 >8 9/28 31 34 37 40 43 46/
0/ 0( 0)>1/ 5 6/20 23 26 29 32 35 38/
2,3 (*) 0/ 2 3 4/15 18 21 24 27 30 33/96
0 1/ 7 10 13 16 19 22 25/75 83 91 99
1,1 2 5 8 11 14 17/54 62 70
1,0 0 3 6 9 12/41 49 57 65 73
0,1 1 4/20 28 36 44 52 60
1,2 7 15 23 31 39 47
2 10 18 26 34
3,5 5 13 21
0 8
8,13
I've drawn "straight" lines to indicate various strips,
in each of which the entry takes a fixed form ax+by, and
have indicated the values (a,b) beneath these. Since it can
be hard to see which /'s belong to which lines, the central
"lane" is indicated instead by brackets.
The entire picture is invariant under squashing by a factor
of tau = (1+root5)/2 in the (1,tau) direction and simultaneously
expanding by a factor of -tau in the orthogonal (-tau,1) direction.
Each strip except the central one, which I'm therefore calling a lane
rather than a strip, has one copy of each natural number 0,1,2,3,...,
these being entered according to their distance from the boundary
line y = -x/tau. I forgot to say that (*) marks the origin.
To see how this implies the statements, consider the multiples
of (for example) the vector (2,1). I've picked out the corresponding
entries with > marks, which march by knight's moves rightwards
across the successive strips. You'll see that for the two values
m = 2 and m = 3 these land in the (1,2) strip, yielding F8 and
F12 for the 2nd and 3rd multiples of F1, but then that the next five
are in the (3,5) strip, yielding F44, F55, F66, F77, F88, after
which we land for quite same time in the (8,13) strip, yielding
various FM for M/m = 29, and so on.
That's all for now. I hope someone can understand it!
Forthcoming attraction: we explain why the sequence
0,1,2,3,4,7,10,5,8,11,6,9,12,20,28,15,23,31,,,
that gives the parameter values for reversed Fib sequences,
has differences
1,1,1,1,3,3,-5,3,3,-5,3,3,8,8,-13,8,8,-13,...
that are all Fibonacci numbers (up to sign).
John Conway
From spork.bbn.com!awechsle Wed Dec 4 16:44 EST 1996
Date: Wed, 4 Dec 1996 16:31:27 -0500 (EST)
From: Allan Wechsler
Here are some thoughts on generalized Fibonacci sequences.
Consider the field Q[phi]. Since phi is irrational, any element
p + q phi is uniquely determined by p and q.
Now consider the function K(x) = phi x. If x = p + q phi, then
K(x) = p phi + q phi^2 = q + (p+q) phi.
In other words, multiplying by phi performs the Fibonacci transform on
p and q. (This is where our intuition comes from, that stepping down
the Fibonacci sequence is "like" multiplying by phi.)
Now consider the function J : Q[phi] -> Q defined by
J(p + q phi) = pp + pq - qq [= p^2 +p*q - q^2]
A little arithmetic reveals that
J(K(x)) = -J(x).
Intuitively, every generalized Fibonacci sequence rides a "J track",
with |J| fixed. The classical Fibonacci sequence has |J| = 1. Its
multiples have |J| in {1, 4, 9, 16, 25, ...}. The Lukas sequence has
|J| = 5.
It would be nice if |J| _characterized_ a given sequence.
Unfortunately, this is not the case. Even among integer sequences,
the 3, 1, 4, 5, 9, ... and 3, 2, 5, 7, 12 ... share |J| = 11.
It is interesting that J preserves multiplication, that is, that J(xy)
= J(x)J(y).
I don't have any real sense for how Conway's parameterization of
Fibonacci sequences relates to J. Here is a brief table of the J's
for the first few Fi's.
n |J(Fn)|
0 1
1 5
2 4
3 9
4 16
5 11
6 19
7 11
8 20
9 31
10 19
11 31
12 45
13 29
14 44
15 25
16 41
17 59
18 36
19 55
Notice the multiplicative relationship: F1.F5=F19.
-A
From well.com!mlb Wed Jan 8 20:44 EST 1997
Date: Wed, 08 Jan 1997 17:32:45 -0800
To: John Conway
From: Marc Le Brun
Subject: Re: Fibs
Cc: math-fun@cs.arizona.edu
> Sorry I've been away for so long. I like your comments below,
>which effectively replace a fixed Fib sequence with a number
>from the "Golden ring", multiplied by all units, if we identify
>a sequence with its negative. So (in this new sense) the Fib
>sequences correspond one for one with Golden integers modulo
>units. However, there is another way to parametrize these,
>namely by choosing "the simplest" totally positive unit. I must
>think about the relation between this way and "my" (really
>Kimberling's) way. JHC
Multiples of the sequences are a sub-case of adding sequences, so perhaps it
might make sense to look at their "addition table"?
But note that there are really two parameters that describe the result of
such an addition: the Kimberling index of the sum, and also the amount by
which the sum sequence is shifted. That is, K0+K1 (ie Fibbonacci + Lukas)
is K5, but it's shifted over 2 places from its "index position"--that is,
K0[n]+K1[n]=K5[n-2].
So to fully describe additions, we would want to account for the index and
shift of both sums and summands: Ix,Sx + Iy,Sy = Iz,Sz.
(I've been meaning to compute and post tables of these I and S values ever
since this thread appeared, but the process keeps producing new sequences I
feel compelled to send to superseeker! I'll try to do it Real Soon...)
Anyway, if we use pairs to desribe these sequences, there are of course a
lot of alternatives to the "standard" registration. For example, I think
another pretty property is that every a,b appears just once. So we could,
for example, instead "register" them by lining up each Ki on the smallest
pairs such that 0<=Ki[n]<=Ki[n+1]. Question: can we somehow describe the
shift distance between this "least positive pair" and the Kimberling index?
Whatever, we might want to restate the problem as that of characterizing a
relationship between I,S pairs and a,b pairs in such a way that we can
describe the I,S of sums a+c,b+d.
From well.com!mlb Fri Jan 10 19:15 EST 1997
Date: Fri, 10 Jan 1997 16:01:59 -0800
To: math-fun@cs.arizona.edu
From: Marc Le Brun
Subject: kim-sum
Here's the "Kimberling sum" addition table from K0+K0 up to K25+K25 (with
row and column labels) It also seems that the shift is ALWAYS by 2 places
(I'm not sure why I thought it varied).
Kim+ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25
0 2 5 7 10 13 15 18 20 23 26 28 31 34 36 39 41 44 47
49 52 54 57 60 62 65 68
1 5 8 10 13 16 18 21 23 26 29 31 34 37 39 42 44 47 50
52 55 57 60 63 65 68 71
2 7 10 4 15 18 20 23 9 28 31 12 36 39 41 44 17 49 52
54 57 22 62 65 25 70 73
3 10 13 15 18 21 23 26 28 31 34 36 39 42 44 47 49 52 55
57 60 62 65 68 70 73 76
4 13 16 18 21 24 26 29 31 34 37 39 42 45 47 50 52 55 58
60 63 65 68 71 73 76 79
5 15 18 20 23 26 28 31 12 36 39 41 44 47 49 52 54 57 60
62 65 25 70 73 75 78 81
6 18 21 23 26 29 31 34 36 39 42 44 47 50 52 55 57 60 63
65 68 70 73 76 78 81 84
7 20 23 9 28 31 12 36 14 41 44 17 49 52 54 57 22 62 65
25 70 27 75 78 30 83 86
8 23 26 28 31 34 36 39 41 44 47 49 52 55 57 60 62 65 68
70 73 75 78 81 83 86 89
9 26 29 31 34 37 39 42 44 47 50 52 55 58 60 63 65 68 71
73 76 78 81 84 86 89 92
10 28 31 12 36 39 41 44 17 49 52 54 57 60 62 65 25 70 73
75 78 30 83 86 33 91 94
11 31 34 36 39 42 44 47 49 52 55 57 60 63 65 68 70 73 76
78 81 83 86 89 91 94 97
12 34 37 39 42 45 47 50 52 55 58 60 63 66 68 71 73 76 79
81 84 86 89 92 94 97 100
13 36 39 41 44 47 49 52 54 57 60 62 65 68 70 73 75 78 81
83 86 33 91 94 96 99 102
14 39 42 44 47 50 52 55 57 60 63 65 68 71 73 76 78 81 84
86 89 91 94 97 99 102 105
15 41 44 17 49 52 54 57 22 62 65 25 70 73 75 78 30 83 86
33 91 35 96 99 38 104 107
16 44 47 49 52 55 57 60 62 65 68 70 73 76 78 81 83 86 89
91 94 96 99 102 104 107 110
17 47 50 52 55 58 60 63 65 68 71 73 76 79 81 84 86 89 92
94 97 99 102 105 107 110 113
18 49 52 54 57 60 62 65 25 70 73 75 78 81 83 86 33 91 94
96 99 38 104 107 109 112 115
19 52 55 57 60 63 65 68 70 73 76 78 81 84 86 89 91 94 97
99 102 104 107 110 112 115 118
20 54 57 22 62 65 25 70 27 75 78 30 83 86 33 91 35 96 99
38 104 40 109 112 43 117 120
21 57 60 62 65 68 70 73 75 78 81 83 86 89 91 94 96 99 102
104 107 109 112 115 117 120 123
22 60 63 65 68 71 73 76 78 81 84 86 89 92 94 97 99 102 105
107 110 112 115 118 120 123 126
23 62 65 25 70 73 75 78 30 83 86 33 91 94 96 99 38 104 107
109 112 43 117 120 46 125 128
24 65 68 70 73 76 78 81 83 86 89 91 94 97 99 102 104 107 110
112 115 117 120 123 125 128 131
25 68 71 73 76 79 81 84 86 89 92 94 97 100 102 105 107 110 113
115 118 120 123 126 128 131 134
From well.com!mlb Wed Jan 15 12:23 EST 1997
Date: Wed, 15 Jan 1997 08:58:32 -0800
To: math-fun@cs.arizona.edu
From: Marc Le Brun
Subject: More about Kimberling sums
This is a consolidated report on some stuff I and others
(eg ACW, NJAS et al) have observed about the interesting
Fibonaccioid recurrences JHC introduced us to back on 25 Nov 96.
Definitions:
Let Kn be the n-th Kimberling sequence, defined by
Kn[0] = n
Kn[1] = An
Kn[i] = Kn[i-1] + Kn[i-2]
for all non-negative integers n and all integers i, where
An = floor[(n+1)*tau].
Also, let KnSs be the n-th Kimberling sequence shifted by the integer s,
that is, KnSs[i] = Kn[i-s] (thus (the unshifted) Kn is KnS0 etc).
(K0[i] is the Fibbonacci numbers, K1[i] is the Lukas sequence, Kn[1]=An,
Kn[2] is the "odd Fibbinary" ie Zeckendorf expansions with ...+F1=...+1 etc).
Specifics:
I swipe JHC's tableaux, decorating and shortening it a little, extending
it to the left, and retaining the "bar" between Kn[1] and Kn[2]:
i ...-2 -1 0 1 2 3 4 5 6 7 8 9 10 11 ...
Kn: n: An: * * * * * ...
K0 ... 0 1| 1 2 3 5 8 13 21 34 55 89 ...
K1 ... 1 3| 4 7 11 18 29 47 76 ...
K2 ... 0 2 2 4| 6 10 16 26 42 68 ...
K3 ... 0 3 3 6| 9 15 24 39 63 ...
K4 ... 0 4 4 8|12 20 32 52 84 ...
K5 ... 1 4 5 9|14 23 37 60 97 ...
K6 ... 1 5 6 11|17 28 45 73 ...
K7 ... 2 5 7 12|19 31 50 81 ...
K8 ... 2 6 8 14|22 36 58 94 ...
K9 ... 2 7 9 16|25 41 66 ...
K10 ... 3 7 10 17|27 44 71 ...
K11 ... 3 8 11 19|30 49 79 ...
K12 ... 3 9 12 21|33 54 87 ...
K13 ... 4 9 13 22|35 57 92 ...
K14 ... 4 10 14 24|38 62 ...
K15 ... 5 10 15 25|40 65 ...
K16 ... 5 11 16 27|43 70 ...
K17 ... 5 12 17 29|46 75 ...
K18 ... 6 12 18 30|48 78 ...
K19 ... 6 13 19 32|51 83 ...
K20 ... 7 13 20 33|53 86 ...
K21 ... 7 14 21 35|56 91 ...
K22 ... 7 15 22 37|59 96 ...
K23 ... 8 15 23 38|61 99 ...
K24 ... 8 16 24 40|64 ...
K25 ... 8 17 25 42|67 ...
K26 ... 9 17 26 43|69 ...
...
(Warning: error-prone, manually transcribed!)
Kimberling Sum:
As a baby step towards understanding things like scaling (ie m*KnS0=KpSs),
we construct Kimbering sum sequences of unshifted summands Kp+Kq=KrSs, and
attempt to characterize r,s in terms of p,q.
Conjecture:
Usually,
r = p + q + Ap + Aq
s = 2
but in certain exceptional cases (defined below)
r = p + q
s = 0.
(Apology: I recently wrongly implied that there weren't exceptions--sorry!)
Exceptions:
Let Zn = An + n + 1 = 2, 5, 7, 10, 13, 18, 20, 23,...
(Z may connote the opposite of A, zero shift, or Zeckendorf).
* The exceptions are when BOTH p and q ARE in Zn, BUT p+q is NOT in Zn.
(Thus K2+K2=K4S0 *is* an exception, because 2+2=4 *isn't* in Zn,
but K2+K5=K20S2 *isn't* an exception, because 2+5=7 *is* in Zn).
Caveat:
One might assume that the scalar multiple m*Kn is determined by the
foregoing, but we've only treated the case where the summands are
unshifted. However a sum is *usually* shifted, so iterating an
incrementation needs to address shifting... These cases aren't
covered by the conjecture here!
Fun things to find or prove:
* That the definition of An implies that every positive integer appears
"to the right of the bar" exactly once (that is, An as defined really
does generate the Kimberling sequences!)
* The conjecture above.
* The general case where the summand's relative shift is non-zero.
* That Zn is the union of the starred columns (ie Zn = U Kn[2*i+1], i>0)
From AIC.NRL.Navy.Mil!hoey Thu Jan 16 19:08 EST 1997
Return-Path:
Date: Thu, 16 Jan 97 18:54:27 EST
From: Dan Hoey
To: math-fun@cs.arizona.edu
Subject: Re: More about Kimberling sums
Marc Le Brun summarized the directions in which he,
ACW, NJAS, have been Kimberled:
> Let Kn be the n-th Kimberling sequence, defined by
> Kn[0] = n
> Kn[1] = An
> Kn[i] = Kn[i-1] + Kn[i-2]
> for all non-negative integers n and all integers i, where
> An = floor[(n+1)*tau].
Thank you thank you! I was hoping for a closed-form expression for
Kn[1]--John uses methods that seem to require looking over the earlier
sequences for missing elements.
> Let Zn = An + n + 1 = 2, 5, 7, 10, 13, 18, 20, 23,...
> (Z may connote the opposite of A, zero shift, or Zeckendorf).
Zn seems to be just those n for which (n+1)tau - An < 1/tau--i.e.
(n+1)tau mod 1 is less than 1/tau. Now I'd think it should be
possible to show why A[p+q] = Ap + Aq exactly when p,q but not p+q are
in Zn, and otherwise A[p + q + Ap + Aq] = p + q + 2Ap + 2Aq, which
would yield the conjecture. But I'm not getting anywhere with it.
Allan's J function easy to calculate here, too. He wrote
J(p + q phi) = pp + pq - qq
but did you notice
J(p + q phi) = (p + q phi)(p - q/phi).
The latter may interact better with the closed form for An. Allan
mentioned that J(F5)=J(F7)=11, and somehow I hoped that was some sort
of pairing instead of an arbitrary multiplicity. Unfortunately
J(F33)=J(F45)=J(F65)=121, and 6061 is the J of sequences 1860, 1941,
2171, 2388, 2932, 3225, 3607, and 3764. There are more examples of
all multiplicities up to 8 among the first 10000 sequences.
Dan
Hoey@AIC.NRL.Navy.Mil
From well.com!mlb Thu Jan 16 22:48 EST 1997
Date: Thu, 16 Jan 1997 19:33:30 -0800
To: John Conway
From: Marc Le Brun
Subject: Re: More about Kimberling sums
Cc: math-fun@cs.arizona.edu
> I'm sorry, I thought I'd given the closed forms for
>the general "Kimberling sequence". I certainly knew them.
(I've hoped that if I sent junk mail long enough it would provoke you into
divulging such secrets! <;-)
>but may I say that I still prefer my name "(higher) Fibonacci
>sequence", because it's more likely to suggest the meaning,
>and because these sequences have long been called the "other"
>Fibonacci sequences.
I'm easy (as long as the name doesn't include parentheses!). I'd also like
to settle on a symbol to use for the n-th sequence, and Fn is already taken
for the n-th term of the 0-th sequence (ie the "vanilla" Fibonaccis).
OK, let's call them the Higher Fibonaccis and use Hn[k] to mean the k-th
term of the n-th sequence.
>really GREAT sequence that Kimberling found is his "parafibonacci"
>sequence. This is my name, intended to recall the fact that it gives
>the parameter of the appropriate (higher) Fib sequence.
Yes! But I (and maybe others) have wanted to get sufficient understanding
of the HFs before moving on to the later stuff in your message, such as "Pn".
This may all be obvious, but it sure felt like you pulled a rabbit out of a
hat! You constructed the HFs by crafting sequences to cover the integers,
took them two steps backwards and... Fibonacadabra! there's the parameter!
> I think I defined the Fibonacci inflation function n+ by
>pumping up the terms in Zeckendorff's expansion as a sum of
>Fib numbers? You can also define it by multiplying n by
>the golden number tau (= phi) and then rounding this
>"goldenly" (you should be able to work out what this means).
Right, generating the stuff "after the bar" is pretty straightforward.
>The two terms "before" the n'th fib sequence are n and 1 + n+,
>from which you can work out the general term.
Also. What is only slowly becoming clear is *why* this is so. That is, why
should exactly this choice of the term after the parameter result in this
tidy covering of the integers? I'm groping towards something expressed via
Beatty sequences, but I'm certainly not there yet. Do you have a nice
explanation (or could you pass on Kimberling's?)
Note that, in Zeckendorfland, the way to get the first two terms right after
the parameter is a different construction than just the inflating that you
do from then on. And, in fact, while there *may* be a "construction" that
takes you further to the *left* of the parameter, there's clearly no inverse
to take you back to the parameter, because you start to get repeated values
in those columns.
> When I saw the conjecture about adding these sequences, it
>was obvious that something like it should be easily provable.
>A given sequence "starts" at the first term for which the error
>satifies certain inequalities, and you just have to see what
>inequalities for the sum follow from those for the summands.
>I bet there's a very clean exact determinantion of the shift.
Oh, feel free to supply one anytime; I'm still plodding toward it. I note
that the "exceptional" sequence is the "Beatty-dual" of the first column, so
there's a complement of the conjecture in terms of [n*tau] instead of
[n*tau^2], but I don't know if this is of any more use than a dog biscuit.
Really, isn't this is all pretty provocative? It implies that, for example,
adding two Hn(x)=(n+xAn)/(1-x-x^2) will have one of exactly two forms (ie
the vanilla or the shifted one), as determined by this wacky rule. The
addition operation commutes but apparently doesn't associate. I was hoping
by including a shift it would have some nice structure (recall that this
would extend the wackiness to cover *all* such recurrences).
> Did I send out the "Empire State" table? This defines
>a natural "central term" for a doubly-infinite fib sequence,
>and shows how to find this from the "starting term". The
>central term is midway between the starting terms of the sequence
>and its "reverse" (with alternate signs changed). Unfortunately,
>the central term of a doubled sequence (say) need not be the
>double of the central term of the original.
This all sounds new--please send whatever you have!
> I don't know if I sent out my stuff on how to find the
>parameters of multiplied sequences? If not, I'll try to
>dig it up.
By multiplied I assume you mean as in your original question--which I'd now
prefer to call "scaled", if it's OK with you to ask a terminological return
favor. (There's at least one other kind of "multiplied" that you can get
when you represent them as homographic (aka bilinear rational) functions
<--> 2x2 matrices, where function composition corresponds to matrix multiply.)
(OK, I'll confess, my secret desire is that HF addition will suggest some
new kind of HF multiplication HF*HF that distributes etc)
> What I like about all this is that it's really not very often
>that one sees anything really new and interesting about Fibonacci
>numbers and the like. This not only feels new, but it's also
>a large and interesting theory, rather than an isolated observation!
>
> John Conway
From and.Princeton.EDU!conway Thu Jan 16 20:08 EST 1997
Return-Path:
Date: Thu, 16 Jan 1997 19:20:38 -0500 (EST)
From: John Conway
Subject: Re: More about Kimberling sums
To: Dan Hoey
Cc: math-fun@cs.arizona.edu
In-Reply-To: <9701162354.AA17256@sun13.aic.nrl.navy.mil>
I'm sorry, I thought I'd given the closed forms for
the general "Kimberling sequence". I certainly knew them.
By the way, I don't want to deprive Clark Kimberling of his credit,
but may I say that I still prefer my name "(higher) Fibonacci
sequence", because it's more likely to suggest the meaning,
and because these sequences have long been called the "other"
Fibonacci sequences.
In general naming things after people is less helpful than
naming them by their properties. Of course "Fibonacci" is a
name, but so standard that it already suggests a meaning! The
really GREAT sequence that Kimberling found is his "parafibonacci"
sequence. This is my name, intended to recall the fact that it gives
the parameter of the appropriate (higher) Fib sequence.
I think I defined the Fibonacci inflation function n+ by
pumping up the terms in Zeckendorff's expansion as a sum of
Fib numbers? You can also define it by multiplying n by
the golden number tau (= phi) and then rounding this
"goldenly" (you should be able to work out what this means).
The two terms "before" the n'th fib sequence are n and 1 + n+,
from which you can work out the general term.
When I saw the conjecture about adding these sequences, it
was obvious that something like it should be easily provable.
A given sequence "starts" at the first term for which the error
satifies certain inequalities, and you just have to see what
inequalities for the sum follow from those for the summands.
I bet there's a very clean exact determinantion of the shift.
Did I send out the "Empire State" table? This defines
a natural "central term" for a doubly-infinite fib sequence,
and shows how to find this from the "starting term". The
central term is midway between the starting terms of the sequence
and its "reverse" (with alternate signs changed). Unfortunately,
the central term of a doubled sequence (say) need not be the
double of the central term of the original.
I don't know if I sent out my stuff on how to find the
parameters of multiplied sequences? If not, I'll try to
dig it up.
What I like about all this is that it's really not very often
that one sees anything really new and interesting about Fibonacci
numbers and the like. This not only feels new, but it's also
a large and interesting theory, rather than an isolated observation!
John Conway
On Thu, 16 Jan 1997, Dan Hoey wrote:
> Marc Le Brun summarized the directions in which he,
> ACW, NJAS, have been Kimberled:
>
> > Let Kn be the n-th Kimberling sequence, defined by
> > Kn[0] = n
> > Kn[1] = An
> > Kn[i] = Kn[i-1] + Kn[i-2]
> > for all non-negative integers n and all integers i, where
> > An = floor[(n+1)*tau].
>
> Thank you thank you! I was hoping for a closed-form expression for
> Kn[1]--John uses methods that seem to require looking over the earlier
> sequences for missing elements.
>
> > Let Zn = An + n + 1 = 2, 5, 7, 10, 13, 18, 20, 23,...
> > (Z may connote the opposite of A, zero shift, or Zeckendorf).
>
> Zn seems to be just those n for which (n+1)tau - An < 1/tau--i.e.
> (n+1)tau mod 1 is less than 1/tau. Now I'd think it should be
> possible to show why A[p+q] = Ap + Aq exactly when p,q but not p+q are
> in Zn, and otherwise A[p + q + Ap + Aq] = p + q + 2Ap + 2Aq, which
> would yield the conjecture. But I'm not getting anywhere with it.
>
> Allan's J function easy to calculate here, too. He wrote
>
> J(p + q phi) = pp + pq - qq
>
> but did you notice
>
> J(p + q phi) = (p + q phi)(p - q/phi).
>
> The latter may interact better with the closed form for An. Allan
> mentioned that J(F5)=J(F7)=11, and somehow I hoped that was some sort
> of pairing instead of an arbitrary multiplicity. Unfortunately
> J(F33)=J(F45)=J(F65)=121, and 6061 is the J of sequences 1860, 1941,
> 2171, 2388, 2932, 3225, 3607, and 3764. There are more examples of
> all multiplicities up to 8 among the first 10000 sequences.
>
> (P.S. Allan is evidently a phi-lologist. Is there a name for the
> folks who say tau? Me, I want to stay neutral, even if it costs me
> two Greek letters.)
>
> Dan
> Hoey@AIC.NRL.Navy.Mil
From AIC.NRL.Navy.Mil!hoey Fri Jan 17 19:11 EST 1997
Return-Path:
Date: Fri, 17 Jan 97 19:02:16 EST
From: Dan Hoey
To: math-fun@cs.arizona.edu
Subject: Inverse higher-fib/Kimberling table
For those of us who may not have found all the neat things in the
table John Conway posted on 2 December, here's a slight extension,
mostly done by computer. For a given x,y it shows the index of the
unique higher Fibonacci sequence that contains ...,x,y,.... Blanks
spaces to the north and east are sequences above H99. The blank
southwest halfplane is for the sequences below H0 (they would be
unreversed negatives of the positive sequences, I guess, but I'm not
sure they fit the scheme).
\x -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
y\
23 / '85 87 89 91/35 36'(5)23'
22 / '80 82 84 86/33 34'13 (8)22'
21 / '77 79 81 83/32'12 (0)21'57
20 / '72 74 76 78/30 31'(4)20'54 55
19 / '67 69 71 73 75/29'11 (7)19'52 53/
18 / '64 66 68 70/27 28'(1)18'49 50 51/
17 / '59 61 63 65/25 26'10 (6)17'47 48/
16 /88 93 98 '56 58 60 62/24' 9 (2)16'44 45 46/
15 /80 85 90 95 '51 53 55 57/22 23'(3)15'41 42 43/
14/67 72 77 82 87 92 97 '46 48 50 52 54/21' 8 (5)14'39 40/
13/59 64 69 74 79 84 89 94 99 '43 45 47 49/19 20'(0)13'36 37 38/
12 51 56 61 66 71 76 81 86 91 96'38 40 42 44/17 18' 7 (4)12'34 35/96 99
11 43 48 53 58 63 68 73 78 83'33 35 37 39 41/16' 6 (1)11'31 32 33/91 94 97
10 35 40 45 50 55 60 65 70 75'30 32 34 36/14 15'(2)10'28 29 30/83 86 89 92 95
9 27 32 37 42 47 52 57 62'25 27 29 31/12 13' 5 (3) 9'26 27/75 78 81 84 87 90
8 19 24 29 34 39 44 49 54'22 24 26 28/11' 4 (0) 8'23 24 25/70 73 76 79 82 85
7 11 16 21 26 31 36 41'17 19 21 23/ 9 10'(1) 7'20 21 22/62 65 68 71 74 77 80'
6 3 8 13 18 23 28'12 14 16 18 20/ 8' 3 (2) 6'18 19/54 57 60 63 66 69 72'
5 0 5 10 15 20' 9 11 13 15/ 6 7'(0) 5'15 16 17/49 52 55 58 61 64 67'
4 2 7' 4 6 8 10/ 4 5' 2 (1) 4'13 14/41 44 47 50 53 56 59'
3 ' 1 3 5 7/ 3' 1 (0) 3'10 11 12/36 39 42 45 48 51'
2 5,8 ' 0 2/ 1 2'(0) 2' 7 8 9/28 31 34 37 40 43 46'
1 ' / 0' 0 (0) 1' 5 6/20 23 26 29 32 35 38'
0 ' 2,3 / '(*) 0' 2 3 4/15 18 21 24 27 30 33'96
-1 ' / 1,1 '( ) ' 0 1/ 7 10 13 16 19 22 25'75 83 91 99
-2 ' / '1,0( ) ' / 2 5 8 11 14 17'54 62 70 78 86 94
-3 ' / '( )0,1' 1,2 / 0 3 6 9 12'41 49 57 65 73 81
-4' / ' ( ) ' / 1 4'20 28 36 44 52 60 68
-5' / ' ( ) ' / 3,5 ' 7 15 23 31 39 47 55
-6 / '( ) ' / ' 2 10 18 26 34 42
-7 / ' ( ) ' / ' 5 13 21 29
-8 / '( ) ' / ' 8,13 0 8 16
Star * marks the origin. The strips are demarcated by / and ' in
lines of slope tau to make it easier to track them near the center.
Remember each strip contains all the nonnegative integers, once, as a
linear function of the coordinates. The most important item in the
extension is that I've continued the central lane (in parens()) far
enough to see the nice surprise it contains. Apologies for the spoiler
to anyone else who hasn't noticed it in the last month and a half.
Dan