On Integrality and Asymptotic Behavior of the (k, l)-Göbel Sequences

Hibiki Gima, Toshiki Matsusaka^{1}, Taichi Miyazaki, and Shunta Yara

Faculty of Mathematics and Department of Mathematics Kyushu University Motooka 744, Nishi-ku, Fukuoka 819-0395 Japan

            gima.hibiki.100@s.kyushu-u.ac.jp
             matsusaka@math.kyushu-u.ac.jp
          miyazaki.taichi.478@s.kyushu-u.ac.jp
            yara.shunta.444@s.kyushu-u.ac.jp

Abstract

Recently, Matsuhira, Matsusaka, and Tsuchida revisited old studies of the integrality of k-Göbel sequences and showed that the first 19 terms are always integers for every integer k ≥ 2. In this article, we further explore two topics: Ibstedt’s (k, l)-Göbel sequences and Zagier’s asymptotic formula for the 2-Göbel sequence, and extend their results.

1 Introduction

Sloane’s collection of integer sequences [8] inspired Göbel to introduce a sequence defined by the recursion

g_{n} = \frac{1 + g_{0}^{2} + g_{1}^{2} + ⋯ + g_{n−1}^{2}}{n} ,

starting with g_{0} = 1. Despite the initial terms (g_{n})_{n} = (1, 2, 3, 5, 10, 28, 154, 3520, …) appearing to follow an integer sequence pattern, the sequence’s integrality was not immediately clear, raising doubts about its suitability for inclusion in Sloane’s collection. In 1975, Lenstra resolved this problem by showing that

1This work was supported by JSPS KAKENHI Grant Numbers JP20K14292 and JP21K18141.

g_{n} ∈ ℤ ⟺ 0 ≤ n ≤ 42.

Unfortunately, Göbel’s sequence is not an integer sequence. Nevertheless, it has since been registered as an intriguing exception in Sloane’s collection [7, \underline{A003504}]. (About its history, also see Matsuhira, Matsusaka, and Tsuchida [6]).

After that, several aspects of Göbel’s sequence were investigated. In 1990, Ibstedt [4] focused on an alternative recursion:

(n + 1)g_{n+1} = g_{n}(n + g_{n})

with the initial value g_{1} = 2, and introduced a generalization.

Definition 1. For integers k, l ≥ 2, the (k, l)-Göbel sequence g_{k,l}(n) is defined by the recursion

(n + 1)g_{k,l}(n + 1) = g_{k,l}(n)(n + g_{k,l}(n)^{k−1})

with the initial value g_{k,l}(1) = l.

We can pose the same question as Lenstra: when does its integrality break? To address the question, we introduce the notation

N_{k,l} := inf{n ∈ ℤ_{>0} : g_{k,l}(n) ∉ ℤ}  (1)

for k, l ≥ 2. Lenstra’s result is stated as N_{2,2} = 43. Then Ibstedt provided a method to compute the values of N_{k,l} and presented the list of N_{k,l} for 2 ≤ k, l ≤ 11 as follows. Here we extend the list to include cases where 2 ≤ k, l ≤ 17. We provide Mathematica codes to compute N_{k,l} in Appendix A.

In 1996, Zagier [10] considered the asymptotic behavior of Göbel’s sequence and described it as

g_{2,2}(n) ∼ C^{2^{n}}n(1 + \frac{2}{n} − \frac{1}{n^{2}} + \frac{4}{n^{3}} − \frac{21}{n^{4}} + \frac{138}{n^{5}} − \frac{1091}{n^{6}} + ⋯) (n → ∞)  (2)

without proof, where C = 1.0478314475764112295599 … is a constant (\underline{A115632}). Finch [2, Section 6.10] notes that this asymptotic formula shares the same coefficients (\underline{A116603}) as that for the sequence (s_{n}) introduced by Somos. Here, the sequence (s_{n}) is defined by the recursion

s_{n} = ns_{n−1}^{2}  (3)

starting with s_{0} = 1 (\underline{A052129}). It satisfies the relation

s_{n} ∼ σ^{2^{n}}n^{−1}(1 + \frac{2}{n} − \frac{1}{n^{2}} + \frac{4}{n^{3}} − \frac{21}{n^{4}} + \frac{138}{n^{5}} − \frac{1091}{n^{6}} + ⋯)^{−1} (n → ∞),

\begin{matrix}l\k & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ 2 & 43 & 89 & 97 & 214 & 19 & 239 & 37 & 79 & 83 & 239 & 31 & 431 & 19 & 79 & 23 & 827 \\ 3 & 7 & 89 & 17 & 43 & 83 & 191 & 7 & 127 & 31 & 389 & 109 & 431 & 7 & 79 & 83 & 683 \\ 4 & 17 & 89 & 23 & 139 & 13 & 359 & 23 & 158 & 41 & 169 & 103 & 643 & 31 & 79 & 167 & 118 \\ 5 & 34 & 89 & 97 & 107 & 19 & 419 & 37 & 79 & 83 & 137 & 31 & 431 & 19 & 41 & 23 & 59 \\ 6 & 17 & 31 & 149 & 269 & 13 & 127 & 23 & 103 & 71 & 239 & 41 & 431 & 31 & 79 & 23 & 499 \\ 7 & 17 & 151 & 13 & 107 & 37 & 127 & 37 & 103 & 83 & 239 & 101 & 167 & 19 & 79 & 13 & 59 \\ 8 & 51 & 79 & 13 & 214 & 13 & 239 & 17 & 163 & 71 & 239 & 41 & 431 & 31 & 79 & 13 & 118 \\ 9 & 17 & 89 & 83 & 139 & 37 & 191 & 23 & 103 & 23 & 239 & 41 & 431 & 47 & 79 & 29 & 177 \\ 10 & 7 & 79 & 23 & 251 & 347 & 239 & 7 & 163 & 41 & 239 & 53 & 251 & 7 & 251 & 23 & 59 \\ 11 & 34 & 601 & 13 & 107 & 19 & 461 & 37 & 79 & 31 & 389 & 101 & 479 & 19 & 79 & 13 & 59 \\ 12 & 17 & 197 & 97 & 263 & 37 & 191 & 17 & 79 & 41 & 263 & 82 & 167 & 29 & 79 & 53 & 59 \\ 13 & 17 & 151 & 23 & 263 & 37 & 127 & 37 & 158 & 31 & 137 & 61 & 431 & 19 & 41 & 83 & 271 \\ 14 & 43 & 158 & 67 & 139 & 37 & 191 & 23 & 158 & 41 & 239 & 29 & 383 & 29 & 79 & 23 & 683 \\ 15 & 67 & 197 & 173 & 139 & 37 & 239 & 37 & 127 & 31 & 1097 & 82 & 431 & 31 & 419 & 23 & 347 \\ 16 & 59 & 151 & 157 & 107 & 59 & 359 & 37 & 103 & 46 & 137 & 29 & 431 & 29 & 79 & 23 & 607 \\ 17 & 7 & 89 & 67 & 43 & 13 & 127 & 7 & 179 & 41 & 263 & 31 & 431 & 7 & 79 & 59 & 59 \end{matrix}

Table 1: The list of N_{k,l}. As noted in OEIS (\underline{A097398}), the articles of Ibstedt [4] and Guy [3, E15] contain some mistakes in the values.

where

σ := ∏_{n=1}^{∞} n^{1/2^{n}} = 1.6616879496 …  (4)

is called the Somos constant (\underline{A112302}).

After a period of silence, in 2023, inspired by the Japanese manga “Seisu-tan” [5], Matsuhira, Tsuchida, and the second author [6] addressed the problem of determining the minimum value of N_{k,2} and showed that

min_{k≥2} N_{k,2} = 19.  (5)

Once again, Göbel’s sequence returned as a subject of research.

In this article, we combine the above results and extend them as suggested by the previous work [6] in the last remarks. First, we consider the minimum value of all N_{k,l} and show the following:

Theorem 2. We have min_{k,l≥2} N_{k,l} = 7, which implies that g_{k,l}(n) ∈ ℤ for all integers k, l ≥ 2 and 1 ≤ n ≤ 6. Moreover, we have N_{k,l} = 7 if and only if k ≡ 2 (mod 6) and l ≡ 3 (mod 7).

Secondly, we give a complete proof of Zagier’s asymptotic formula (2) and generalize it for (k, l)-Göbel sequences. Before stating the theorem, we recall the definition of asymptotic expansions.

Definition 3. Assume that the sequence (λ_{r}(n))_{r} satisfies λ_{r+1}(n) = o(λ_{r}(n)) as n → ∞, that is,

lim_{n→∞} \frac{λ_{r+1}(n)}{λ_{r}(n)} = 0

for every r. For a sequence (c_{n})_{n}, we call (a_{r})_{r} its asymptotic coefficients and write

c_{n} ∼ ∑_{r=0}^{∞} a_{r}λ_{r}(n)

if

c_{n} − ∑_{r=0}^{R} a_{r}λ_{r}(n) = O(λ_{R+1}(n)) (n → ∞)

holds for every R ≥ 0.

By adapting the sequence λ_{r}(n) = C_{k,l}^{k^{n}}n^{\frac{1}{k−1}} n^{−r}, we obtain the following asymptotic expansion.

Theorem 4. For integers k, l ≥ 2, there exist a constant C_{k,l} > 1 and a sequence (a_{k,r})_{r} such that

g_{k,l}(n) ∼ C_{k,l}^{k^{n}}n^{\frac{1}{k−1}} (1 + ∑_{r=1}^{∞} \frac{a_{k,r}}{n^{r}} ) (n → ∞).

The constant C_{k,l} and the sequence (a_{k,r})_{r} is explicitly defined in Proposition 10 and Theorem 15, respectively.

In Section 2 and Section 3, we give proofs of the above theorems, respectively. In Section 4, we provide further observations on a variability of g_{k,l}(n) modulo a higher power of p.

2 How long can (k, l)-Göbel sequences remain integers?

In this section, we provide a proof of Theorem 2, drawing on Ibstedt’s method for computing N_{k,l} and the argument presented by Matsuhira, Matsusaka, and Tsuchida [6]. First, we prepare some notation.

2.1 Notation and key properties

Let P be the set of all prime numbers. For each p ∈ P, we let ℤ_{(p)} denote the localization of ℤ at the prime ideal (p), that is, ℤ_{(p)} = {a/b ∈ ℚ : p ∤ b}. By the fact that

⋂_{p∈P} ℤ_{(p)} = ℤ,  (6)

for x ∈ ℚ, we have x ∈ ℤ if and only if x ∈ ℤ_{(p)} for all p ∈ P. Let ν_{p}(x) be the p-adic valuation of x ∈ ℚ. More precisely, for an integer n, ν_{p}(n) is the exponent of the largest power of p that divides n, and it is extended to rational numbers by ν_{p}(a/b) = ν_{p}(a) − ν_{p}(b). The following lemma is the key for our proof of Theorem 2. For convenience, we also include the cases when k = 1 or l = 1, in which g_{k,l}(n) is a constant sequence.

Lemma 5. Let N be a positive integer. For each p ∈ P, we put r = ν_{p}(N!). Let k, k_{1}, k_{2}, l, l_{1}, l_{2} ≥ 1 and 1 ≤ n ≤ N be integers. Then we have the following.

(1) If p > N, then g_{k,l}(N) ∈ ℤ_{(p)}.

(2) If g_{k,l}(n) ∉ ℤ_{(p)}, then g_{k,l}(n + 1) ∉ ℤ_{(p)}.

(3) Assume that p ≤ N, that is, r ≥ 1. If k_{1}, k_{2} ≥ r and k_{1} ≡ k_{2} (mod φ(p^{r})), then g_{k_{1},l}(n) ∈ ℤ_{(p)} if and only if g_{k_{2},l}(n) ∈ ℤ_{(p)}, where φ(n) is the Euler totient function. Moreover, in this case, we have g_{k_{1},l}(n) − g_{k_{2},l}(n) ∈ p^{r−ν_{p}(n!)}ℤ_{(p)}.

(4) Assume that p ≤ N. If l_{1} ≡ l_{2} (mod p^{r}), then g_{k,l_{1}}(n) ∈ ℤ_{(p)} if and only if g_{k,l_{2}}(n) ∈ ℤ_{(p)}. Moreover, in this case, we have g_{k,l_{1}}(n) − g_{k,l_{2}}(n) ∈ p^{r−ν_{p}(n!)}ℤ_{(p)}.

Proof.

(1) Obvious from Definition 1.

(2) If g_{k,l}(n) ∉ ℤ_{(p)}, that is, ν_{p}(g_{k,l}(n)) < 0, then we have

ν_{p}(g_{k,l}(n + 1)) = ν_{p}(g_{k,l}(n)) + ν_{p}(n + g_{k,l}(n)^{k−1}) − ν_{p}(n + 1)
= kν_{p}(g_{k,l}(n)) − ν_{p}(n + 1) < 0.

(3) follows from Euler’s theorem, (a generalization of Fermat’s little theorem), and induction on n. For the initial case, we have g_{k_{1},l}(1) = l = g_{k_{2},l}(1). Assume that the claim holds for some 1 ≤ n < N. If g_{k_{1},l}(n) ∉ ℤ_{(p)}, then both of g_{k_{1},l}(n+1) and g_{k_{2},l}(n+1) are not in ℤ_{(p)} by the induction hypothesis and (2). On the other hand, if g_{k_{1},l}(n) ∈ ℤ_{(p)}, then

(n + 1)(g_{k_{1},l}(n + 1) − g_{k_{2},l}(n + 1)) = n(g_{k_{1},l}(n) − g_{k_{2},l}(n)) + (g_{k_{1},l}(n)^{k_{1}} − g_{k_{2},l}(n)^{k_{2}}).

By the induction hypothesis, the first term is in p^{r−ν_{p}(n!)}ℤ_{(p)}. As for the second term, if g_{k_{1},l}(n) ∉ pℤ_{(p)}, then by applying Euler’s theorem, it belongs to p^{r−ν_{p}(n!)}ℤ_{(p)}. If g_{k_{1},l}(n) ∈ pℤ_{(p)}, then since k_{1}, k_{2} ≥ r, it is also in p^{r−ν_{p}(n!)}ℤ_{(p)}. Therefore, by dividing the both sides by (n + 1), we get g_{k_{1},l}(n + 1) − g_{k_{2},l}(n + 1) ∈ p^{r−ν_{p}((n+1)!)}ℤ_{(p)}. In particular, if g_{k_{1},l}(n + 1) ∉ ℤ_{(p)}, then g_{k_{2},l}(n + 1) ∉ ℤ_{(p)}, and vice versa.

(4) Since g_{k,l_{1}}(n) and g_{k,l_{2}}(n) satisfy the same recursion with the same initial value modulo p^{r}, the claim immediately follows in a similar manner to (3).

2.2 Proof of Theorem 2

We have to check the following two claims.

1. For integers k, l ≥ 2 and 1 ≤ n ≤ 6, g_{k,l}(n) ∈ ℤ.

2. g_{k,l}(7) ∉ ℤ if and only if k ≡ 2 (mod 6) and l ≡ 3 (mod 7).

By applying Lemma 5 with N = 7 and combining it with (6), these claims can be translated as follows.

Lemma 6. Theorem 2 is equivalent to the following claims for p = 2, 3, 5, 7.

1. For 2 ≤ k ≤ 11 and 1 ≤ l ≤ 16, we have g_{k,l}(7) ∈ ℤ_{(2)}.

2. For 2 ≤ k ≤ 7 and 1 ≤ l ≤ 9, we have g_{k,l}(7) ∈ ℤ_{(3)}.

3. For 1 ≤ k ≤ 4 and 1 ≤ l ≤ 5, we have g_{k,l}(7) ∈ ℤ_{(5)}.

4. For 1 ≤ k ≤ 6 and 1 ≤ l ≤ 7, g_{k,l}(7) ∉ ℤ_{(7)} if and only if k = 2 and l = 3.

Proof. Since it is obvious that Theorem 2 implies the claims, we now show the converse implication. By Lemma 5 (1), g_{k,l}(7) ∈ ℤ_{(p)} for every p > 7. Since the discussion remains similar for the remaining cases of p = 2, 3, 5, and 7, let us focus here on explaining the case when p = 2. By Lemma 5 (2), g_{k,l}(7) ∈ ℤ_{(2)} if and only if g_{k,l}(n) ∈ ℤ_{(2)} for all 1 ≤ n ≤ 7. By the periodicity shown in Lemma 5 (3) and (4), it is enough to show that g_{k,l}(7) ∈ ℤ_{(2)} for k = 2, 3, and 4 ≤ k < 4 + φ(2^{4}), and 1 ≤ l ≤ 2^{4}, where we note that ν_{2}(7!) = 4. This is the claim for p = 2.

Proof of Theorem 2. Since there are only a finite (and relatively small) number of cases to consider, it can be checked by using Mathematica. The codes to compute them are available in Appendix A. Alternatively, it is enough (and possible) to check that g_{k,l}(7) ∈ ℤ if and only if (k, l) ≠ (2, 3), (2, 10), (8, 3), (8, 10) for 1 ≤ k ≤ 11 and 1 ≤ l ≤ 16 because g_{k,l}(7) is not too large in these cases.

3 Zagier’s asymptotic formula and its generalization

In this section, we prove Theorem 4 by defining the constant C_{k,l} and the asymptotic coefficients a_{k,r} explicitly.

3.1 The constant C_{k,l}

We first show the monotonic behavior of C_{k,l}(n) := g_{k,l}(n)^{1/k^{n}}.

(k, l) = (2, 2)  (k, l) = (3, 2)  (k, l) = (2, 3)

Figure 1: The plots of C_{k,l}(n) for 1 ≤ n ≤ 15.

Lemma 7. For integers k, l ≥ 2 and n ≥ 1, we have C_{k,l}(n) > C_{k,l}(n + 1) > 1.

Proof. First, we check that C_{k,l}(n) > 1, that is, g_{k,l}(n) > 1 by induction on n. The initial condition is satisfied by g_{k,l}(1) = l ≥ 2. Assume that g_{k,l}(n) > 1. Then we have

g_{k,l}(n + 1) = \frac{1}{n + 1}(ng_{k,l}(n) + g_{k,l}(n)^{k}) > \frac{n + 1}{n + 1} = 1.

Next, we check for monotonicity. Since g_{k,l}(n) > 1, we have g_{k,l}(n)^{k−1} > 1, and then

\frac{1}{n + 1}(\frac{n}{g_{k,l}(n)^{k−1}} + 1) < 1.

Hence, we have

(\frac{C_{k,l}(n + 1)}{C_{k,l}(n)})^{k^{n+1}} = \frac{g_{k,l}(n + 1)}{g_{k,l}(n)^{k}} = \frac{1}{n + 1} \frac{ng_{k,l}(n) + g_{k,l}(n)^{k}}{g_{k,l}(n)^{k}} < 1,  (7)

which concludes the proof.

The above lemma shows that C_{k,l}(n) converges. We denote the limit as

C_{k,l} := lim_{n→∞} C_{k,l}(n) ≥ 1.  (8)

Next, we introduce some notation to show the strict inequality C_{k,l} > 1. For k ≥ 2, we define the k-Somos constant σ_{k} by

σ_{k} := exp ( ∑_{m=1}^{∞} \frac{log m}{k^{m}}) > 1,  (9)

(see also Sondow-Hadjicostas’s article [9] and \underline{A123852}). For a real number t_{0} > 1, we define a Somos-like sequence t_{k}(n) by the recursion:

t_{k}(n + 1) = \frac{1}{n + 1}t_{k}(n)^{k}  (10)

with the initial value t_{k}(0) = t_{0}.

Lemma 8. If t_{0} > σ_{k}, then there exists a constant c > 1 such that t_{k}(n)^{1/k^{n}} decreases monotonically and tends to c as n → ∞.

Proof. It is equivalent to show that a_{k}(n) := k^{−n} log t_{k}(n) decreases and tends to a positive constant. Since a_{k}(n) satisfies the recursion

a_{k}(n) = a_{k}(n − 1) − \frac{log n}{k^{n}}

for n ≥ 1, the sequence decreases monotonically. By our assumption, we have a_{k}(0) > log σ_{k}, which implies that

lim_{n→∞} a_{k}(n) = a_{k}(0) − ∑_{n=1}^{∞} \frac{log n}{k^{n}} > 0.

We can estimate (k, l)-Göbel sequences g_{k,l}(n) by using the sequence t_{k}(n) as follows.

Lemma 9. If l ≥ t_{0}^{k}, then g_{k,l}(n) ≥ t_{k}(n) for all n ≥ 1.

Proof. It immediately follows from induction on n. Indeed, we have g_{k,l}(1) = l ≥ t_{0}^{k} = t_{k}(1). Assume that g_{k,l}(n) ≥ t_{k}(n). Then we obtain

g_{k,l}(n + 1) > \frac{1}{n + 1}g_{k,l}(n)^{k} ≥ \frac{1}{n + 1}t_{k}(n)^{k} = t_{k}(n + 1).

Proposition 10. For integers k, l ≥ 2, the constant C_{k,l} defined in (8) satisfies C_{k,l} > 1.

Proof. We prove the claim by considering three cases.

(1) For k ≥ 3 and l ≥ 2, since σ_{3}^{3} = 1.5462 … and σ_{k}^{k} decreases monotonically, there exists a real number t_{0} > 1 such that l ≥ t_{0}^{k} > σ_{k}^{k}. For such a t_{0}, by applying Lemma 8 and Lemma 9, we obtain

C_{k,l}(n) = g_{k,l}(n)^{1/k^{n}} ≥ t_{k}(n)^{1/k^{n}} ≥ c > 1,

which implies that C_{k,l} > 1.

(2) For k = 2 and l ≥ 3, since σ_{2}^{2} = 2.7612 …, there exists a real number t_{0} > 1 such that l ≥ t_{0}^{2} > σ_{2}^{2}. By the same argument, we also obtain C_{k,l} > 1.

(3) For k = l = 2, we need to modify the argument. We define another sequence t′_{2}(n) by the same recursion as in (10) with the initial value t′_{2}(3) = 5. Then the inequality g_{2,2}(n) ≥ t′_{2}(n) for n ≥ 3 is shown in a manner similar to Lemma 9. Thus, we obtain

C_{2,2}(n) = g_{2,2}(n)^{1/2^{n}} ≥ t′_{2}(n)^{1/2^{n}}

and

lim_{n→∞} \frac{1}{2^{n}} log t′_{2}(n) = \frac{1}{2^{3}} log 5 − ∑_{n=4}^{∞} \frac{log n}{2^{n}} = 0.00395 … > 0.

Hence, we conclude that C_{2,2} > 1.

3.2 Asymptotic behavior

In the previous subsection, we defined the constant C_{k,l} > 1. By definition, we obtain

\frac{g_{k,l}(n)}{C_{k,l}^{k^{n}}} = (\frac{C_{k,l}(n)}{C_{k,l}})^{k^{n}}.  (11)

Thus, it is sufficient to evaluate the right-hand side to prove Theorem 4. The aim of this subsection is to establish a connection to a simpler sequence.

Theorem 11. For every real number R > 0, we have

exp ( ∑_{m=1}^{∞} \frac{log (m + n)}{k^{m}}) − (\frac{C_{k,l}(n)}{C_{k,l}})^{k^{n}} = O(\frac{1}{n^{R}} )

as n → ∞.

First, we prepare a lemma with the aim of proving this theorem. Let

ϵ_{k,l}(n) := ∑_{m=1}^{∞} \frac{log (m + n)}{k^{m}} − k^{n}(log C_{k,l}(n) − log C_{k,l}).

Lemma 12. We have

ϵ_{k,l}(n) = ∑_{m=1}^{∞} \frac{1}{k^{m}} log (1 + \frac{m + n − 1}{g_{k,l}(m + n − 1)^{k−1}} ) ≤ \frac{2n}{C_{k,l}^{(k−1)k^{n}}} .

Proof. By (7), we have

log C_{k,l}(m + n) − log C_{k,l}(m + n − 1) = \frac{1}{k^{m+n}} log (\frac{m + n − 1}{g_{k,l}(m + n − 1)^{k−1}} + 1) − \frac{log(m + n)}{k^{m+n}}.

By summing each side over m, we obtain

k^{n}(log C_{k,l} − log C_{k,l}(n)) = ∑_{m=1}^{∞} \frac{1}{k^{m}} log (\frac{m + n − 1}{g_{k,l}(m + n − 1)^{k−1}} + 1) − ∑_{m=1}^{∞} \frac{log(m + n)}{k^{m}},

which implies the first equality.

Next, the inequality log(1 + x) < x for x > 0 implies that

∑_{m=1}^{∞} \frac{1}{k^{m}} log (1 + \frac{m + n − 1}{g_{k,l}(m + n − 1)^{k−1}} ) < ∑_{m=1}^{∞} \frac{1}{k^{m}} \frac{m + n − 1}{g_{k,l}(m + n − 1)^{k−1}} .

Since C_{k,l}(n) ≥ C_{k,l} > 1 and g_{k,l}(n) = C_{k,l}(n)^{k^{n}}, we have

g_{k,l}(m + n − 1)^{k−1} = C_{k,l}(m + n − 1)^{(k−1)k^{m+n−1}} ≥ C_{k,l}^{(k−1)k^{n}}.

Therefore, by using m + n − 1 ≤ mn for m, n ≥ 1, we obtain

ϵ_{k,l}(n) < \frac{n}{C_{k,l}^{(k−1)k^{n}}} ∑_{m=1}^{∞} \frac{m}{k^{m}} = \frac{n}{C_{k,l}^{(k−1)k^{n}}} \frac{k}{(k − 1)^{2}} ≤ \frac{2n}{C_{k,l}^{(k−1)k^{n}}}

for k ≥ 2.

Proof of Theorem 11. By using the expression

(\frac{C_{k,l}(n)}{C_{k,l}})^{k^{n}} = exp ( ∑_{m=1}^{∞} \frac{log(m + n)}{k^{m}} − ϵ_{k,l}(n))

and the inequality e^{x} − e^{x−ϵ} ≤ ϵe^{x}, we have

exp ( ∑_{m=1}^{∞} \frac{log (m + n)}{k^{m}}) − (\frac{C_{k,l}(n)}{C_{k,l}})^{k^{n}} ≤ ϵ_{k,l}(n) exp ( ∑_{m=1}^{∞} \frac{log(m + n)}{k^{m}}).

Moreover, by applying m + n ≤ m(n + 1) for m, n ≥ 1, it is bounded by

≤ ϵ_{k,l}(n)σ_{k} · exp ( ∑_{m=1}^{∞} \frac{log(n + 1)}{k^{m}}) = ϵ_{k,l}(n)σ_{k} · (n + 1)^{\frac{1}{k−1}} ,

where σ_{k} is the k-Somos constant defined in (9). Finally, by Lemma 12, we obtain the theorem.

3.3 The asymptotic coefficients a_{k,r}

Finally, to complete the statement of Theorem 4 and its proof, we provide the asymptotic expansion of the first term of Theorem 11. First, we review the relevant parts of the studies by Sondow and Hadjicostas [9] regarding a generalization of Somos’s sequence introduced in (3). Then we establish a connection between their results and our (k, l)-Göbel sequences. To state their claims explicitly, we recall the Eulerian polynomials.

Definition 13. For any integer r ≥ 0 and t > 1, there exists a polynomial A_{r}(t) such that

∑_{m=1}^{∞} \frac{m^{r}}{t^{m}} = \frac{A_{r}(t)}{(t − 1)^{r+1}} .

We call the polynomial A_{r}(t) the Eulerian polynomial.

Example 14. The first few examples are given by A_{0}(t) = 1 and

A_{1}(t) = t,
A_{2}(t) = t^{2} + t,
A_{3}(t) = t^{3} + 4t^{2} + t,
A_{4}(t) = t^{4} + 11t^{3} + 11t^{2} + t,
A_{5}(t) = t^{5} + 26t^{4} + 66t^{3} + 26t^{2} + t.

For more examples, see \underline{A008292}.

Then the following is known.

Theorem 15 ([9, Theorem 9 and Lemma 1]). For an integer k ≥ 2, we define the sequence (a_{k,r})_{r} to be

a_{k,r} := ∑_{\begin{matrix}m_{1},...,m_{r}≥0 \\ m_{1}+2m_{2}+···+rm_{r}=r \end{matrix}} ∏_{j=1}^{r} \frac{1}{m_{j}!}(\frac{(−1)^{j−1}}{j} \frac{A_{j}(k)}{(k − 1)^{j+1}} )^{m_{j}}.  (12)

Then we have

exp ( ∑_{m=1}^{∞} \frac{log(m + n)}{k^{m}}) ∼ n^{\frac{1}{k−1}} (1 + ∑_{r=1}^{∞} \frac{a_{k,r}}{n^{r}} ) (n → ∞).

Example 16. The first several terms are calculated as follows.

a_{k,1} = \frac{k}{(k − 1)^{2}} ,
a_{k,2} = −\frac{k(k^{2} − k − 1)}{2(k − 1)^{4}},
a_{k,3} = \frac{k(2k^{4} + k^{3} − 11k^{2} + 7k + 2)}{6(k − 1)^{6}},
a_{k,4} = −\frac{k(6k^{6} + 37k^{5} − 124k^{4} + 53k^{3} + 92k^{2} − 59k − 6)}{24(k − 1)^{8}},
a_{k,5} = \frac{k(24k^{8} + 478k^{7} − 1013k^{6} − 1324k^{5} + 4411k^{4} − 2724k^{3} − 453k^{2} + 578k + 24)}{120(k − 1)^{10}}.

In particular, when k = 2, we observe that (a_{2,r})_{r=1}^{5} = (2, −1, 4, −21, 138), which matches the asymptotic coefficients in (2).

Proof of Theorem 4. We show that

\frac{g_{k,l}(n)}{C_{k,l}^{k^{n}}} − n^{\frac{1}{k−1}} (1 + ∑_{r=1}^{R} \frac{a_{k,r}}{n^{r}} ) = O(\frac{n^{\frac{1}{k−1}}}{n^{R+1}} ) (n → ∞)

for every R ≥ 0. It immediately follows by applying (11), Theorem 11, and Theorem 15.

Remark 17. Let G_{k,l}(n) := log g_{k,l}(n) denote the logarithm of the (k, l)-Göbel sequence. The recurrence relation in Definition 1 can be rewritten as

G_{n+1} = kG_{n} + F_{n},

where we define

F_{n} := log (\frac{1}{n + 1} (1 + \frac{n}{g_{k,l}(n)^{k−1}} )) .

As the reviewer noted, this recursion closely resembles the one considered by Aho and Sloane [1]. Likewise, the sequence

H_{n} := ∑_{m=1}^{∞} \frac{log(m + n)}{k^{m}}

discussed in Theorem 11 also satisfies a similar recurrence relation:

H_{n+1} = kH_{n} − log(n + 1).

Aho and Sloane analyzed the asymptotic behavior of sequences defined by recurrence relations of this form in the case of k = 2. Our analysis in Section 3 can be seen as following their approach, extending it to provide a rigorous treatment for the (k, l)-Göbel sequences.

4 Further observations

Zagier [10] observed not only the asymptotic formula but also a heuristic explaining why N_{2,2} = 43 is unexpectedly large, assuming a certain “randomness” of the values g_{2,2}(n) modulo p for 1 ≤ n < p. Inspired by his heuristic argument, we can ask the question: for any pair of integers k, l ≥ 2, does there exist (infinitely many) p ∈ P such that g_{k,l}(p) ∉ ℤ_{(p)}. For instance, g_{2,2}(p) ∉ ℤ_{(p)} holds when p = 43, 61, 67, 83, . . .. We do not have an answer to this question, but we obtained a result concerning “randomness”, which we present as a final remark.

Theorem 18. For any prime number p ∈ P and integers k, l, r ≥ 2, the set

G_{k,l,p}^{r} := {g_{k,l}(n) mod p^{r} : 1 ≤ n < p, g_{k,l}(n) ≡ 0 (mod p^{r−1})}

is a singleton {0 mod p^{r}} or has the same cardinality as {1 ≤ n < p : g_{k,l}(n) ≡ 0 (mod p^{r−1})}. Here the congruence is considered in ℤ_{(p)}.

Example 19. Let r = 2. For (k, l) = (4, 4) and p = 13, we see that g_{4,4}(1) ≢ 0 (mod 13) and g_{4,4}(n) ≡ 0 (mod 13) for 2 ≤ n ≤ 12. Moreover, we can check that all entries of

(g_{4,4}(n) mod 13^{2})_{2≤n≤12} = (130, 143, 65, 52, 156, 13, 117, 104, 26, 39, 78)

are distinct from each other.

On the other hand, for (k, l) = (3, 2) and p = 13, we see that g_{3,2}(n) ≢ 0 (mod 13) for 1 ≤ n ≤ 3 and g_{3,2}(n) ≡ 0 (mod 13^{2}) for 4 ≤ n ≤ 12. Thus, G_{3,2,13}^{2} = {0 mod 13^{2}} is a singleton.

To prove the theorem, we first show a lemma.

Lemma 20. Let k, l, r ≥ 2 be integers and p ∈ P. Assume that there exists 1 ≤ a < p and 0 ≤ b < p such that g_{k,l}(a) ≡ bp^{r−1} (mod p^{r}). Then, for every a ≤ n < p, we have

ng_{k,l}(n) ≡ abp^{r−1} (mod p^{r}).

Proof. It follows from induction on n. The first condition ag_{k,l}(a) ≡ abp^{r−1} (mod p^{r}) is clearly satisfied by our assumption. Assume that ng_{k,l}(n) ≡ abp^{r−1} (mod p^{r}) for some a ≤ n < p − 1. By definition,

(n + 1)g_{k,l}(n + 1) = g_{k,l}(n)^{k} + ng_{k,l}(n) ≡ (n^{−1}ab)^{k}p^{k(r−1)} + abp^{r−1} (mod p^{r}),

which implies that (n + 1)g_{k,l}(n + 1) ≡ abp^{r−1} (mod p^{r}) because k(r − 1) ≥ r.

Proof of Theorem 18. It is sufficient to consider the case where I := {1 ≤ n < p : g_{k,l}(n) ≡ 0 (mod p^{r−1})} ≠ ∅. Then we take a := min I and 0 ≤ b < p satisfying g_{k,l}(a) ≡ bp^{r−1} (mod p^{r}). If b = 0, then Lemma 20 tells us that g_{k,l}(n) ≡ 0 (mod p^{r}) for all n ∈ I, that is, G_{k,l,p}^{r} = {0 mod p^{r}}. We now assume that b ≠ 0. If there exist n_{1}, n_{2} ∈ I satisfying g_{k,l}(n_{1}) ≡ g_{k,l}(n_{2}) (mod p^{r}), Lemma 20 implies that

n_{1}g_{k,l}(n_{1}) ≡ abp^{r−1} ≡ n_{2}g_{k,l}(n_{2}) (mod p^{r}),

and then n_{1} = n_{2}.

As a further observation, Table 1 suggests a tendency for N_{k,l} to increase when k is prime. However, elucidating this phenomenon is a subject for future investigation.

A Methods for Computing N_{k,l}

In this appendix, we provide a method to compute N_{k,l} and the Mathematica codes we used to generate Table 1. First, we recall the following sequence g_{k,l,p,r}(n) introduced in [6].

Definition 21. Let k, l ≥ 2, r ≥ 1 be integers, and p a prime. We define b(n) = b_{p,r}(n) = r − ν_{p}(n!) and use the symbol F to represent “False”. For any positive integer n with ν_{p}(n!) ≤ r, we define g_{k,l,p,r}(n) ∈ ℤ/p^{b(n)}ℤ ∪ {F} as follows.

• Initial condition: g_{k,l,p,r}(1) = l mod p^{r} ∈ ℤ/p^{r}ℤ.

• For n ≥ 2: When g_{k,l,p,r}(n − 1) = F, g_{k,l,p,r}(n) = F.

• For n ≥ 2: When g_{k,l,p,r}(n − 1) = a mod p^{b(n−1)},

- if a(n − 1 + a^{k−1}) ≢ 0 (mod p^{ν_{p}(n)}), then g_{k,l,p,r}(n) = F.

- if a(n − 1 + a^{k−1}) ≡ 0 (mod p^{ν_{p}(n)}), then letting c ∈ ℤ such that c · (n/p^{ν_{p}(n)}) ≡ 1 (mod p^{b(n)}), we define

g_{k,l,p,r}(n) = \frac{a(n − 1 + a^{k−1})}{p^{ν_{p}(n)}} · c mod p^{b(n)}.

The recursion above, defining g_{k,l,p,r}(n), is a translation of Definition 1 modulo a power of p. Since g_{k,l}(n) ∉ ℤ_{(p)} if and only if g_{k,l,p,ν_{p}(n!)}(n) = F, the number N_{k,l} can be expressed as

N_{k,l} = inf{n ∈ ℤ_{>0} : there exists p ∈ P_{≤n} such that g_{k,l,p,ν_{p}(n!)}(n) = F}.

The following code implements this argument in Mathematica.

nu[p_, n_] := FirstCase[FactorInteger[n], {p, r_} -> r, 0];
inv[n_, M_] := If[M == 1, 1, ModularInverse[n, M]];
g[k_, l_, p_, r_, 1] := {Mod[l, p^r], r};
g[k_, l_, p_, r_, n_] :=

 g[k, l, p, r, n] =
  Module[{a, b},
   If[g[k, l, p, r, n - 1] === "F",
    "F", {a, b} = g[k, l, p, r, n - 1];
    If[Mod[a (n - 1 + a^(k - 1)), p^nu[p, n]] != 0,
     "F", {Mod[
       a (n - 1 + a^(k - 1))/p^nu[p, n] inv[n/p^nu[p, n],
         p^(b - nu[p, n])], p^(b - nu[p, n])], b - nu[p, n]}]]];
NN[k_, l_] := Module[{n}, n = 2;
  While[
   FreeQ[Table[
     g[k, l, Prime[m], nu[Prime[m], n!], n], {m, 1, PrimePi[n]}],
    "F"], n++]; n];

Here, the output g[k,l,p,r,n] = {a, b} means that g_{k,l,p,r}(n) = a mod p^{b} with b = b(n), that is, g_{k,l}(n) ≡ a (mod p^{b}), and NN[k,l] gives the value of N_{k,l}.

References

[1] A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quart. 11 (1973), 429–437.

[2] S. R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, Vol. 94, Cambridge University Press, 2003.

[3] R. K. Guy, Unsolved Problems in Number Theory, 3rd edition, Problem Books in Mathematics, Springer-Verlag, 2004.

[4] H. Ibstedt, Some sequences of large integers, Fibonacci Quart. 28 (1990), 200–203.

[5] D. Kobayashi and S. Seki, Seisu-tan 1: A strange tale of integers’ world, Nippon Hyoron Sha (in Japanese), 2023.

[6] R. Matsuhira, T. Matsusaka, and K. Tsuchida, How long can k-Göbel sequences remain integers?, to appear in Amer. Math. Monthly.

[7] N. J. A. Sloane, The on-line encyclopedia of integer sequences, https://oeis.org.

[8] N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973.

[9] J. Sondow and P. Hadjicostas, The generalized-Euler-constant function γ(z) and a generalization of Somos’s quadratic recurrence constant, J. Math. Anal. Appl. 332 (2007), 292–314.

[10] D. Zagier, Problems given at the St. Andrews Colloquium, 1996, https://

    mathshistory.st-andrews.ac.uk/EMS/Colloquium_1996/, Solution: Day 5, Problem
    3, https://mathshistory.st-andrews.ac.uk/EMS/Zagier/Solution53/.

2020 Mathematics Subject Classification: Primary 11B37; Secondary 11B50. Keywords: Göbel sequence, Somos sequence, asymptotic formula.

(Concerned with sequences \underline{A003504}, \underline{A008292}, \underline{A052129}, \underline{A097398}, \underline{A112302}, \underline{A115632}, \underline{A116603}, and \underline{A123852}.)

Received March 10 2024; revised version received October 27 2024. Published in Journal of Integer Sequences, October 29 2024.

Return to Journal of Integer Sequences home page.