# On the Local Minima of the Order of Appearance Function

Authors: Florian Luca; Thato Mosima
Journal: International Journal of Mathematics and Mathematical Sciences
 (2015)

---

## Abstract

The order of appearancez
(
n
) of the positive integer n is the smallest positive integer k such that n divides F
k, the kth member of the Fibonacci sequence. In this paper, we improve upon some results from (Marques, 2011) concerning local minima of z
(
n
).


---

## Body

## 1. Introduction

Let{
F
m
}
m
≥
0 be the Fibonacci sequence given by F
0
=
0, F
1
=
1, and F
n
+
2
=
F
n
+
1
+
F
n for all n
≥
0. For a positive integer n, let z
(
n
) be theorder of appearance of n in the Fibonacci sequence, which is the minimal positive integer k such that n
∣
F
k. It is known that z
(
n
) always exists and in fact z
(
n
)
≤
σ
(
n
), where σ
(
n
) is the sum of divisors of n. Let us say that N is a local minimum for the function z
(
n
) if z
(
N
)
<
min
⁡
{
z
(
N
-
1
)
,
z
(
N
+
1
)
}. It is not hard to prove that if N
=
F
n for some positive integer n
≠
3 (so N
≠
2), then N is a local minimum for z
(
n
) (see Page 1 in [1]).In Theorem 1.1 in [1], Marques exhibited a family of positive integers which are not members of the Fibonacci sequence but are local minima for z
(
n
). That family is (1)
M
1
=
F
m
k
F
k
:
k
≥
3
,
m
≥
m
k
,where m
k
≥
5 is some fixed number depending on k which is not computable from the arguments in [1]. This problem was revisited in [2], where a different family of local minima is given; namely, (2)
M
2
=
F
m
k
+
ɛ
F
k
F
k
-
ɛ
:
ɛ
∈
±
1
,
12
∣
k
∣
m
,
m
>
m
ɛ
,
k
,where as before m
ɛ
,
k depends on ɛ and k and is not computable from the arguments in [2].None of the above two families gives us too many examples. Indeed, let bex a large positive real number and put A
(
x
)
=
A
∩
[
1
,
x
]. Assume that N
∈
M
1
(
x
)
∪
M
2
(
x
). Then, using the Binet formula(3)
F
i
=
α
i
-
β
i
α
-
β
,
w
h
e
r
e
α
,
β
=
1
+
5
2
,
1
-
5
2valid for all integers i
≥
0, it follows that N is determined in at most 3 ways by a pair of parameters (
m
,
k
) with k
≥
3 such that (4)
m
k
-
1
≤
c
+
o
1
log
⁡
x
a
s
x
⟶
∞
,where c
=
(
log
⁡
α
)
-
1. Using the classical estimates on the summatory function of the number of divisors function we get that(5)
#
M
1
x
∪
M
2
x
=
O
log
⁡
x
log
⁡
log
⁡
x
.Before we formulate the main result of this paper we need one more notion. A prime factor p of F
m is calledprimitive if z
(
p
)
=
m. A celebrated result of Carmichael [3] (see [4] for the most general result of this type) asserts that p always exists whenever m
≥
13. The main result of this paper is the following.Theorem 1.
Letn
≥
15 and(6)
N
=
F
n
a
,where a is a divisor of F
n subject to the following restrictions: (i)
a
≤
F
n
1
/
5;
(ii)
there exists a primitive prime factorp of F
n such that p
∤
a.Then n is a local minimum for z
(
n
). Furthermore, each such N is representable in a unique way as N
=
F
n
/
a for some integers n
≥
15 and a satisfying (i) and (ii) above, and N is not a Fibonacci number whenever a
≥
2.The inequalityF
a
+
b
≥
F
a
F
b is valid for all positive integers a and b. To prove it, fix a, note that it trivially holds for b
∈
{
1,2
}, and then use induction on b and the recurrence formula for the Fibonacci numbers to show that it holds for all b
≥
1. In particular, F
k
≤
F
m
k
1
/
m. Thus, if N
∈
M
1, then (7)
N
=
F
m
k
F
k
,where if we put n
:
=
m
k and a
≔
F
k, then a
≤
F
m
k
1
/
m
≤
F
n
1
/
5 because m
≥
5. Additionally, n
≥
15 because k
≥
3 and m
≥
5. Further, the number N is clearly divisible by a primitive divisor of F
n (in fact, byany of the primitive divisors of F
n). This argument shows that the set M
1 is contained in the set of numbers N satisfying the conditions of Theorem 1. Now Theorem 1 says that in fact the parameter m
k from M
1 canalways be taken to be 5. Putting M
3 for the set of numbers satisfying the conditions of Theorem 1, we have the following estimate.Theorem 2.
The estimate(8)
#
M
3
x
≥
exp
⁡
exp
⁡
c
1
+
o
1
log
⁡
log
⁡
x
log
⁡
log
⁡
log
⁡
x
h
o
l
d
s
a
s
x
⟶
∞
, where c
1
=
log
⁡
2.Theorem2 implies that the counting function of local minima N
≤
x exceeds (
log
⁡
x
)
A for any positive constant A (compare with (5)). In particular, the series (9)
∑
N
>
1
l
o
c
a
l
m
i
n
i
m
u
m
o
f
z
n
1
log
⁡
N
Adiverges for all A
>
0.


## 2. Proof of Theorem1

Suppose thatn
=
15. Then F
n
=
610 and the only divisors a of 610 satisfying (i) of Theorem 1 is a
∈
{
1,2
}. Now one checks that z
(
609
), z
(
611
), z
(
304
), z
(
306
) are all larger than z
(
305
)
=
z
(
610
)
=
15. One does not even have to compute the above orders of appearance; one only has to factor the first 15 members of the Fibonacci sequence in order to convince oneself that none of them is a multiple of 609 or of 611 or of 304 or of 306. From now on, n
≥
16.Assume thatN
=
F
n
/
a satisfies the conditions of Theorem 1. Then z
(
N
)
=
n. Indeed, N
∣
F
n, so z
(
N
)
≤
n. On the other hand, if N
∣
F
m for some positive integer m, then (ii) of Theorem 1 shows that p
∣
N
∣
F
m for some prime p with z
(
p
)
=
n; therefore m
≥
n. Thus, z
(
N
)
=
n. Assume now that z
(
N
+
ɛ
)
≤
n for some ɛ
∈
{
±
1
}. We then get an equation of the form(10)
F
n
a
+
ɛ
=
F
m
bfor some positive integers m
≤
n and b
∣
F
m. Since (11)
F
n
a
≥
F
n
4
/
5
≥
F
16
4
/
5
>
200
,we get (12)
F
m
b
=
F
n
a
+
ɛ
≥
F
n
a
-
1
>
2
F
n
3
a
,so(13)
b
<
3
a
2
F
m
F
n
≤
3
a
2
.Let us see that in fact m
<
n. Indeed, if m
=
n, then multiplying both sides of (10) by a
b, we get F
n
(
a
-
b
)
=
ɛ
a
b. This implies first that a
≠
b and secondly that (14)
F
n
∣
a
b
.But this conclusion is impossible because it leads, by (13), to (15)
F
n
≤
a
b
<
3
a
2
2
≤
1.5
F
n
2
/
5
,which is false for n
≥
16. Hence, m
≤
n
-
1. Since (16)
F
m
F
n
≤
F
n
-
1
F
n
≤
2
3
,for n
≥
16, together with inequality (13), we get b
<
a. We will use the inequality(17)
α
k
-
2
≤
F
k
≤
α
k
-
1valid for all integers k
≥
2. We then have, using inequality (17) with k
=
m and n, respectively, that (18)
α
n
-
2
≥
α
m
-
1
≥
F
m
b
≥
F
n
a
-
1
≥
F
n
4
/
5
-
1
>
F
n
4
/
5
α
2
/
5
≥
α
4
n
/
5
-
2
,so m
=
n
-
k for some integer k
∈
[
1
,
n
/
5
+
1
). Using Binet formula (3) with i
=
m and i
=
n, respectively, (10) is equivalent to (19)
b
α
n
-
β
n
+
ɛ
5
a
b
=
a
α
n
-
k
-
β
n
-
k
,which can be regrouped as(20)
α
n
b
-
a
α
-
k
=
b
β
n
-
ɛ
5
a
b
-
a
β
n
-
k
.The number η
≔
b
-
a
α
-
k is an algebraic integer in K
≔
Q
(
5
) which is not zero; otherwise α
k
=
b
/
a
∈
Q, which is impossible for positive integers k. Thus, the norm of η over K is an integer which is at least 1 in absolute value. Hence, (21)
b
-
a
α
-
k
b
-
a
β
-
k
≥
1
,giving(22)
b
-
a
α
-
k
≥
1
b
+
a
α
k
>
1
F
n
1
/
5
1
+
α
n
/
5
+
1
>
1
α
n
-
1
/
5
1
+
α
n
+
5
/
5
.Inserting (22) into (20) and using also (17), we get (23)
α
4
n
+
1
/
5
1
+
α
n
+
5
/
5
<
α
n
b
-
a
α
-
k
=
b
β
n
-
ɛ
5
a
b
-
a
β
n
-
k
≤
b
α
n
+
5
a
b
+
a
α
n
-
k
<
F
n
1
/
5
α
n
+
5
F
n
2
/
5
+
F
n
1
/
5
α
4
n
/
5
-
1
<
5
+
0.1
F
n
2
/
5
<
5
+
0.1
α
2
n
-
1
/
5
,where we used the fact that α
4
n
/
5
-
1
>
20 for n
≥
16. The above inequality leads to the conclusion that x
:
=
α
n
/
5 satisfies the inequality(24)
α
3
/
5
x
2
-
5
+
0.1
α
x
-
5
+
0.1
<
0
.However, the largest root of the quadratic polynomial from the left-hand side above is 4.607
⋯
<
4.664
⋯
=
α
3.2
≤
α
n
/
5
=
x for n
≥
16, so quadratic (24) in x cannot be negative for n
≥
16, which is a contradiction.The remaining assertions of the theorem are easy. To see unicity, assume thatN
=
F
n
/
a
=
F
n
′
/
a
′ are two representations of the same N satisfying conditions (i) and (ii) of the theorem. If n
=
n
′, then a
=
a
′ and we are through. If n
≠
n
′, suppose without loss of generality that n
>
n
′. Then, by (ii), there is some primitive prime factor p of F
n which divides N
=
F
n
/
a. Since p is primitive for F
n it cannot divide F
n
′, which is a multiple of N, a contradiction. In particular, if n
≥
15 and a
≥
2, then N
=
F
n
/
a cannot have another representation of the form F
n
′
/
a
′ with a
′
=
1 (so n
′
>
n
≥
15), so it cannot be a Fibonacci number.The theorem is therefore proved.


## 3. Proof of Theorem2

Letx be large and let n be such that(25)
15
≤
n
≤
c
log
⁡
x
.Since F
n
<
α
n
≤
x by (17), it follows that any number N
=
F
n
/
a satisfying the conditions of Theorem 1 with n satisfying (25) is in M
3
(
x
). We now choose n maximal satisfying inequality (25) of the form (26)
n
=
∏
i
=
1
m
p
i
,where 2
=
p
1
<
p
2
<
⋯ denotes the sequence of all primes. By the Prime Number Theorem, we have (27)
n
=
e
1
+
o
1
p
m
,as m
→
∞, showing that p
m
=
log
⁡
log
⁡
x as x
→
∞. By the Prime Number Theorem again, we get that(28)
m
=
1
+
o
1
log
⁡
log
⁡
x
log
⁡
log
⁡
log
⁡
xas x
→
∞. Now let a be a divisor of F
n
/
p
m. For large x, we have p
m
≥
5; therefore a
≤
F
n
/
p
m
≤
F
n
1
/
p
m
≤
F
n
1
/
5, so condition (i) from Theorem 1 is satisfied. Condition (ii) is also satisfied and in fact any primitive prime factor of F
n will divide F
n
/
F
n
/
p
m, which is a divisor of F
n
/
a. Now by the Primitive Divisor Theorem, for every divisor d
∉
{
1,2
,
6
} of n
/
p
m, F
d has a primitive prime factor p
d which of course divides F
n
/
p
m. This shows that F
n
/
p
m has at least (29)
τ
n
p
m
-
3
=
τ
n
2
-
3
=
2
m
-
1
-
3distinct prime factors, where τ
(
k
) denotes the number of divisors of the positive integer k. Hence, the number of such convenient a’s is at least as large as the number of square-free integers built up with prime factors from a set of 2
m
-
1
-
3 distinct primes, and this number is at least as large as (30)
2
2
m
-
1
-
3
.Thus, (31)
#
M
3
x
≥
2
2
m
-
1
-
3
,where m satisfies estimate (28), which leads to the desired conclusion of the theorem.



---

*Source: 823973-2015-10-01.xml*