Interspersions and Fractal Sequences Associated with Fractions c^{j}/d^{k}

Clark Kimberling Department of Mathematics University of Evansville 1800 Lincoln Avenue Evansville, IN 47722 USA

                      ck6@evansville.edu

Abstract

Suppose c ≥ 2 and d ≥ 2 are integers, and let S be the set of integers ⌊c^{j}/d^{k}⌋, where j and k range over the nonnegative integers. Assume that c and d are multiplicatively independent; that is, if p and q are integers for which c^{p} = d^{q}, then p = q = 0. The numbers in S form interspersions in various ways. Related fractal sequences and permutations of the set of nonnegative integers are also discussed.

1 Introduction

Throughout this article, the letters c, d, j, k, p, q, h, m, n represent nonnegative integers such that c ≥ 2 and d ≥ 2, and c and d are multiplicatively independent; that is, if c^{p} = d^{q}, then p = q = 0.

Definitions, examples, and references for the terms interspersion and fractal sequence are easily accessible ([9, 10, 11, 7]), so that only a brief summary is given in this introduction. This introduction also presents certain new arrays defined from the manner in which the fractions c^{j}/d^{k} are distributed. The main purpose of the article is to prove that each such array is an interspersion.

Definition. An array A = (a_{mh}), m ≥ 1, h ≥ 1, of positive integers is an interspersion if (I1) the rows of A partition the positive integers; (I2) every row of A is an increasing sequence; (I3) every column of A is an increasing (possibly finite) sequence; (I4) if (u_{h}) and (v_{h}) are distinct rows of A, and p and q are indices for which u_{p} < v_{q} <

u_{p+1}, then

u_{p+1} < v_{q+1} < u_{p+2}.

Example 1 below illustrates the manner in which property (I4) matches the name “interspersion”; viz., the terms of each row individually separate and are separated by the terms of all other rows (after initial terms).

Definition of the array T_{(c,d,k_{0})} = {t(m, h)}. Row 1 is defined by t(1, h) = c^{h−1}, for h = 1, 2, . . .. For m ≥ 2, the first term t(m, 1) of row m is the least positive integer

⌊c^{j}/d^{k}⌋ , where k ≥ k_{0},

that is not in rows 1, 2, ..., m − 1. In order to define the rest of row m, we shall choose a precise k for the representation t(m, 1) = ⌊c^{j}/d^{k}⌋ . According to Lemma 2 below, every n has infinitely many representations ⌊c^{j}/d^{k}⌋ , and we choose the one for which k is minimal (with k ≥ k_{0}), noting that j is uniquely determined by k. The rest of row m is then defined by

t(m, h) = ⌊c^{j+h−1}/d^{k}⌋ , for h = 1, 2, ….

Example 1. The array T_{(3,2,0)} consists of numbers ⌊\frac{3^{j}}{2^{k}} · 3^{h−1}⌋ , h = 1, 2, 3, …

Table 1. T_{(3,2,0)}
1 3 9 27 81 243 729 2187 ⋯
2 6 20 60 182 546 1640 4900
4 13 40 121 364 1093 3280 9841
5 15 45 136 410 1230 3690 11071
7 22 68 205 615 1845 5535 16607
8 25 76 230 691 2075 6227 18683
10 30 91 273 820 2460 7831 22143
⋮

The rows of T_{(3,2,0)}, indexed by m = 1, 2, 3, …, are given by (j, k) = (0, 0), then (j, k) = (2, 2), then (j, k) = (2, 1), …, as indicated here:

Table 2. The pairs (j, k) = (j_{m}, k_{m}) for T_{(3,2,0)}
m 1 2 3 4 5 6 7 8 9 10 11 12 13 14
j 0 2 2 4 5 7 4 6 8 10 12 7 14 9
k 0 2 1 4 5 8 3 6 9 12 15 7 18 10

Table 1 shows how an interspersion begets a fractal sequence: for each n, we write the number of the row containing n:

(1, 2, 1, 3, 4, 2, 5, 6, 1, 7, 8, 9, 3, 10, 4, 11, 12, 13, 14, 2, 15, 5, …),

a sequence which contains itself as a proper subsequence (infinitely many times).

To conclude this introduction, we note that the arrays T_{(c,d,k_{0})} represent a class of interspersions new to the literature. A few historical notes will help to place the topics of interspersions, dispersions, and fractal sequences within a wider context. Possibly the earliest published array which is an interspersion was published by Kenneth Stolarsky [8] with a revealing title, “A set of generalized Fibonacci sequences such that each natural number belongs to exactly one”. In 1980, David Morrison introduced another interspersion, the Wythoff array. Both the Stolarksy and Wythoff arrays are presented in Neil Sloane’s Classic Sequences [7], which also gives additional twentieth century references, including [2], where the terms “interspersion” and “dispersion” are introduced and proved equivalent, and [3] in which fractal sequences are defined. Twenty-first century references include [1, 4].

2 Verification of interspersion properties

Lemma 1. Suppose s/r is a positive irrational number and 0 < δ < ϵ. Then there exist arbitrarily large integers j and k such that

δ < jr − ks < ϵ.  (1)

Proof. First, suppose δ = 0. Let j_{i}/k_{i} be the ith convergent to s/r, so by [5], for all sufficiently large i, we have

|s/r − j_{i}/k_{i}| < 1/k_{i}^{2}.

Let i be large enough that k_{i} > r/ϵ and j_{i}/k_{i} > s/r. Then

|s/r − j_{i}/k_{i}| < ϵ/rk_{i},

whence 0 < j_{i}r − k_{i}s < ϵ, as desired.

Now suppose there exists δ > 0 such that for some J and K, the inequality (1) fails for all (j, k) satisfying j ≥ J and k ≥ K. Let j′ and k′ satisfy j′ ≥ J, k′ ≥ K, and

0 < j′r − k′s < ϵ − δ,

and let δ_{1} = j′r − k′s. Then

ϵ/δ_{1} − δ/δ_{1} > 1,

so that

δ/δ_{1} < q < ϵ/δ_{1}

for some q ≥ 1. Thus, taking j = qj′ and k = qk′, we have δ < jr − ks < ϵ, a contradiction.

Lemma 2. Every n can be represented as ⌊c^{j}/d^{k}⌋ using arbitrarily large j and k.

Proof. In Lemma 1, put s = ln c and t = ln d; put δ = ln n and ϵ = ln(n + 1), and let j and k be arbitrarily large integers satisfying (1):

ln n < j ln c − k ln d < ln(n + 1).

Equivalently, n < c^{j}/d^{k} < n + 1, so that n = ⌊c^{j}/d^{k}⌋ .

Lemma 3. Suppose n is a term in T = T_{(c,d,x_{0})}, so that n = t(m, h) for some (m, h). Then the row-successor of n is given by

t(m, h + 1) = cn + q for some q satisfying 0 ≤ q ≤ c − 1.

Proof. We have n = ⌊c^{j}/d^{k}⌋ = c^{j}/d^{k} − δ, where 0 < δ < 1, so that cn = c^{j+1}/d^{k} − cδ. Also, t(m, h + 1) = c^{j+1}/d^{k} − ϵ, where 0 < ϵ < 1, so that

t(m, h + 1) − cn = cδ − ϵ.

Now 0 < cδ < c, so that −1 < cδ − ϵ < c. Because cδ − ϵ is an integer, we conclude that it is in {0, 1, …, c − 1}.

Lemma 4. No two terms of the array T = T_{(c,d,k_{0})} are equal.

Proof. Suppose, to the contrary, that there are distinct terms n = ⌊c^{j}/d^{k}⌋ and n_{1} = ⌊c^{j_{1}}/d^{k_{1}}⌋ such that n = n_{1}. Assume, without loss of generality, that j is the least exponent for which ⌊c^{j_{1}}/d^{k_{1}}⌋ = ⌊c^{j}/d^{k}⌋ for some j_{1} and k_{1}.

Case 1 : neither n nor n_{1} lies in column 1 of T. By Lemma 3,

n = c ⌊c^{j−1}/d^{k}⌋ + q and n_{1} = c ⌊c^{j_{1}−1}/d^{k_{1}}⌋ + q_{1},

where 0 ≤ q ≤ c − 1 and 0 ≤ q_{1} ≤ c − 1. Thus,

c ⌊c^{j−1}/d^{k}⌋ + q = c ⌊c^{j_{1}−1}/d^{k_{1}}⌋ + q_{1},

so that, assuming without loss that ⌊c^{j−1}/d^{k}⌋ ≥ ⌊c^{j_{1}−1}/d^{k_{1}}⌋ , we have

⌊c^{j−1}/d^{k}⌋ − ⌊c^{j_{1}−1}/d^{k_{1}}⌋ = (q_{1} − q)/c.

But 0 ≤ (q_{1} − q)/c < 1, so that, as (q_{1} − q)/c is an integer, we have q_{1} = q and ⌊c^{j−1}/d^{k}⌋ = ⌊c^{j_{1}−1}/d^{k_{1}}⌋ , contrary to the minimality of j.

Case 2 : one of the terms, n or n_{1}, lies in column 1. By definition of column 1, n and n_{1} cannot both lie in column 1. Assume that n but not n_{1} lies in column 1. Write n = t(m, 1) and n_{1} = t(m_{1}, h), where h ≥ 2. Then by definition of t(m, 1), we have m_{1} ≥ m, so that

n ≤ T (m_{1}, 1) < n_{1},

contrary to the assumption that n = n_{1}.

Theorem 5. The array T_{(c,d,k_{0})} is an interspersion.

Proof. By Lemma 4, property (I1) in the introduction holds, and clearly (I2) and (I3) hold. To see that (I4) holds, suppose

t(m, h) < t(m′, h′) < t(m, h + 1).

We must prove

t(m, h + 1) < t(m′, h′ + 1) < t(m, h + 2).

Since t(m, h) < t(m′, h′), we have t(m′, h′) − t(m, h) ≥ 1, so that

ct(m′, h′) − ct(m, h) ≥ c.

Consequently, if 0 ≤ q_{1} ≤ c − 1 and 0 ≤ q_{2} ≤ c − 1, then ct(m′, h′) − ct(m, h) ≥ q_{1} − q_{2}, so that

ct(m, h) + q_{1} ≤ ct(m′, h′) + q_{2},

which by Lemma 3 implies t(m, h + 1) ≤ t(m′, h′ + 1), so that by Lemma 4,

t(m, h + 1) < t(m′, h′ + 1)

Likewise, the inequality

ct(m, h + 1) − ct(m′, h′) ≥ c

implies t(m′, h′ + 1) < t(m, h + 2).

3 Permutations of ℕ

Suppose c, d, k_{0} are as already stipulated, and abbreviate T_{(c,d,k_{0})} as T. In this section, we shall show that the exponents k in the representation ⌊c^{j}/d^{k}⌋ for the numbers in T form a permutation of the sequence ℕ = (0, 1, 2, …). For example, as indicated in Table 2, for (c, d, k_{0}) = (3, 2, 0), the sequence of values of k is

(0, 2, 1, 4, 5, 8, 3, 6, 9, 12, 15, 7, 18, 10, …).

Theorem 6. Regarding the interspersion T_{(c,d,k_{0})}, let

⌊(c^{j_{m}}/d^{k_{m}})c^{h−1}⌋ , for h = 1, 2, 3, …,

be the numbers in row m. Then each n ≥ k_{0} occurs exactly once in the sequence (k_{m}).

Proof. Suppose, to the contrary, that there is a least K ≥ k_{0} for which, for every j,

⌊c^{j}/d^{K}⌋ = ⌊c^{p_{j}}/d^{k}⌋

for some k satisfying k_{0} ≤ k < K and p_{j}. Then

|\frac{c^{j}}{d^{K}} − \frac{c^{p_{j}}}{d^{k}} | < 1.

Moreover, as k < K, we have p_{j} < j and can write K = k + e where e > 0 and j = p_{j} + e_{j} where e_{j} > 0, so that

|\frac{c^{e_{j}}}{d^{e}} − 1| < \frac{d^{k}}{c^{p_{j}}} .

As j → ∞, clearly p_{j} → ∞, so that \frac{d^{k}}{c^{p_{j}}} → 0. Consequently, c^{e_{j}} = d^{e} for all sufficiently large j, contrary to the independence of c and d, as defined and hypothesized in the introduction. Thus, there is no such K, which is to say that for every k ≥ k_{0}, there exists a row of T such that the numbers in that row are the numbers ⌊(c^{j}/d^{k})c^{h−1}⌋ for some j. By definition of t(m, 1) as the least ⌊c^{j}/d^{k}⌋ = ⌊c^{j_{m}}/d^{k_{m}}⌋ not in a row numbered 1, 2, ..., m − 1, the numbers k_{m} are distinct.

Regarding the set ℕ of natural numbers to be {1, 2, 3, ...}, Theorem 6 shows that the sequence (k_{m}−k_{0}+1) is a permutation of ℕ. Do such permutations have notable asymptotics? Can they be efficiently computed? We leave these questions open.

4 Examples

In Theorem 5, the index k_{0} can be any nonnegative integer, and in Example 1, k_{0} = 0. In Table 3, we keep (c, d) = (3, 2) as in Table 1 but change k_{0} to 1. In infinitely many cases, a row of T_{(3,2,0)} is identical to a row of T_{(3,2,1)}, and in infinitely many cases a row of T_{(3,2,0)} is not identical to a row of T_{(3,2,1)}. These easily proved observations remain true for k_{0} = 2, 3, 4, ….

Table 3. T_{(3,2,1)}
1 4 13 40 121 364 1093 3280 ⋯
2 6 20 60 182 546 1640 4920
3 10 30 91 273 820 2460 7381
5 15 45 136 410 1230 3690 11071
7 22 68 205 615 1845 5535 16607
8 25 76 230 691 2075 6227 18683
9 28 86 259 778 2335 7006 21018
⋮

The rows of T_{(3,2,1)}, indexed by m = 1, 2, 3, …, are given by (j, k) = (1, 1), then (j, k) = (2, 2), then (j, k) = (3, 3), …, as indicated here:

Table 4. The pairs (j, k) = (j_{m}, k_{m}) for T_{(3,2,1)}
m 1 2 3 4 5 6 7 8 9 10 11 12 13 14
j 1 2 3 4 5 7 9 6 8 10 12 7 14 9
k 1 2 3 4 5 8 11 6 9 12 15 7 18 19

The fractal sequence corresponding to T_{(3,2,1)} is

(1, 2, 3, 1, 4, 2, 5, 6, 7, 3, 8, 9, 1, 10, 4, 11, 12, 13, 14, 2, 15, 5, 16, 17, 6, …).

Next, we change k_{0} to 3 :

Table 5. T_{(3,2,3)}
1 3 10 30 91 273 820 2460 ⋯
2 7 22 68 205 615 1845 5535
4 12 38 115 345 1037 3113 9341
5 15 45 136 410 1230 3690 11071
6 19 57 172 518 1556 4670 14012
8 25 76 230 691 2075 6227 18683
9 28 86 259 778 2335 7006 21018
⋮

The rows of T_{(3,2,3)}, indexed by m = 1, 2, 3, …, are given by (j, k) = (2, 3), then (j, k) = (4, 5), then (j, k) = (7, 9), …, as indicated here:

Table 6. The pairs (j, k) = (j_{m}, k_{m}) for T_{(3,2,3)}
m 1 2 3 4 5 6 7 8 9 10 11 12 13 14
j 2 4 7 4 8 7 9 6 15 10 12 7 14 16
k 3 5 9 4 10 8 11 6 20 12 15 7 18 21

The fractal sequence corresponding to T_{(3,2,3)} is

(1, 2, 1, 3, 4, 5, 2, 6, 7, 1, 8, 3, 9, 10, 4, 11, 12, 13, 5, 14, 15, 2, 16, 17, 6, …).

As a final example, consider the interspersion T_{(2,3,0)} :

Table 7. T_{(2,3,0)}
1 2 4 8 16 32 64 128 ⋯
3 7 14 28 56 113 227 455
5 10 21 42 85 170 341 682
6 12 25 50 101 202 404 809
9 189 37 75 151 303 606 1213
11 22 44 89 179 359 719 1438
13 26 53 106 213 426 852 1704
⋮

The rows of T_{(2,3,0)}, indexed by m = 1, 2, 3, …, are given by (j, k) = (0, 0), then (j, k) = (5, 2), then (j, k) = (4, 1), …, as indicated here:

Table 8. The pairs (j, k) = (j_{m}, k_{m}) for T_{(2,3,0)}
m 1 2 3 4 5 6 7 8 9 10 11 12 13 14
j 0 5 4 9 8 13 18 23 20 17 44 22 30 46
k 0 2 1 4 3 6 9 12 10 8 25 11 16 26

The fractal sequence corresponding to T_{(2,3,0)} is

(1, 1, 2, 1, 3, 4, 2, 1, 5, 3, 6, 4, 7, 2, 8, 1, 9, 5, 10, 11, 3, 6, 12, 13, 4, 7, 14, 2, …).

References

[1] C. Kimberling and John E. Brown, Partial complements and transposable dispersions, J. Integer Sequences 7 (2004), Article 04.1.6.

[2] C. Kimberling, Interspersions and dispersions, Proc. Amer. Math. Soc. 117 (1993), 313– 321.

[3] C. Kimberling, Numeration systems and fractal sequences, Acta Arith. 73 (1995), 103– 117.

[4] C. Kimberling, The equation (j + k + 1)^{2} − 4k = Qn^{2} and related dispersions, J. Integer Sequences 10 (2007), Article 07.2.7.

[5] S. Lang, Introduction to Diophantine Approximations, Addison-Wesley, Reading, Massachusetts, 1966.

[6] N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences, available at

   http://www.research.att.com/~njas/sequences/.

[7] N. J. A. Sloane, Classic Sequences In The On-Line Encyclopedia of Integer Sequences, Part 1: The Wythoff Array and The Para-Fibonacci Sequence, available at

   http://www.research.att.com/~njas/sequences/classic.html.

[8] K. Stolarsky, A set of generalized Fibonacci sequences such that each natural number belongs to exactly one, Fib. Quart., 15 (1977), 224.

[9] E. Weisstein, MathWorld, Fractal Sequence, http://mathworld.wolfram.com/FractalSequence.html

[10] E. Weisstein, MathWorld, Interspersion, http://mathworld.wolfram.com/Interspersion.html

[11] E. Weisstein, MathWorld, Dispersion, http://mathworld.wolfram.com/SequenceDispersion.html

2000 Mathematics Subject Classification: Primary 11B99 Keywords: interspersion, fractal sequence.

(Concerned with sequences \underline{A007337}, \underline{A022447}, \underline{A114537}, \underline{A114577}, \underline{A120862}, \underline{A120863}, \underline{A124904}, \underline{A124905}, \underline{A124906}, \underline{A124907}, \underline{A124908}, \underline{A124909}, \underline{A124910}, \underline{A124911}, \underline{A124912}, \underline{A124913}, \underline{A124914}, \underline{A124915}, \underline{A124916}, \underline{A124917}, \underline{A124918}, \underline{A124919}, \underline{A125150}, \underline{A125151}, \underline{A125152}, \underline{A125153}, \underline{A125154}, \underline{A125155}, \underline{A125156}, \underline{A125157}, \underline{A125158}, \underline{A125159}, \underline{A125160}, and \underline{A125161}.)

Received December 30 2006; revised version received May 4 2007. Published in Journal of Integer Sequences, May 6 2007.

Return to Journal of Integer Sequences home page.