Binary Recurrences for which Powers of Two are Discriminating Moduli

Adriaan A. de Clercq

Department of Mathematics and Applied

Mathematics University of Pretoria

Private Bag X20 Hatfield 0028 South Africa

adriaandeclercq1998@gmail.com

Florian Luca School of Maths Wits University

1 Jan Smuts Avenue Braamfontein 2000

Johannesburg South Africa

and

Centro de Ciencias Matemáticas UNAM Morelia Mexico

florian.luca@wits.ac.za

Lilit Martirosyan

Department of Mathematics and Statistics University of North Carolina, Wilmington

601 South College Road Wilmington, NC 28403-5970

USA

martirosyanl@uncw.edu

Maria Matthis Department of Mathematics

Katharineum zu Lübeck

Königsstraße 27-31

23552 Lübeck

Germany

matthima@katharineum.de

Pieter Moree

Max-Planck-Institut für Mathematik Vivatsgasse 7 D-53111 Bonn

Germany

moree@mpim-bonn.mpg.de

Max A. Stoumen

Department of Mathematics and Statistics University of North Carolina, Wilmington

601 South College Road Wilmington, NC 28403-5970

USA

mas5084@uncw.edu

Melvin Weiß Department of Mathematics

Universität Bonn Endenicher Allee 60

53115 Bonn Germany

melvin@weissprivat.de

Abstract Given a sequence w = (w_{n})_{n≥0} of distinct positive integers w_{0}, w_{1}, w_{2}, … and any positive integer n, we define the discriminator function D_{w}(n) to be the smallest positive integer m such that w_{0}, …, w_{n−1} are pairwise incongruent modulo m. In this paper, we classify all binary recurrent sequences w consisting of different integer terms such that D_{w}(2^{e}) = 2^{e} for every e ≥ 1. For all of these sequences it is expected that one can actually give a fairly simple description of D_{w}(n) for every n ≥ 1. For one infinite family of such sequences this has already been done by Faye, Luca, and Moree, and for another by Ciolan and Moree.

1 Introduction

The discriminator sequence of a sequence w = (w_{n})_{n≥0} of distinct integers is the sequence (D_{w}(n))_{n≥0} given by

D_{w}(n) = min{m ≥ 1 : w_{0}, …, w_{n−1} are pairwise distinct modulo m}.

In other words, D_{w}(n) is the smallest integer m that allows one to discriminate (tell apart) the integers w_{0}, …, w_{n−1} on reducing them modulo m. If not all integers are distinct, but say w_{0}, …, w_{k}, then we can define D_{w}(j) for j = 1, …, k + 1. Obviously D_{w}(n) is nondecreasing as a function of n. Note that since w_{0}, …, w_{n−1} are in n distinct residue classes modulo D_{w}(n), we must have D_{w}(n) ≥ n. On the other hand clearly

D_{w}(n) ≤ max{w_{0}, …, w_{n−1}} − min{w_{0}, …, w_{n−1}} + 1.

The main problem is to give an easy description or characterization of D_{w}(n). In many cases such a characterization does not seem to exist.

If w_{j} is a polynomial in j, the behavior of the discriminator is fairly well understood. See Moree [7], Zieve [11], and the references therein.

An intensively studied class of sequences is that of binary recurrent sequences, cf. the book by Everest et al. [4]. For a generic binary recurrent sequence there is currently no meaningful characterization of its discriminator. An example is provided by the discriminator for the Fibonacci sequence (see Table 1). However, if we have

D_{w}(2^{e}) = 2^{e} for every e ≥ 1,  (1)

the discriminator behavior tends to be much simpler. It is easy to see that then D_{w}(n) < 2n. This allows one to exclude many potential discriminator values. Indeed, in general discriminator characterizations for a fixed n proceed by excluding all integers different from D_{w}(n) as values. If (1) holds, then typically many powers of two occur as values (cf. Table 2). All known binary recurrent discriminators, described in Families 1 and 2 below, satisfy (1). Thus, it is natural to ask for a classification of all binary recurrent sequences (w_{n})_{n≥0} such that (1) is satisfied. Note that for any such sequence the terms w_{n} must be distinct.

Our main result completely answers this question.

Theorem 1. For integers w_{0}, w_{1}, p and q, let (w_{n})_{n≥0} be the sequence defined by

w_{n+2} = pw_{n+1} + qw_{n} for all n ≥ 0.  (2)

If w_{0} + w_{1} is even and k ≥ 1, then #{w_{n} (mod 2^{k}) : 0 ≤ n ≤ 2^{k} − 1} < 2^{k}. If (p mod 4, q mod 4) = (2, 3) and w_{0} + w_{1} is odd, then D_{w}(2^{k}) = 2^{k} for every k ≥ 1. If (p mod 4, q mod 4) ≠ (2, 3) and k ≥ 3, then #{w_{n} (mod 2^{k}) : 0 ≤ n ≤ 2^{k} − 1} < 2^{k}.

Representing the residue classes modulo m by \overline{a}, with 0 ≤ a ≤ m − 1, we can reformulate property (1) as saying that the map from ℤ/mℤ to ℤ/mℤ given by \overline{a} ↦ \overline{u_{a}} is a permutation for every m that is a power of two.

We next describe the binary recurrent sequences for which the discriminator has been characterized. They fall into two families. Theorem 1 shows at a glance that for all of them (1) is satisfied.

Family 1. In Faye et al. [5], and its continuation by Ciolan et al. [2], the discriminator D_{U(k)}(n) is studied, where the Shallit sequence U(k) is given by U(k) = (U_{n}(k))_{n≥0} with U_{0}(k) = 0, U_{1}(k) = 1 and

U_{n+2}(k) = (4k + 2)U_{n+1}(k) − U_{n}(k)

for all n ≥ 0. By Theorem 1, we have D_{U(k)}(2^{e}) = 2^{e} for every e ≥ 1.

Family 2. Let q ≥ 5 be a prime and put q^{∗} = (−1)^{(q−1)/2}·q. The sequence u_{q}(1), u_{q}(2), …, with

u_{q}(j) = \frac{3^{j} − q^{∗}(−1)^{j}}{4} ,

we call the Browkin-Sălăjan sequence for q. The sequence u_{q} satisfies the recursive relation u_{q}(j) = 2u_{q}(j − 1) + 3u_{q}(j − 2) for j ≥ 3, with initial values

u_{q}(1) = (3 + q^{∗})/4 and u_{q}(2) = (9 − q^{∗})/4.

We denote its discriminator by D_{q}. In the context of the discriminator, the sequence u_{5} (2, 1, 8, 19, 62, 181, 548, 1639, 4922, …) was first considered by Sabin Sălăjan during an internship carried out in 2012 under the guidance of Moree (for this reason we call it the Sălăjan sequence). Disregarding signs this is sequence \underline{A084222}. Moree and Zumalacárregui [8] determined D_{5}(n) (cf. Table 2).

Theorem 2. Let n ≥ 1 be an arbitrary integer. Let e be the smallest integer such that 2^{e} ≥ n and f be the smallest integer such that 5^{f} ≥ 5n/4. Then D_{5}(n) = min{2^{e}, 5^{f}}.

More recently Ciolan and Moree [3] completely characterized D_{q} for arbitrary primes q > 5. Noting that u_{q}(1)+u_{q}(2) = 3, one sees that Theorem 1 applies and hence D_{q}(2^{e}) = 2^{e} for every e ≥ 1.

In order to prove Theorem 1, we will deal with the special case where w is a Lucas sequence first in Section 3. In the general case, we express w as a linear combination of a Lucas and a shifted Lucas sequence (Section 4). Our arguments require some consideration of the two divisibility of binomial coefficients (Section 2).

Beyond the polynomial and the recurrence sequence case there is very little known. Haque and Shallit [6] considered the discriminator for k-regular sequences. For these also property (1) is satisfied. Sun [10] made some conjectures regarding the discriminator for various sequences.

2 Preliminaries

We recall a celebrated result of Kummer, cf. Ribenboim [9, pp. 30–33].

Theorem 3 (Kummer, 1852). Let p be a prime number. The exponent of p in \binom{n}{m} is the number of base p carries when summing m with n − m in base p.

Here and in what follows we write ν_{2}(a) for the exponent of 2 in the factorization of the integer a.

Lemma 4. We have

ν_{2} (\binom{ℓ}{k}2^{3k}) > ν_{2}(2ℓ)

for all k ≥ 1. Further,

ν_{2} (\binom{2^{k}}{ℓ}2^{ℓ}) ≥ k + 3

for ℓ = 3 and ℓ ≥ 5.

Proof. We use Theorem 3 with p = 2. For the first inequality, we note that it is clear for k = 1, so we may assume that k ≥ 2. Write ℓ = 2^{ℓ_{0}}ℓ_{1} with integers ℓ_{0} ≥ 0 and ℓ_{1} odd. The inequality is clear for ℓ_{0} ≤ 1. It is also clear if k > (ℓ_{0} + 1)/3. So, we may assume that k ≤ (ℓ_{0} + 1)/3. Write k = 2^{k_{0}}k_{1}, where k_{0} ≥ 0 and k_{1} is odd. Then k_{0} < k ≤ (ℓ_{0} + 1)/3 < ℓ_{0}. It follows that by summing up k with ℓ − k, we have at least ℓ_{0} − k_{0} carries in base 2. Thus,

ν_{2} (\binom{ℓ}{k}2^{3k}) ≥ (ℓ_{0} − k_{0}) + 3k > ℓ_{0} + 2k ≥ ℓ_{0} + 2,

which is what we wanted to prove.

We will now prove the second inequality. Assume first that ℓ ∈ [3, 2^{k} − 1]. Then the number of carries from summing up ℓ with 2^{k} − ℓ is, by the previous argument, k − ℓ_{0}, where again ℓ = 2^{ℓ_{0}}ℓ_{1} with ℓ_{1} odd. Hence,

ν_{2} (\binom{2^{k}}{ℓ}2^{ℓ}) = k − ℓ_{0} + ℓ.

This is at least k + 3 if ℓ ≥ 3 is odd (since then ℓ_{0} = 0). It is also at least k − ℓ_{0} + 2^{ℓ_{0}} > k + 3 if ℓ_{0} ≥ 3. If ℓ_{0} = 1, then ℓ > 4 so k − ℓ_{0} + ℓ ≥ k + 3. Finally, if ℓ_{0} = 2, then since ℓ ≠ 4, we have ℓ ≥ 8 (since 4 | ℓ), so the above expression is at least k − 2 + 8 > k + 3. This was for ℓ < 2^{k}. Finally, when ℓ = 2^{k}, we have

ν_{2} (\binom{2^{k}}{ℓ}2^{ℓ}) = 2^{k} > k + 3

because k ≥ 3.

3 The Lucas sequence

A basic role in the theory of binary recurrent sequences is played by Lucas sequences.

Theorem 5. Let (u_{n})_{n≥0} be a Lucas sequence with u_{0} = 0, u_{1} = 1 and

u_{n+2} = pu_{n+1} + qu_{n}, for all n ≥ 0.

Then D_{u}(2^{k}) = 2^{k} for all k ≥ 1 if and only if (p mod 4, q mod 4) = (2, 3).

Proof. We look at {u_{0}, u_{1}, u_{2}, u_{3}} = {0, 1, p, p^{2} + q}. Since these are all the residues modulo 4, it follows that either (p mod 4, q mod 4) = (2, 3) or (p mod 4, q mod 4) = (3, 1). The second possibility entails (p mod 8, q mod 8) ∈ {(3, 1), (7, 1), (3, 5), (7, 5)} and one checks computationally that none of these 4 possibilities gives that {u_{k} (mod 8) : 0 ≤ k ≤ 7} covers all residue classes modulo 8. Thus, we must have (p mod 4, q mod 4) = (2, 3).

We consider the quadratic polynomial x^{2} − px − q having discriminant Δ = p^{2} + 4q. The equation x^{2} − px − q = 0 is the characteristic equation for the Lucas sequence. We consider the cases Δ = 0 and Δ ≠ 0 separately.

The degenerate case (Δ = 0). In this case u_{n} = np_{0}^{n−1} with p_{0} = p/2. We have {u_{0}, u_{1}, u_{2}, u_{3}} = {0, 1, 2p_{0}, 3p_{0}^{2}} and since p_{0} is odd, these are distinct modulo 4. We claim that ν_{2}(u_{m} − u_{n}) = ν_{2}(m − n) for m > n. Notice that this claim implies (1).

We have u_{m} − u_{n} ≡ m − n (mod 2). So ν_{2}(u_{m} − u_{n}) = 0 if and only if ν_{2}(m − n) = 0. Next assume that m ≡ n (mod 2). Write m = n + 2ℓ. Then

u_{m} − u_{n} = (n + 2ℓ)p_{0}^{n+2ℓ−1} − np_{0}^{n−1} = (n + 2ℓ)p_{0}^{n−1}(p_{0}^{2ℓ} − 1) + 2ℓp_{0}^{n−1}.  (3)

We can write p_{0}^{2} = 1 + 8p_{1} with p_{1} an integer. Thus,

p_{0}^{2ℓ} = (1 + 8p_{1})^{ℓ} = 1 + 8ℓp_{1} + \binom{ℓ}{2}(8p_{1})^{2} + · · · .

This in combination with (3) leads to

u_{m} − u_{n} = p_{0}^{n−1} (2ℓ + ∑_{k≥1}(n + 2ℓ)\binom{ℓ}{k}(8p_{1})^{k}) .

Since by Lemma 4 for every k ≥ 1 we have

ν_{2} (\binom{ℓ}{k}(8p_{1})^{k}) > ν_{2}(2ℓ),

we conclude that

ν_{2}(u_{m} − u_{n}) = ν_{2}(2ℓ) = ν_{2}(m − n),

thus establishing the claim.

The non-degenerate case (Δ ≠ 0). Since p = 2p_{0} and q mod 4 = 3, it follows that Δ = 4(p_{0}^{2} + q) = 16Δ_{0}, where Δ_{0} is an integer. Let

α = p_{0} + 2\sqrt{Δ_{0}} and β = p_{0} − 2\sqrt{Δ_{0}}

be the roots of x^{2} − px − q = 0. The Binet formula for u_{n} is

u_{n} = \frac{α^{n} − β^{n}}{α − β} .  (4)

While not necessary for this proof, we take a detour and prove a property concerning the index of appearance of powers of 2. In the course of proving it, we will show that 2∥v_{n}, with (v_{n})_{n≥0} the companion sequence of our Lucas sequence. This fact we actually do need in our proof.

For a positive integer m let z(m) be the order of appearance of m in the sequence (u_{n})_{n≥0}. It is the minimal positive integer k such that m | u_{k}. It is known (see Bilu et al. [1]) that this exists for all m which are coprime to q. Further, m | u_{n} if and only if z(m) | n. For us, z(2) = 2 since p ≡ 2 (mod 4) and z(4) = 4. It follows easily by induction on k that

z(2^{k}) = 2^{k}.

One way to see this is to introduce the companion sequence (v_{n})_{n≥0} given by v_{0} = 2, v_{1} = p and v_{n+2} = pv_{n+1} + qv_{n} for all n ≥ 0. By induction, we get that 2∥v_{n} for all n ≥ 0. The Binet formula for v_{n} is

v_{n} = α^{n} + β^{n} for all n ≥ 0.  (5)

We have u_{2n} = u_{n}v_{n} by the Binet formulas (4) and (5). We are now ready to show that z(2^{k}) = 2^{k}. Assume that k ≥ 3 and that 2^{k} | u_{n}. This implies that n = 2^{ℓ}n_{1} for some integers ℓ and n, with ℓ ≥ 2 and n_{1} odd. Now we use repeatedly the formula u_{2m} = u_{m}v_{m} for m = n/2, n/4, …, resulting in

u_{n} = u_{2^{ℓ}n_{1}} = v_{2^{ℓ−1}n_{1}}v_{2^{ℓ−2}n_{1}} ⋯ v_{n_{1}}u_{n_{1}}.

Since v_{2^{i}n_{1}} ≡ 2 (mod 4) for i = 0, 1, …, ℓ − 1 and u_{n_{1}} is odd, we infer that

ν_{2}(u_{2^{ℓ}n_{1}}) = ℓ.

It follows that k ≥ ℓ. In particular, z(2^{k}) = 2^{k}.

Next we show that

u_{n+2^{k}} ≡ u_{n} + 2^{k} (mod 2^{k+1})  (6)

for all k ≥ 1. One checks it easily by hand for k = 1 and n = 0, 1 as well as for k = 2 and n = 0, 1, 2, 3. Assume next k ≥ 3. In what follows, for three algebraic integers a, b, c, we write a ≡ b (mod c) if (a − b)/c is an algebraic integer. We have

α^{2^{k}} = (p_{0} + 2\sqrt{Δ_{0}})^{2^{k}} =p_{0}^{2^{k}} + 2^{k}p_{0}^{2^{k}−1}(2\sqrt{Δ_{0}}) + \binom{2^{k}}{2}p_{0}^{2^{k}−2}(2\sqrt{Δ_{0}})^{2}
+\binom{2^{k}}{4}p_{0}^{2^{k}−4}(2\sqrt{Δ_{0}})^{4} + ∑_{\begin{matrix}ℓ≥3 \\ ℓ≠4 \end{matrix}} \binom{2^{k}}{ℓ}p_{0}^{2^{k}−ℓ}(2\sqrt{Δ_{0}})^{ℓ}.

Then, by Lemma 4,

α^{2^{k}} ≡ p_{0}^{2^{k}} + 2^{k}p_{0}^{2^{k}−1}(2\sqrt{Δ_{0}}) + \binom{2^{k}}{2}p_{0}^{2^{k}−2}(2\sqrt{Δ_{0}})^{2} + \binom{2^{k}}{4}p_{0}^{2^{k}−1}(2\sqrt{Δ_{0}})^{4} (mod 2^{k+3}\sqrt{Δ_{0}}).

Changing α to β, the same calculation yields

β^{2^{k}} ≡ p_{0}^{2^{k}} − 2^{k}p_{0}^{2^{k}−1}(2\sqrt{Δ_{0}}) + \binom{2^{k}}{2}p_{0}^{2^{k}−2}(2\sqrt{Δ_{0}})^{2} + \binom{2^{k}}{4}p_{0}^{2^{k}−4}(2\sqrt{Δ_{0}})^{4} (mod 2^{k+3}\sqrt{Δ_{0}}).

Thus,

α^{n+2^{k}} − β^{n+2^{k}} ≡ α^{n} (p_{0}^{2^{k}} + 2^{k}p_{0}^{2^{k}−1}(2\sqrt{Δ_{0}}) + \binom{2^{k}}{2}p_{0}^{2^{k}−2}(2\sqrt{Δ_{0}})^{2} + \binom{2^{k}}{4}p_{0}^{2^{k}−4}(2\sqrt{Δ_{0}})^{4})

− β^{n} (p_{0}^{2^{k}} − 2^{k}p_{0}^{2^{k}−1}(2\sqrt{Δ_{0}}) + \binom{2^{k}}{2}p_{0}^{2^{k}−2}(2\sqrt{Δ_{0}})^{2} + \binom{2^{k}}{4}p_{0}^{2^{k}−4}(2\sqrt{Δ_{0}})^{4})

≡ p_{0}^{2k}(α^{n} − β^{n}) + 2^{k}p_{0}^{2^{k}−1}(2\sqrt{Δ_{0}})(α^{n} + β^{n})

+ \binom{2^{k}}{2}p_{0}^{2^{k}−2}(2\sqrt{Δ_{0}})^{2}(α^{n} − β^{n})

+ \binom{2^{k}}{4}p_{0}^{2^{k}−4}(2\sqrt{Δ_{0}})^{4}(α^{n} − β^{n}) (mod 2^{k+3}\sqrt{Δ_{0}}).

Dividing across by α − β (which is equal to 4\sqrt{Δ_{0}}), we obtain

\begin{aligned}u_{n+2^{k}} & ≡ p_{0}^{2^{k}}u_{n} + 2^{k}p_{0}^{2^{k}−1}(v_{n}/2) + \binom{2^{k}}{2}p_{0}^{2^{k}−2}(4Δ_{0})u_{n} \\ & + \binom{2^{k}}{4}p_{0}^{2^{k}−4}(16Δ_{0}^{2})u_{n} (mod 2^{k+1}). \end{aligned}  (7)

We have p_{0}^{2^{k}} ≡ 1 (mod 2^{k+1}) and v_{n}/2 ≡ 1 (mod 2). Finally,

\binom{2^{k}}{2}p_{0}^{2^{k}−2}(4Δ_{0}) = 2^{k+1}(2^{k} − 1)p_{0}^{2^{k}−2}Δ_{0} ≡ 0 (mod 2^{k+1}),

and also

\binom{2^{k}}{4}p_{0}^{2^{k}−4}(16Δ_{0}^{2}) = \frac{2^{k−2}(2^{k} − 1)(2^{k−1} − 1)(2^{k} − 3)}{3}2^{4}Δ_{0}^{2} ≡ 0 (mod 2^{k+1}).

We thus get from (7) that (6) holds for all k ≥ 1. This implies by induction on k that D_{u}(2^{k}) = 2^{k}.

4 The general case: the proof of Theorem 1

In the previous section we dealt with the Lucas sequence (Theorem 5). We will make crucial use of that result in order to deal with a more general recurrence (w_{n})_{n≥0} as in (2).

Proof of Theorem 1. If #{w_{n} (mod 2^{k}) : 0 ≤ n ≤ 2^{k} − 1} = 2^{k} for all k, it holds for k = 1 in particular. Thus, w_{0}, w_{1} have different parities which is equivalent to w_{0} + w_{1} being odd. This proves the first assertion. Conversely, write

w_{n} = au_{n} + bu_{n+1}.

Note that au_{n} + bu_{n+1} satisfies the same recurrence relation as w_{n}. On setting n = 0, respectively n = 1, we find b = w_{0} and a = w_{1} − pw_{0}. Thus, a + b = (w_{1} + w_{0}) − pw_{0} is odd. By (6), we obtain

w_{n+2^{k}} = au_{n+2^{k}} + bu_{n+1+2^{k}} ≡ a(u_{n} + 2^{k}) + b(u_{n+1} + 2^{k})
≡ (au_{n} + bu_{n+1}) + (a + b)2^{k} ≡ w_{n} + 2^{k} (mod 2^{k+1})

for k ≥ 1. This shows that D_{w}(2^{k}) = 2^{k} for every k ≥ 1.

It remains to prove the final assertion. Note that it is enough to prove it for k = 3. This can be done by doing a computer calculation modulo 8. We consider all integers a, b, p, q with 0 ≤ a, b, p, q ≤ 7 and compute #{w_{n} (mod 8) : 0 ≤ n ≤ 7}. It turns out that if (p mod 4, q mod 4) ≠ (2, 3), then this cardinality is < 8.

5 Tables

We tabulate the discriminator for a sequence that does not (Fibonacci sequence) and a sequence that does (Sălăjan sequence) satisfy the conditions of Theorem 1. We give the prime factorization of the values. Note the big difference in behavior.

\begin{matrix}n & D_{F} (n) & n & D_{F} (n) & n & D_{F} (n) \\ 1 & 1 & 21 − 24 & 59 & 69 − 80 & 431 \\ 2 & 2 & 25 − 26 & 79 & 81 − 113 & 3 · 197 \\ 3 & 3 & 27 − 32 & 83 & 114 − 115 & 3 · 283 \\ 4 & 5 & 33 − 35 & 2^{3} · 3 · 5 & 116 − 152 & 1039 \\ 5 & 2^{3} & 36 − 39 & 157 & 153 − 158 & 5 · 13 · 17 \\ 6 & 3^{2} & 40 − 44 & 173 & 159 − 162 & 1171 \\ 7 − 8 & 2 · 7 & 45 − 55 & 193 & 163 − 166 & 1451 \\ 9 − 11 & 3 · 5 & 56 − 59 & 311 & 167 − 184 & 3 · 487 \\ 12 − 16 & 2 · 3 · 5 & 60 − 64 & 337 & 185 − 208 & 1609 \\ 17 − 20 & 5 · 7 & 65 − 68 & 409 & 209 − 281 & 3 · 761 \end{matrix}

Table 1: \underline{A270151}: Discriminator for the Fibonacci sequence 1, 2, 3, 5, 8, 13, …

\begin{matrix}n & D_{S}(n) & n & D_{S}(n) \\ 1 & 1 & 129 − 256 & 2^{8} \\ 2 & 2 & 257 − 512 & 2^{9} \\ 3 − 4 & 2^{2} & 513 − 1024 & 2^{10} \\ 5 − 8 & 2^{3} & 1025 − 2048 & 2^{11} \\ 9 − 16 & 2^{4} & 2049 − 2500 & 5^{5} \\ 17 − 20 & 5^{2} & 2501 − 4096 & 2^{12} \\ 21 − 32 & 2^{5} & 4097 − 8192 & 2^{13} \\ 33 − 64 & 2^{6} & 8193 − 12500 & 5^{6} \\ 65 − 100 & 5^{3} & 12501 − 16384 & 2^{14} \\ 101 − 128 & 2^{7} & 16385 − 32768 & 2^{15} \end{matrix}

Table 2: Discriminator for the Sălăjan sequence 2, 1, 8, 19, 62, 181, …

Table 2 demonstrates Theorem 2.

6 Acknowledgments

The problem of characterizing the binary recurrences w such that D_{w}(2^{e}) = 2^{e} for every e ≥ 1 was posed by Moree to many interns. Eventually it was solved, in essence, independently by de Clercq, Matthis, and Weiss (interns in 2019) and Stoumen (a student of Martirosyan). Their work was completed by Luca. Ciolan kindly commented on an earlier version.

The authors, except Stoumen who has not visited the Max Planck Institute for Mathematics (yet!), are grateful for the pleasant working conditions and inspiring research atmosphere.

References

[1] Yu. Bilu, G. Hanrot, and P. M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers. With an appendix by M. Mignotte. J. Reine Angew. Math. 539 (2001), 75–122.

[2] A. Ciolan, M. Ferrari, F. Luca, and P. Moree, On the discriminator of Lucas sequences II: Effective aspects, in preparation.

[3] A. Ciolan and P. Moree, Browkin’s discriminator conjecture, Colloq. Math. 156 (2019), 25–56.

[4] G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward, Recurrence Sequences, Mathematical Surveys and Monographs 104, American Mathematical Society, 2003.

[5] B. Faye, F. Luca, and P. Moree, On the discriminator of Lucas sequences, Ann. Math. Qué. 43 (2019), 51–71.

[6] S. Haque and J. Shallit, Discriminators and k-regular sequences, Integers 16 (2016), Paper #A76.

[7] P. Moree, The incongruence of consecutive values of polynomials, Finite Fields Appl. 2 (1996), 321–335.

[8] P. Moree and A. Zumalacárregui, Salajan’s conjecture on discriminating terms in an exponential sequence, J. Number Theory 160 (2016), 646–665.

[9] P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag, 1996.

[10] Z.-W. Sun, On functions taking only prime values, J. Number Theory 133 (2013), 2794–2812.

[11] M. Zieve, A note on the discriminator, J. Number Theory 73 (1998), 122–138.

2010 Mathematics Subject Classification: Primary 11B50, Secondary 11A07, 11B39. Keywords: congruence, discriminator, binary recurrent sequence, Lucas sequence, Binet formula, permutation.

(Concerned with sequences \underline{A084222} and \underline{A270151}.)

Received March 10 2020; revised versions received September 28 2020; October 23 2020. Published in Journal of Integer Sequences, November 28 2020.

Return to Journal of Integer Sequences home page.