The Equation (j + k + 1)^{2} − 4k = Qn^{2} and Related Dispersions

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

                      ck6@evansville.edu

Abstract Suppose Q is a positive nonsquare integer congruent to 0 or 1 mod 4. Then for every positive integer n, there exists a unique pair (j, k) of positive integers such that (j + k + 1)^{2} − 4k = Qn^{2}. This representation is used to generate the fixed-j array for Q and the fixed-k array for Q. These arrays are proved to be dispersions; i.e., each array contains every positive integer exactly once and has certain compositional and row-interspersion properties.

1 Introduction

The Pell-like equation m^{2} − 4k = Qn^{2}, where Q is a positive nonsquare integer congruent to 0 or 1 mod 4, can be written in the form

(j + k + 1)^{2} − 4k = Qn^{2},  (1)

or equivalently

(j + k − 1)^{2} + 4j = Qn^{2}.  (2)

When so written, there is, for each n, a unique solution (j, k); here and throughout this work, the symbols n, j, k represent positive integers. In section 2, the existence and uniqueness of such a solution is proved. In section 3, the definition of dispersion is recalled, and in section 4, it is proved that certain arrays associated with solutions of (2) are dispersions. In section 5, another class of arrays are proved to be dispersions. In sections 4 and 5, Q is restricted to 0-congruence mod 4, and in section 6, conjectures are given for Q ≡ 1 mod 4. In section 7, various numerical sequences associated with the dispersions in preceding sections are discussed.

Throughout, we abbreviate \sqrt{Q}/2 as Q_{1}.

2 Unique Representations

Theorem 1. Suppose that Q ≡ 0 mod 4. Then the unique solution of (1) is given by

j = (Q_{1}n)^{2} − ⌊Q_{1}n⌋^{2} ,  (3)
k = (1 + ⌊Q_{1}n⌋)^{2} − (Q_{1}n)^{2}.  (4)

Proof: The method of proof is to assume that (1) has a solution, to find it, and then to observe that it is unique. Let m = j + k + 1. Clearly, in order for (1) to hold, m must be even, so we write m = 2h. The equation m^{2} − 4k = Qn^{2} then yields

k = h^{2} − Qn^{2}/4.

Equation (2) can be written as (m − 2)^{2} + 4j = Qn^{2}, from which

j = Qn^{2}/4 − (h − 1)^{2},

so that the requirement that j̇ > 0 is equivalent to

h < 1 + Q_{1}n.

Also, the requirement that k > 0 is equivalent to

h > Q_{1}n.

Clearly there is exactly one such integer:

h = 1 + ⌊Q_{1}n⌋ ,

from which (3) and (4) follow. ■

Theorem 2. Suppose that Q ≡ 1 mod 4. Then the unique solution of (1) is given by

j = \{ \begin{matrix}(Q_{1}n)^{2} − (⌊1/2 + Q_{1}n⌋ − 1/2)^{2} & if n is odd, \\ (Q_{1}n)^{2} − ⌊Q_{1}n⌋^{2} & if n is even, \end{matrix}  (5)
k = \{ \begin{matrix}(⌊1/2 + Q_{1}n⌋ + 1/2)^{2} − (Q_{1}n)^{2} & if n is odd, \\ (1 + ⌊Q_{1}n⌋)^{2} − (Q_{1}n)^{2} & if n is even. \end{matrix}  (6)

Proof: The method for even n is the same as for Theorem 1. If n is odd, then m must be odd. Put m = 2h + 1, and find the asserted result using essentially the same method as for Theorem 1. ■

Theorem 3. Suppose that Q ≡ 2 mod 4 or Q ≡ 3 mod 4 and that n is even. Then the unique solution of (1) is given by (3) and (4). If n is odd, then (1) has no solution.

Proof: The method for even n is the same as for Theorem 1. Now suppose n is odd. Write Q = r + 4s, where r = 2 or r = 3, and write n = 2h + 1. Then m^{2} = 4k + (r + 4s)(2h + 1)^{2} ≡ r mod 4. But this is contrary to the fact that the residues mod 4 of the squares are all 0 or 1. ■

Corollary. Suppose Q ≡ 2 mod 4 or Q ≡ 3 mod 4 and n is a positive integer. Then the unique solution of the equation

(j + k + 1)^{2} − 4k = 4Qn^{2}  (7)

is given by (3) and (4)

Proof: The number 2n is even, so that Theorem 3 applies – or, as a second proof, apply Theorem 1, as 4Q ≡ 0 mod 4. ■

3 Dispersions

A dispersion is an array of positive integers in which each occurs exactly once, and certain conditions ([1], [4]) hold: specifically, an array D = {d(g, h)} is the dispersion of a strictly increasing sequence s(k) if the first column of D is the complement of s(k) in increasing order, and

d(1, 2) = s(1) ≥ 2;
d(1, h) = s(d(1, h − 1)) for all h ≥ 3;
d(g, h) = s(d(g, h − 1)) for all h ≥ 2, for all g ≥ 2.

In this section we introduce simple dispersions D(r) and E(r). In later sections, related dispersions will be generated in connection with equations (1) and (2).

Suppose r > 2 is an irrational number, and let D(r) denote the dispersion of the sequence {⌊rn⌋}. In order to construct D(r), let r′ be the number given by

1/r + 1/r′ = 1,

so that the Beatty sequences {⌊rn⌋} and {⌊r′n⌋} partition the set of positive integers. Writing d(g, h) for the general term of D(r), we have

d(g, 1) = ⌊r′g⌋ for all g ≥ 1,
d(g, h) = ⌊rd(g, h − 1)⌋ for all g ≥ 1 and h ≥ 2.

Thus, all the terms of the sequence {⌊rn⌋} are dispersed in the columns of D(r) excluding the first.

Example 1. The dispersion D(r) for r = 3 + 2\sqrt{2} is represented here and as \underline{A120858} in [3]. Column 1 is the sequence d(g, 1) = ⌊r′g⌋ for r′ = (1 + \sqrt{2})/2.

1 5 29 169 985 ⋯
2 11 64 373 2174
3 17 99 577 3363
4 23 134 781 4552
6 34 198 1154 6726
7 40 233 1358 7915
8 46 268 1562 9104
9 52 303 1766 10293
10 58 338 1970 11482
12 69 402 2343 13656
13 75 437 2547 14845

⋮

Now suppose r > 1 is an irrational number, and define

E(1, 1) = 1, E(1, h) = ⌊rE(1, h − 1)⌋ + 1 for h ≥ 2,

and inductively define, for g ≥ 2,

E(g, 1) = least positive integer not among E(i, h) for 1 ≤ i ≤ g − 1, h ≥ 1;
E(g, h) = ⌊rE(1, h − 1)⌋ + 1 for h ≥ 2.

Then E = {E(g, h)} is clearly the dispersion of the sequence s(k) given by

s(k) = ⌊rk⌋ + 1,

and the complement {s′(k)} of {s(k)} is given by

s′(k) = ⌊r′(k − 1)⌋ + 1, where 1/r + 1/r′ = 1.

Example 2. The dispersion E(3 + 2\sqrt{2}) is represented here and as \underline{A120859} in [3]:

1 6 35 204 1189 ⋯
2 12 70 408 2378
3 18 105 612 4756
4 24 140 816 4348
5 30 175 1020 5945
7 41 239 1393 8119
8 47 274 1597 9308
9 53 309 1801 10497
10 59 344 2005 11686
11 65 379 2209 12875
13 76 443 2582 15049

⋮

Next, suppose that r is a quadratic irrational number: r = a + b\sqrt{Q}, where Q is not a square. By Theorem 4 in [1], the rows of D(r) and also the rows of E(r) satisfy the recurrence

x_{n} = 2ax_{n−1} + (b^{2}Q − a^{2})x_{n−2}.

For example, the row recurrence for the dispersions in Examples 1 and 2 is

x_{n} = 6x_{n−1} − x_{n−2}.

4 Fixed-j Dispersions for Q ≡ 0 mod 4

Suppose that Q ≡ 0 mod 4 and that (2) holds for a triple (j, k, n). Keeping j fixed, we ask what other pairs (k_{1}, n_{1}) there are for which (j, k_{1}, n_{1}) is another solution of (1). This question is answered by Theorem 4, which, with Theorems 5 and 6, shows that for given j, the set of such n_{1} forms a row, or in some cases, several rows, of a dispersion.

Theorem 4. Suppose that Q ≡ 0 mod 4 and that n, j, k satisfy (2). Let u be the least positive integer x such that

x^{2} − 1 = Qy^{2}/4

for some positive integer y, and let

n_{1} = un + y ⌊Q_{1}n⌋ ,  (8)
k_{1} = (1 + ⌊Q_{1}n_{1}⌋)^{2} − (Q_{1}n_{1})^{2}.  (9)

Then

(j + k_{1} − 1)^{2} + 4j = Qn_{1}^{2}.  (2A)

Proof: In view of (2) and (2A), it suffices to prove that

(j + k − 1)^{2} − Qn^{2} = (j + k_{1} − 1)^{2} − Qn_{1}^{2}.  (10)

Using (3) and (4), we have

j + k − 1 = 2 ⌊Q_{1}n⌋ ,

which, along with (3) and (8), leads to the following equivalent of (10):

(Q_{1}^{2}n^{2} − ⌊Q_{1}n⌋^{2} + k_{1} − 1)^{2} = 4 ⌊Q_{1}n⌋^{2} − Qn^{2} + Qu^{2}n^{2}
+2Quny ⌊Q_{1}n⌋ + Qy^{2} ⌊Q_{1}n⌋^{2} .  (11)

Next using

u^{2} − 1 = Q_{1}^{2}y^{2}  (12)

and Q_{1}^{2} = Q/4, we find, after simplifications, that (11) is equivalent to

(Q_{1}^{2}n^{2} − ⌊Q_{1}n⌋^{2} + k_{1} − 1)^{2} = (2u ⌊Q_{1}n⌋ + 2nyQ_{1}^{2})^{2}.  (13)

Taking square roots leads to

k_{1} = ⌊Q_{1}n⌋^{2} − Q_{1}^{2}n^{2} + 2u ⌊Q_{1}n⌋ + 2ynQ_{1}^{2} + 1  (14)

as an equivalent of (13). Thus, using (9), what we must prove is that

(1 + ⌊Q_{1}n_{1}⌋)^{2} = ⌊Q_{1}n⌋^{2} − Q_{1}^{2}n^{2} + 2u ⌊Q_{1}n⌋ + 2ynQ_{1}^{2} + 1
+Q_{1}^{2}(un + y ⌊Q_{1}n⌋)^{2}.  (15)

Expanding the right side of (15) and again using (12), we find that the right-hand side of (15) is a square, and taking square roots leaves the following equivalent of (10):

1 + ⌊Q_{1}n_{1}⌋ = u ⌊Q_{1}n⌋ + ynQ_{1}^{2} + 1,

so that, using (8), what we must prove has now been reduced to

⌊Q_{1}(un + y ⌊Q_{1}n⌋)⌋ = u ⌊Q_{1}n⌋ + ynQ_{1}^{2}.  (16)

To prove (16), we begin by noting from (12) that

(u − yQ_{1})(u + yQ_{1}) = 1,  (17)

showing that

u − yQ_{1} > 0.

Let ϵ = Q_{1}n − ⌊Q_{1}n⌋ , the fractional part of Q_{1}n. The fact that (u − yQ_{1})ϵ > 0 readily renders

u ⌊Q_{1}n⌋ + ynQ_{1}^{2} < Q_{1}(un + y ⌊Q_{1}n⌋).  (18)

Also, since u + yQ_{1} > 1, we have from (17)

u − yQ_{1} < 1,  (19)

so that (u − yQ_{1})ϵ < 1, and consequently,

Q_{1}(un + y ⌊Q_{1}n⌋) < u ⌊Q_{1}n⌋ + ynQ_{1}^{2} + 1.

This and (18) imply (16) and hence (10). ■

Regarding u and y in Theorem 4 as sequences with terms u(n) and y(n), where n = Q/4, we note that u and y are registered in [3] as \underline{A033313} and \underline{A033317}. Several initial terms are shown here:

\begin{matrix}Q & 8 & 12 & 20 & 24 & 28 & 32 & 40 & 44 & 48 \\ u & 3 & 2 & 9 & 5 & 8 & 3 & 19 & 10 & 7 \\ y & 2 & 1 & 4 & 2 & 3 & 1 & 6 & 3 & 4 \end{matrix}

Theorem 5. Suppose that Q, j, k, u, y, n, and n_{1} are as in Theorem 4, and let

n_{2} = un_{1} + y ⌊Q_{1}n_{1}⌋ .  (20)

Then

n_{2} = 2un_{1} − n.  (21)

Proof: It suffices to prove that the right-hand sides of (21) and (22) are equal, or equivalently, that

n = un_{1} − y ⌊Q_{1}n_{1}⌋ .  (22)

Using (8) to substitute for n shows that (22) is equivalent to

⌊unQ_{1} + yQ_{1} ⌊Q_{1}n_{1}⌋⌋ = nyQ_{1}^{2} + u ⌊Q_{1}n⌋ .  (23)

Now since ⌊nQ_{1}⌋ < nQ_{1}, we have

nyQ_{1}^{2} + u ⌊Q_{1}n⌋ < unQ_{1} + yQ_{1} ⌊Q_{1}n_{1}⌋ .  (24)

Also, in connection with (17),

Q_{1}n − ⌊Q_{1}n⌋ < 1/(u − yQ_{1}),

which implies

unQ_{1} + yQ_{1} ⌊Q_{1}n_{1}⌋ < nyQ_{1}^{2} + u ⌊Q_{1}n⌋ + 1,

which with (24) establishes (23) and hence (20). ■

We turn now to the construction of the fixed-j array of Q. By Theorem 1, every n has a unique representation of a certain form depending on a pair (j, k) which we shall now write as (j_{n}, k_{n}). By Theorem 4, for each j_{n}, there are infinitely many pairs (n′, k′) such that (1) and (2) hold; that is,

(j_{n} + k_{n′} − 1)^{2} + 4j_{n} = Q(n′)^{2}.  (25)

Let S_{1} be the set of all n′ for which (1A) holds for n = 1 and some k_{n′}. By Theorem 4, n_{1} = u + y ⌊Q_{1}⌋ ∈ S_{1}. (Note that in (25),

j_{1} = Q/4 − ⌊\sqrt{Q}/2⌋ ,

this being the “fixed j” used to define S_{1}). By Theorem 5, the numbers given by the recurrence relation

x_{i} = 2ux_{i−1} − x_{i−1},

with initial values x_{1} = 1 and x_{2} = n_{1}, all lie in S_{1}. Possibly they comprise all of S_{1}, but if not, let w be the least number in S_{1} that is not an x_{i}. By Theorems 4 and 5, we obtain another recurrence sequence {w_{i}} lying in S_{1}. If S_{1} contains a number not in {x_{i}} and not in {w_{i}}, the production of recurrence sequences with all terms in S_{1} can be continued inductively, so that S_{1} is partitioned into a set of such sequences.

Next, let υ be the least positive integer not in S_{1}, and let S_{2} be the set of all υ′ for which (25) holds for n = υ and some k_{υ}′. Again Theorems 4 and 5 apply, so that S_{2} is partitioned into a set of recurrence sequences.

Continuing in this manner, the set of all positive integers is partitioned into sets S_{i}, which are themselves partitioned into sets of recurrence sequences. Next, arrange these sequences so that their first terms form an increasing sequence, thus producing an array of all the positive integers, with increasing first column, and whose rows all satisfy the recurrence relation x_{i} = 2ux_{i−1} − x_{i−1}.

Example 3. The fixed-j array for Q = 8. (This is \underline{A120860} in [3].)

1 5 29 169 985 ⋯
2 10 58 338 1970
3 17 99 577 3363
4 22 128 746 4348
6 34 198 1154 6726
7 39 227 1323 7711
8 46 268 1562 9104
9 51 297 1731 10089
11 63 367 2139 12467
12 68 396 2308 13452
13 75 437 2547 14845
⋮

We prove below that the array in Example 3 is the dispersion of the ordered sequence s of numbers not in its first column; this sequence appears to be \underline{A098021}, described in [3] as “Irrational rotation of the square root of 2 as an implicit sequence with an uneven Cantor cartoon.” (A Cantor cartoon is a kind of geometric fractal, so that \underline{A098021} indicates a connection between geometric fractals and fractal integer sequences as defined just before Example 15. The sequence s and \underline{A098021} agree for 30 terms and no later discrepancies were detected.)

In order to prove that the fixed-j array of Q is actually a dispersion, we begin with a lemma which applies to a wider class of arrays all of whose row sequences satisfy a common second-order recurrence.

Lemma. Suppose that p and q are integers, that p > 0, and that A = {a(g, h)} is an array consisting of all the positive integers, each exactly once. Suppose further that the first column of A is increasing and that every row sequence satisfies the recurrence

x_{n} = px_{n−1} + qx_{n−2}

for n ≥ 3. Finally, suppose for arbitrary indices g, g_{1}, g_{2}, and h that

if a(g_{1}, h) < a(g, 1) < a(g_{1}, h + 1), then a(g_{1}, h + 1) < a(g, 2) < a(g_{1}, h + 2).  (26)

Then A is a dispersion.

Proof: An array is a dispersion if and only if it is an interspersion. In [1], the four defining properties of an interspersion are given, and the first three are assumed in our present hypothesis. It remains to prove the fourth, which is as follows:

if (σ_{i}) and (τ_{i}) are rows of A and σ_{g} < τ_{h} < σ_{g+1}, then σ_{g+1} < τ_{h+1} < σ_{g+2}.  (27)

(Property (27) essentially means that, beginning at the first term of any row having greater initial term than that of another row, all the following terms individually separate the individual terms of the other row; in this sense, every pair of rows are mutually interspersed, as in Examples 1-4.)

Now suppose (σ_{i}) and (τ_{i}) are distinct rows, that g ≥ 1 and h ≥ 1, and that

σ_{g} < τ_{h} < σ_{g+1},  (28)
σ_{g+1} < τ_{h+1} < σ_{g+2}.  (29)

Then since

σ_{g+2} = pσ_{g+1} + qσ_{g} and τ_{g+2} = pτ_{g+1} + qτ_{g},

we have σ_{g+2} < τ_{h+2} < σ_{g+3}, and, inductively,

σ_{g′} < τ_{h′} < σ_{g′+1}

for all g′ ≥ g and h′ ≥ h. This is to say, if (28) and (29) hold, then the rows (σ_{i}) and (τ_{i}) are interspersed beginning at term τ_{h}. The hypothesis (26) implies (28) and (29) for h = 1, so that (27) holds. ■

Theorem 6. Suppose that Q ≡ 0 mod 4. Then the fixed-j array for Q is a dispersion.

Proof: Let {d(g, h} be the fixed-j array for Q, and suppose that g, g_{1}, and h are indices such that

d(g_{1}, h) < d(g, 1) < d(g_{1}, h + 1).  (30)

With reference to the lemma, we wish to prove that

d(g_{1}, h + 1) < d(g, 2) < d(g_{1}, h + 2).  (31)

Abbreviate (30) and (31) as

n < w < n′  (32)

and

n′ < w′ < n′′,  (33)

where, by Theorem 5,

n′ = un + y ⌊Q_{1}n⌋ ,
w′ = uw + y ⌊Q_{1}w⌋ ,
n′′ = 2un′ − n.

The obvious inequality

0 < u(w − n) + y(⌊Q_{1}w⌋ − ⌊Q_{1}n⌋)

easily implies n′ < w′. To prove that w′ < n′′, we appeal to (19) to see that

(u − yQ_{1})(Q_{1}n − ⌊Q_{1}n⌋) < 1,  (34)

which readily yields

unQ_{1} + yQ_{1} ⌊Q_{1}n⌋ < yQ_{1}^{2} + u ⌊Q_{1}n⌋ + 1.

The hypothesis that

w < un + y ⌊Q_{1}n⌋  (35)

implies

Q_{1}w < unQ_{1} + yQ_{1} ⌊Q_{1}n⌋ ,

so that by (34),

Q_{1}w < ynQ_{1}^{2} + u ⌊Q_{1}n⌋ + 1,

which implies

⌊Q_{1}w⌋ − u ⌊Q_{1}n⌋ < ynQ_{1}^{2}.

Multiply through by y and apply (12) to obtain

n + y ⌊Q_{1}w⌋ < u^{2}n + uy ⌊Q_{1}n⌋ ,

equivalent to

u^{2}n + uy ⌊Q_{1}n⌋ + y ⌊Q_{1}w⌋ < 2u^{2}n + 2uy ⌊Q_{1}n⌋ − n.  (36)

Returning to the hypothesis, we have

uw < u^{2}n + uy ⌊Q_{1}n⌋ ,

so that

uw + y ⌊Q_{1}w⌋ < u^{2}n + uy ⌊Q_{1}n⌋ + y ⌊Q_{1}w⌋ .

This and (36) give

uw + y ⌊Q_{1}w⌋ < 2u(un + y ⌊Q_{1}n⌋) − n,

which is w′ < n′′. To summarize, (30) implies (31). Therefore, the lemma applies, and {d(g, h)} is a dispersion. ■

5 Fixed-k Dispersions for Q ≡ 0 mod 4

Loosely speaking, if we hold k fixed instead of j, then the methods of section 4 yield another kind of dispersion. The purpose of this section is to define these fixed-k arrays and to prove that they are dispersions. Theorems 7 and 8 are similar to Theorems 4 and 5, and the fixed-k array is then defined with reference to Theorems 7 and 8. Thereafter, Example 4 using Q = 8 is presented, and then lemma of section 4 is used to prove Theorem 9, similar to Theorem 6.

Theorem 7. Suppose that Q ≡ 0 mod 4 and that n, j, k satisfy (1). Let u, y, and r be as in Theorem 4, and let

n_{1} = un + y ⌊Q_{1}n⌋ + y,  (37)
j_{1} = (Q_{1}n_{1})^{2} − ⌊Q_{1}n_{1}⌋^{2} .  (38)

Then

(j_{1} + k + 1)^{2} − 4k = Qn_{1}^{2}.  (1A)

Proof: In view of (1) and (1A), it suffices to prove that

(j + k + 1)^{2} − Qn^{2} = (j + k_{1} − 1)^{2} − Qn_{1}^{2}.  (39)

Following the method of proof of Theorem 4, we find (39) equivalent to

(j_{1} + (1 + ⌊Q_{1}n⌋)^{2} − Q_{1}^{2}n^{2} + 1)^{2} = (2 + 2 ⌊Q_{1}n⌋)^{2} + Q_{1}n_{1}^{2} − Q_{1}n^{2}
= 4(u + u ⌊Q_{1}n⌋ + yQ_{1}^{2}n)^{2}.

Taking square roots leads to

j_{1} = − ⌊Q_{1}n⌋^{2} + Q_{1}^{2}n^{2} + 2(u − 1) ⌊Q_{1}n⌋ + 2ynQ_{1}^{2}n + 2(u − 1)  (40)

as an equivalent of (39). Thus, using (36), what we must prove is that

⌊Q_{1}n_{1}⌋^{2} = Q_{1}^{2}(un + y ⌊Q_{1}n⌋ + y)^{2} + ⌊Q_{1}n⌋^{2} − Q_{1}^{2}n^{2}
−2(u − 1) ⌊Q_{1}n⌋ − 2ynQ_{1}^{2}n − 2(u − 1).  (41)

Expanding the right side of (41) and using (12) leads to factoring the right-hand side as a square, and then taking square roots leaves the following equivalent of (39):

⌊Q_{1}n_{1}⌋^{2} = u ⌊Q_{1}n⌋ + ynQ_{1}^{2} + u − 1.

Thus, in view of (37), we need only prove that

⌊Q_{1}(un + y ⌊Q_{1}n⌋ + y)⌋ = u ⌊Q_{1}n⌋ + ynQ_{1}^{2} + u − 1;

but this now follows easily from

(u − yQ_{1})(1 − ϵ) > 0,

where ϵ = Q_{1}n − ⌊Q_{1}n⌋ . ■

Theorem 8. Suppose that Q, j, k, u, y, n, and n_{1} are as in Theorem 5, and let

n_{2} = un_{1} + y ⌊Q_{1}n_{1}⌋ + y.  (42)

Then

n_{2} = 2un_{1} − n.  (21)

A proof similar to that of Theorem 7 is omitted. We do note, however, that (42) and (21) yield

n = un_{1} − y ⌊Q_{1}n_{1}⌋ − y,

an inversion formula for (37), as (22) is for (8).

We are now in a position to define, by construction, the fixed-k array for Q. Each n is uniquely represented as in (1) by a pair (j, k), which we write as (j_{n}, k_{n}). By Theorem 7, for each k_{n}, there are infinitely many pairs (n′, j′) such that (1) and (2) hold; that is,

(j_{n′} + k_{n} + 1)^{2} − 4k_{n} = Q(n′)^{2}.  (46)

Let S_{1} be the set of all n′ for which (1A) holds for n = 1 and some j_{n′}. By Theorem 7, n_{1} = u + y ⌊Q_{1}⌋ ∈ S_{1}. (Note that in (46),

k_{1} = ⌊1 + \sqrt{Q}/2⌋^{2} − Q/4,

this being the “fixed k” used to define S_{1}). By Theorem 8, the numbers given by the recurrence relation

x_{i} = 2ux_{i−1} − x_{i−1},

with initial values x_{1} = 1 and x_{2} = n_{1}, all lie in S_{1}. Possibly they comprise all of S_{1}, but if not, let w be the least number in S_{1} that is not an x_{i}. By Theorems 7 and 8, we obtain another recurrence sequence {w_{i}} lying in S_{1}. If S_{1} contains a number not in {x_{i}} and not in {w_{i}}, the production of recurrence sequences with all terms in S_{1} can be continued inductively, so that S_{1} is partitioned into a set of such sequences. Next, let υ be the least positive integer not in S_{1}, and let S_{2} be the set of all υ′ for which (46) holds for n = υ and some k_{υ}′. Again Theorems 7 and 8 apply, so that S_{2} is partitioned into a set of recurrence sequences.

Continuing in this manner, the set of all positive integers is partitioned into sets S_{i}, which are themselves partitioned into sets of recurrence sequences. Next, arrange these sequences so that their first terms form an increasing sequence, thus producing an array of all the positive integers, with increasing first column, and whose rows all satisfying the recurrence relation x_{i} = 2ux_{i−1} − x_{i−1}. This array is the fixed-k array.

Example 4. The fixed-k array for Q = 8. (This is \underline{A120861} in [3].)

1 7 41 239 1393 ⋯
2 12 70 408 2378
3 19 111 647 3771
4 24 140 816 4756
6 31 181 1055 6149
7 36 210 1224 7134
8 48 280 1632 9512
9 53 309 1801 10497
11 60 350 2040 11890
12 65 379 2209 12875
13 77 449 2617 15253
⋮

Theorem 9. Suppose that Q ≡ 0 mod 4. Then the fixed-k array for Q is a dispersion.

A proof using

n′ = un + y ⌊Q_{1}n⌋ + y,
w′ = uw + y ⌊Q_{1}w⌋ + y,
n′′ = 2un′ − n

is very similar to that of Theorem 6 and is omitted.

6 Dispersions for Q ≡ 1 mod 4

If Q ≡ 1 mod 4, the parity of n leads to two cases, as in Theorem 2, and to more subtle results of the sort given in Theorems 4 and 5 (and Theorems 7 and 8). We offer the following conjectures:

Conjecture 1. Suppose that Q ≡ 1 mod 4 and that n, j, k satisfy (2). Let u be the least positive integer x such that

x^{2} − 4 = Qy^{2}

for some positive integer y, let

r = (u + y\sqrt{Q})/2,
n_{1} = ⌊rn⌋ − ⌊yf(n)⌋ ,

where f(n) denotes the fractional part of (1 + \sqrt{Q})n/2, and let

k_{1} = \{ \begin{matrix}(⌊1/2 + Q_{1}n_{1}⌋ + 1/2)^{2} − (Q_{1}n_{1})^{2} & if n_{1} is odd, \\ (1 + ⌊Q_{1}n_{1}⌋)^{2} − (Q_{1}n_{1})^{2} & if n_{1} is even. \end{matrix}

Then

(j + k_{1} − 1)^{2} + 4j = Qn_{1}^{2}.

Moreover, if

n_{2} = ⌊rn_{1}⌋ − ⌊yf(n_{1})⌋ ,

then the recurrence (21) holds.

Conjecture 1 depends on the existence of the pairs (u, y). Regarding u and y as sequences with terms u(n) and y(n), where n = (Q − 1)/4, we note that u and y are registered in [3] as \underline{A077428} and \underline{A078355}. Several initial terms are shown here:

\begin{matrix}Q & 5 & 13 & 17 & 21 & 29 & 33 & 37 & 41 & 45 \\ u & 3 & 11 & 66 & 5 & 27 & 46 & 146 & 4098 & 7 \\ y & 1 & 3 & 16 & 1 & 5 & 8 & 24 & 640 & 1 \end{matrix}

Conjecture 2. Suppose that Q ≡ 1 mod 4 and that n, j, k satisfy (1). Let u, y, r be as in Conjecture 1, let

n_{1} = ⌊rn⌋ − ⌊yf(n)⌋ + y,

where f(n) denotes the fractional part of (1 + \sqrt{Q})n/2, and let

j_{1} = \{ \begin{matrix}(Q_{1}n_{1})^{2} − (⌊1/2 + Q_{1}n_{1}⌋ − 1/2)^{2} & if n_{1} is odd, \\ (Q_{1}n_{1})^{2} − ⌊Q_{1}n_{1}⌋^{2} & if n_{1} is even. \end{matrix}

Then

(j_{1} + k + 1)^{2} − 4k = Qn_{1}^{2}.

Moreover, if

n_{2} = ⌊rn_{1}⌋ − ⌊yf(n_{1})⌋ + y,

then the recurrence (21) holds.

Assuming the two conjectures valid, we construct fixed-j and fixed-k arrays exactly as in sections 4 and 5, and we conjecture that they are dispersions.

Example 5. The fixed-j array for Q = 13.

1 10 109 1189 ⋯
2 20 218 2378
3 30 327 3567
4 43 469 5116
5 53 578 6305
6 63 687 7494
7 76 829 9043
8 86 938 10232
9 96 1047 11421
11 119 1298 14159

⋮

Example 6. The fixed-k array for Q = 13.

1 13 142 1549 ⋯
2 23 251 2738
3 33 360 3927
4 46 502 5476
5 56 611 6665
6 66 720 7854
7 79 862 9403
8 89 971 10592
9 99 1080 11781
10 112 1222 13330
11 122 1331 14519

⋮

7 Examples

This section consists of Examples 7-14 illustrating Theorems 1 and 2 for small values of Q, followed by fractal sequences associated with the fixed-j and fixed-k arrays for Q = 5.

Example 7. Taking Q = 8 in Theorem 1, for each n, there is a unique pair (j, k) = (j(n), k(n)) such that (j + k + 1) − 4k = 8n^{2}. The sequences j and k are given by

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & ⋯ \\ j & 1 & 4 & 2 & 7 & 1 & 8 & 17 & 7 & 18 & 4 & 17 & 32 & 14 & ⋯ \\ k & 2 & 1 & 7 & 4 & 14 & 9 & 2 & 16 & 7 & 25 & 14 & 1 & 23 & ⋯ \end{matrix}

The sequences j and k appear in [3] as \underline{A087056} and \underline{A087059}, respectively.

Example 8. Taking Q = 12 in Theorem 1, for each n, there is a unique pair (j, k) = (j(n), k(n)) such that (j + k + 1) − 4k = 12n^{2}. The sequences j and k are given by

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & ⋯ \\ j & 2 & 3 & 2 & 2 & 11 & 8 & 3 & 23 & 18 & 11 & 2 & 32 & 23 & ⋯ \\ k & 1 & 4 & 9 & 1 & 6 & 13 & 22 & 4 & 13 & 24 & 37 & 9 & 22 & ⋯ \end{matrix}

The sequences j and k appear in [3] as \underline{A120864} and \underline{A120865}, respectively.

Example 9. Taking Q = 20 in Theorem 1, for each n, there is a unique pair (j, k) = (j(n), k(n)) such that (j + k + 1) − 4k = 20n^{2}. The sequences j and k are given by

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & ⋯ \\ j & 1 & 4 & 9 & 16 & 4 & 11 & 20 & 31 & 5 & 16 & 29 & 44 & 4 & ⋯ \\ k & 4 & 5 & 4 & 1 & 19 & 16 & 11 & 4 & 36 & 29 & 20 & 9 & 55 & ⋯ \end{matrix}

The sequences j and k appear in [3] as \underline{A120866} and \underline{A120867}, respectively.

Example 10. Taking Q = 5 in Theorem 2, for each n, there is a unique pair (j, k) = (j(n), k(n)) such that (j + k + 1) − 4k = 5n^{2}. The sequences j and k are given by

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & ⋯ \\ j & 1 & 1 & 5 & 4 & 1 & 9 & 5 & 16 & 11 & 4 & 19 & 11 & 1 & ⋯ \\ k & 1 & 4 & 1 & 5 & 11 & 4 & 11 & 1 & 9 & 19 & 5 & 16 & 29 & ⋯ \end{matrix}

The sequences j and k appear in [3] as \underline{A005752} and \underline{A120868}, respectively.

Example 11. Taking Q = 13 in Theorem 2, for each n, there is a unique pair (j, k) = (j(n), k(n)) such that (j + k + 1) − 4k = 13n^{2}. The sequences j and k are given by

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & ⋯ \\ j & 1 & 4 & 9 & 3 & 9 & 17 & 3 & 12 & 23 & 1 & 13 & 27 & 43 & ⋯ \\ k & 3 & 3 & 1 & 12 & 9 & 4 & 23 & 17 & 9 & 36 & 27 & 16 & 3 & ⋯ \end{matrix}

The sequences j and k appear in [3] as \underline{A120869} and \underline{A120870}, respectively.

Example 12. The table shows, in row g and column h, the unique pair (j, k) corresponding to the fixed-j array {d(g, h)} for Q = 8; i.e., (j + k + 1)^{2} − 4k = 8n^{2}, where n = d(g, h) is as in Example 3:

(1, 2) (1, 14) (1, 82) (1, 478) ⋯
(4, 1) (4, 25) (4, 161) (4, 953)
(2, 7) (2, 47) (2, 279) (2, 1631)
(7, 4) (7, 56) (7, 356) (7, 2104)
(9, 6) (9, 89) (9, 553) (9, 3257)
⋮

The values of j, fixed for each row, form the sequence \underline{A120871}:

(1, 4, 2, 7, 8, 17, 7, 18, 17, 32, 14, 31, 9, 28, 23, 46, 16, 41, 34, 63, 25, 56, 14, 47, …).

These numbers are terms of the j-sequence in Example 7, but without duplicates.

Example 13. The table shows, in row g and column h, the unique pair (j, k) corresponding to the fixed-k array {d(g, h)} for Q = 8; i.e., (j + k + 1)^{2} − 4k = 8n^{2}, where n = d(g, h) is as in Example 4:

(1, 2) (17, 2) (43, 2) (673, 2) ⋯
(4, 1) (32, 1) (196, 1) (1152, 1)
(2, 7) (46, 7) (306, 7) (1822, 7)
(7, 4) (63, 4) (391, 4) (2303, 4)
(1, 14) (72, 14) (497, 14) (2969, 14)
⋮

The values of k, fixed for each column, form the sequence \underline{A120872}:

(2, 1, 7, 4, 14, 9, 16, 7, 25, 14, 23, 8, 34, 17, 47, 28, 41, 18, …).

These numbers are terms of the k-sequence in Example 7, but without duplicates.

Example 14. The unique pair (j, k) = (j(n), k(n)) such that

(j + k + 1)^{2} − 4k = 5n^{2}

is given in Example 10. If the duplicates in {j(n)} are expelled, the remaining sequence gives the j values for the fixed-j array for Q = 5 (cf., Example 12); this remaining sequence appears to be essentially \underline{A022344}, described as “Allan Wechsler’s ‘J determinant’ sequence”. To compare the two sequences, check successive terms of \underline{A022344} and \underline{A005742}.

We conclude with a few notes about the case Q = 5, the least Q covered by Theorem 2. The fixed-j array is the Wythoff difference array (\underline{A080164} in [3]) and the fixed-k array is the Fraenkel array (\underline{A038150}). These and their relationship to the equation (j+k+1)^{2}−4k = 5n^{2} are discussed in [2].

As noted in [4], there is a fractal sequence associated with every dispersion. Specifically, if d(g, h) is the general term of the dispersion, and we define f(n) to be the value of g for which n = d(g, h), then f is the associated fractal sequence. (A fractal sequence contains itself as a proper subsequence; e.g., if you delete the first occurrence of each positive integer in f, the remaining sequence is f; iterating this procedure shows that the sequence properly contains itself infinitely many times.)

Example 15. The fractal sequence associated with the Wythoff difference array \{d(g, h)\} is \underline{A120873}:

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

Example 16. The fractal sequence associated with the Fraenkel array {d(g, h)} is \underline{A120874}:

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

References

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

[2] Clark Kimberling, The equation m^{2} − 4k = 5n^{2} and unique representations of positive integers, submitted.

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

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

[4] N. J. A. Sloane, Classic sequences in the On-Line Encyclopedia of Integer Sequences, Part 1, The Wythoff Array and The Para-Fibonacci Sequence.

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11D09, 11D85 . Keywords: Beatty sequence, complementary equation, dispersion, interspersion, Pell equation, recurrences.

(Concerned with sequences \underline{A005752}, \underline{A033313}, \underline{A033317}, \underline{A038150}, \underline{A077428}, \underline{A078355}, \underline{A080164}, \underline{A087076}, \underline{A087079}, \underline{A098021}, \underline{A120858}, \underline{A120859}, \underline{A120860}, \underline{A120861}, \underline{A120862}, \underline{A120863}, \underline{A120864}, \underline{A120865}, \underline{A120866}, \underline{A120867}, \underline{A120868}, \underline{A120869}, \underline{A120870}, \underline{A120871}, \underline{A120872}, \underline{A120873}, and \underline{A120874}. )

Received July 10 2006; revised version received February 20 2007. Published in Journal of Integer Sequences, March 13 2007.

Return to Journal of Integer Sequences home page.