THE MAXIMUM LENGTH FOR DUCCI SEQUENCES ON Znm

WHEN n IS EVEN
arXiv:2410.18204v1 [math.NT] 23 Oct 2024

MARK L. LEWIS AND SHANNON M. TEFFT

Abstract. Let D : Zn n
m → Zm be defined so
D(x1 , x2 , ..., xn ) = (x1 + x2 mod m, x2 + x3 mod m, ..., xn + x1 mod m).
D is known as the Ducci function and for u ∈ Zn α
m , {D (u)}α=0 is the Ducci
∞

sequence of u. Every Ducci sequence enters a cycle because Zn m is finite. In

this paper, we aim to establish an upper bound for how long it will take for a
Ducci sequence in Znm to enter its cycle when n is even.

1. Introduction
We focus on an endomorphism, D, on Znm such that
D(x1 , x2 , ..., xn ) = (x1 + x2 mod m, x2 + x3 mod m, ..., xn + x1 mod m).
We call D the Ducci function, similar to [2, 8, 11]. If u ∈ Znm , then {Dα (u)}∞
α=0
is known as the Ducci sequence of u.
Because Znm is finite, every Ducci sequence eventually enters a cycle. We have a
specific name for this cycle, which we give in the following definition:
Definition 1. The Ducci cycle of u is
{v | ∃α ∈ Z+ ∪ {0}, β ∈ Z+ ∋ v = Dα+β (u) = Dα (u)}
. The length of u, Len(u), is the smallest α satisfying the equation
v = Dα+β (u) = Dα (u)
for some v ∈ Znm and the period of u, Per(u), is the smallest β that satisfies the
equation.
To see this in action, let us look at the Ducci sequence of (0, 0, 0, 1) ∈ Z45 :
(0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 2, 1), (1, 3, 3, 1), (4, 1, 4, 2), (0, 0, 1, 1). From here, we can
see that the Ducci cycle of (0, 0, 0, 1) is (0, 0, 1, 1), (0, 1, 2, 1), (1, 3, 3, 1), (4, 1, 4, 2),
(0, 0, 1, 1). We can also determine that Len(0, 0, 0, 1) = 1 and Per(0, 0, 0, 1) = 4.
This tuple (0, 0, 0, 1) and any tuple of the form (0, 0, ..., 0, 1) ∈ Znm is important
when it comes to Ducci sequences. The Ducci sequence of (0, 0, ..., 0, 1) ∈ Znm
is called the basic Ducci sequence of Zn m . This definition is first used on
page 302 by [8] and also by [2, 7, 11]. We also define Pm (n) = Per(0, 0, ..., 0, 1)
and Lm (n) = Len(0, 0, ..., 0, 1). Both of these notations are very similar to how
Definition 5 of [2] define them, and for P er(0, 0, ..., 0, 1), the notation is also like
[8, 11]. Therefore, our example from the previous paragraph tells us P5 (4) = 4 and
L5 (4) = 1. These values are significant because by Lemma 1 in [2], if u ∈ Znm ,

Date: September 2024.

2020 Mathematics Subject Classification. 20D60, 11B83, 11B50.
Key words and phrases. Ducci sequence, modular arithmetic, length, period, n-Number Game.
1
2 MARK L. LEWIS AND SHANNON M. TEFFT

then Len(u) ≤ Lm (n) and Per(u)|Pm (n). Therefore, Pm (n) and Lm (n) provide a
maximal value for P er(u) and Len(u) respectively for any u ∈ Znm . The notation
of Pm (n) representing the maximum value for a tuple in Znm is also used on page
858 of [3].
For the rest of this paper, we are most interested in the value of Lm (n), partic-
ularly when n is even. Our goal is to prove:
Theorem 2. Let n be even. Then
(1) If gcf (n, m) = 1, then Lm (n) = 1.

(2) If there exists p prime, k, n1 , m1 ∈ Z+ , such that n = pk n1 , m = pm1 ,

gcf (n1 , m1 ) = 1 and p ∤ n1 , m1 , then Lm (n) = pk .

(3) If there exists p prime and k, l, n1 , m1 ∈ Z+ such that n = pk n1 , m = pl m1 ,

gcf (n1 , m1 ) = 1, and p ∤ n1 , m1 then Lm (n) ≤ pk−1 (l(p − 1) + 1).

(4) If there exists p1 , p2 , ..., pt prime where p1 < p2 < · · · < pt , for 1 ≤ i ≤ t,
and n = pk11 pk22 · · · ptkt n1 , m = pl11 pl22 · · · pltt m1 with gcf (n1 , m1 ) = 1 and
pi ∤ n1 , m1 for every i, then
Lm (n) = max{Lpli (n) | 1 ≤ i ≤ t}.
i

It is worth noting that in part (3) of Theorem 2, we believe

Lm (n) = pk−1 (l(p − 1) + 1).
We are able to confirm this is true for all m ≤ 50 and even n ≤ 20 where gcf (n, m)
is a power of a prime. We would test for larger n, m, but our program for computing
Lm (n) requires first finding Pm (n), which typically gets larger as n, m increase. The
values of Pm (n) get too large for our Matlab program to find.
The work in this paper was done while the second author was a Ph.D. student
at Kent State University under the advisement of the first author and will appear
as part of the second author’s dissertation.

2. Background
The Ducci function is originally defined as an endomorphism on Zn or (Z+ ∪{0})n
such that D̄(x1 , x2 , ..., xn ) = (|x1 − x2 |, x2 − x3 |, ...., |xn − x1 |), and is the most
common definition of the Ducci function. Some examples of papers that define the
Ducci function this way are [2, 8, 10, 11, 14]. Note that if D̄ is defined on Zn , then
D̄(u) ∈ (Z+ ∪ {0})n . Therefore, for simplicity, we will refer to both of these cases
as Ducci on Zn . Other papers, including [4, 6, 15], use the same formula for D̄ but
define Ducci on Rn . It is of course necessary that we handle the cases of Ducci on
Zn and on Rn separately.
Ducci sequences in both of these cases also always enter a cycle. There are
discussions of why this happens on Zn in [5, 8, 11, 14] and Theorem 2 of [15] proves
it for Ducci on Rn . A well known fact for Ducci on Zn is proved in Lemma 3 of
[14]: all of the entries of a tuple in a Ducci cycle belong to {0, c} for some c ∈ Z+ .
Since D̄(λu) = λD̄(u) for all u ∈ Zn , this means that we can focus on when Ducci
is defined on Z2 where we are using our definition of D given at the beginning of
the paper, particularly when examining Ducci cycles. Theorem 1 of [15] proves a
similar finding for Ducci on Rn , namely that if the Ducci sequence reaches a limit
 THE MAXIMUM LENGTH FOR DUCCI SEQUENCES ON Zn
m WHEN n IS EVEN 3

point, then all of the entries of that limit point belong to {0, c}, where this time we
have c ∈ R.
Because of the significance of Ducci on Zn2 to the original Ducci case, this leads
us to wonder what happens if we define Ducci on Znm using our definition given at
the beginning of the paper. The first paper to look at Ducci on Znm is [17], and is
also examined in [2, 3, 7].
There are a few classical results from the case of Ducci on Zn that apply to the
case when m = 2. When looking at L2 (n) in particular, [8] is the first to give that
L2 (n) = 1 when n is odd on page 303. When n is even, Theorem 6 of [11] gives that
if n = 2k1 + 2k2 where k1 > k2 ≥ 0, then L2 (n) = 2k2 . This is then extended by
Theorem 4 of [1] to all even n = 2k n1 where n1 is odd. Here, L2 (n) = 2k . Notice
that this supports part 2 of Theorem 2 when m = p = 2.
If we allow n to be odd, we have a formula for Lm (n) from Theorem 2 of [13].
Specifically, if m = 2l m1 where n, m1 are odd, then Lm (n) = l. For a case where n is
even, Theorem 2 of [12], proves that if n = 2k and m = 2l , then Lm (n) = 2k−1 (l+1).
Before moving on, we would also like to give a few definitions that will be useful
later. If u, v ∈ Znm , then v is a predecessor to u if D(v) = u.
We let K(Zn m ) be the set of all tuples in a Ducci cycle. On page 6001 of [2], it
is stated that K(Znm ) is a subgroup of Znm . A proof of this is provided in Theorem
1 of [12].
We now consider another example of a Ducci sequence and its cycle. For this,
we will look at the basic Ducci sequence of Z62 . We create a transition graph that
not only gives the basic Ducci sequence, but also gives all tuples whose sequence
has tuples in the basic Ducci sequence. This transition graph is given in Figure 1.
Notice that we can determine that L2 (6) = 2 from Figure 1, which agrees with
Theorem 2. We can also see that P2 (6) = 6.
It is worth noting that every tuple in Figure 1 that has a predecessor has exactly
two, which is the same as our m in this case. This is because of Theorem 4 in [12],
which says that if n is even, then every tuple that has a predecessor has exactly m
predecessors. This theorem also tells us that if u ∈ Znm has a predecessor, call it
(x1 , x2 , ..., xn ), then the remaining predecessors are of the form
(x1 + z, x2 − z, x3 + z, ..., xn − z)
for some z ∈ Zm and all tuples of this form are a predecessor to u.
All of the tuples in the transition graph in Figure 1 that have a predecessor, call
them (x1 , x2 , ..., xn ), also satisfy the condition that x1 −x2 +x3 −· · ·−xn ≡ 0 mod 2.
In fact,we have the following theorem about this:
Theorem 3. Let n be even. (x1 , x2 , ..., xn ) ∈ Znm has a predecessor, if and only if
x1 − x2 + x3 − x4 + · · · + xn−1 − xn ≡ 0 mod m
We first note that [14] proves in Lemma 5 that this is true for m = 2 and [2]
proves it is true when m is prime in Lemma 4.
Proof of Theorem 3. (⇒) Assume (x1 , x2 , ..., xn ) has a predecessor (y1 , y2 , ..., yn ).
Then
y1 + y2 ≡ x1 mod m
y2 + y3 ≡ x2 mod m
..
.
4 MARK L. LEWIS AND SHANNON M. TEFFT

(0, 0, 0, 0, 0, 1) (0, 1, 0, 1, 1, 0, 1)

(1, 1, 1, 1, 1, 0) (0, 0, 0, 0, 1, 1) (1, 1, 1, 0, 1, 1) (1, 0, 1, 0, 0, 1, 0)

(0, 1, 1, 0, 0, 1) (0, 0, 0, 1, 0, 1) (0, 0, 1, 1, 1, 1) (0, 1, 0, 0, 0, 0)

(1, 0, 1, 0, 1, 1) (1, 1, 1, 1, 0, 0) (0, 1, 0, 0, 0, 1) (1, 1, 0, 0, 0, 0)

(1, 0, 0, 1, 1, 0) 0, 1, 0, 1, 0, 0) (1, 1, 0, 0, 1, 1) (1, 0, 1, 1, 1, 1)

(0, 0, 0, 1, 0, 0) (0, 0, 1, 1, 0, 0) (1, 0, 1, 1, 1, 0) (0, 1, 1, 0, 1, 0)

(1, 1, 1, 0, 1, 1) (1, 0, 0, 1, 0, 1)

Figure 1. Transition Graph for Z62

yn + y1 ≡ xn mod m. (2.1)
Subtracting the second equation from the first, we get
y1 − y3 ≡ x1 − x2 mod m.
Adding this to the third equation, we get
y1 + y4 ≡ x1 − x2 + x3 mod m.
Continuing, we get
y1 − yn−1 ≡ x1 − x2 + · · · − xn−2 mod m
and
y1 + yn ≡ x1 − x2 + · · · + xn−1 mod m.
Using this and Equation (2.1), we see
xn ≡ x1 − x2 + · · · + xn−1 mod m,
which gives
x1 − x2 + · · · + xn−1 − xn ≡ 0 mod m,
and (⇒) follows.
(⇐) Assume x1 − x2 + x3 − x4 + · · · + xn−1 − xn ≡ 0 mod m. It suffices to show
that there exists y1 , y2 , ..., yn that satisfy the equations
y1 + y2 ≡ x1 mod m
 THE MAXIMUM LENGTH FOR DUCCI SEQUENCES ON Zn
m WHEN n IS EVEN 5

y2 + y3 ≡ x2 mod m
..
.
yn + y1 ≡ xn mod m.
Let y1 = 0. If we let y2 = x1 , then the first equation will be satisfied. If we then let
y3 = x2 − x1 , the second equation will be satisfied. If we continue this following the
structure yj = xj−1 − xj−2 + · · · + x1 when j is even and yj = xj−1 − xj−2 + · · · − x1
when j is odd, then the first n − 1 equations will be satisfied.
This would result in yn = xn−1 − xn−2 + · · · + x1 . We then see that
y1 + yn ≡ xn−1 − xn−2 + · · · + x1 mod m
By assumption, xn−1 − xn−2 + · · · + x1 ≡ xn mod m and y1 + yn ≡ xn mod m
follows, and the final equation is satisfied. Therefore, (x1 , x2 , ..., xn ) has at least
one predecessor, (y1 , y2 , ..., yn ). 
Moving forward, if u ∈ Znm , it will be useful to have a tool that gives us infor-
mation about tuples in the Ducci sequence of u. To do this, let us first look at the
first few tuples in the Ducci sequence of a tuple (x1 , x2 , ..., xn ) ∈ Znm :

(x1 , x2 , ..., xn )
(x1 + x2 , x2 + x3 , ..., xn + x1 )
(x1 + 2x2 + x3 , x2 + 2x3 + x4 , ..., xn + 2x1 + x2
(x1 + 3x2 + 3x3 + x4 , x2 + 3x3 + 3x4 + x5 , ..., xn + 3x1 + 3x2 + x3 )
..
.
We can see that the coefficients on the xj in the first entry of each tuple in
the Ducci sequence occurs in all of the entries of that tuple for some xi . For this
reason, we will let ar,s represent the coefficient that is on xs in the first entry of
Dr (x1 , x2 , ..., xn ). Here r ≥ 0 and 1 ≤ s ≤ n. The s coordinate reduces modulo n,
with the exception that we write ar,n instead of ar,0 . Note that ar,s also appears
as the coefficient on xs−i+1 in the ith entry of Dr (x1 , x2 , ..., xn ). Page 6 of [12]
provides a more thorough explanation of why we can do this. We also have that
Dr (0, 0, ..., 0, 1) = (ar,n , ar,n−1 , ..., ar,1 ).
 
r
Additionally, by Theorem 5 of [12], when r < n, ar,s = . This theorem
s−1
Xn
also tells us that ar+t,s = at,i ar,s−i+1 when t ≥ 1 and ar,s = ar−1,s + ar−1,s−1 .
i=1

3. Proving the Main Theorem

Before we can prove Theorem 2, there are a few lemmas that we will need.
We begin with two lemmas about particular binomial coefficients. We believe that
both Lemmas 4 and 5 are known and have been proven before, but we are providing
proofs here for completeness.
Lemma 4. Let p be prime and j ≤ pk − 1, k ≥ 1. Then
 k 
p −1
≡ (−1)j mod p.
j
6 MARK L. LEWIS AND SHANNON M. TEFFT

Proof. To prove this, we will do induction on j.  k 

p −1
Basis Step j = 0: Note that this is satisfied by = 1.
 k  0
p −1
Inductive Step: Now assume that ≡ (−1)j−1 mod p. Note
j−1
 k  k   k 
p p −1 p −1
= + .
j j j−1
Because we proved the j = 0 case in the basis step, we can assume 0 < j ≤ pk − 1,
which will give us
 k   k 
p −1 p −1
+ ≡ 0 mod p.
j j−1
 k 
p −1
Solving for , we get
j
 k   k 
p −1 p −1
≡− mod p.
j j−1
By induction, this is equivalent to
−(−1)j−1 mod p
or
(−1)j mod p,
and the lemma follows.

The next lemma is similar to Lemma 4:
Lemma 5. For k > 1 and p an odd prime
 k  (
p − pk−1 (−1)c mod p j = cpk−1
≡ .
j 0 mod p otherwise
Proof. We prove this via induction on j.
Basis steps j = 0, 1: These follow from
 k
p − pk−1

≡ 1 mod p
0
and  k
p − pk−1

≡ 0 mod p.
1
Inductive step: Assume that the lemma is true for j ∗ < j. For j > 0, we use
the Chu-Vandermonde identity, a proof of which can be found in [16] to yield
 k X j  k−1  k
p − pk−1

p p
= ≡ 0 mod p. (3.1)
j i=0
i j−i

If j < pk−1 , the sum in (3.1) is also equivalent to

 k−1  k
p − pk−1

p
mod p,
0 j
 THE MAXIMUM LENGTH FOR DUCCI SEQUENCES ON Zn
m WHEN n IS EVEN 7

 k
p − pk−1

which is congruent to 0 mod p, so ≡ 0 mod p.
j
If j ≥ pk−1 , the sum in (3.1) is equivalent to
 k−1  k
p − pk−1
  k−1  k
p − pk−1

p p
+ k−1 .
0 j p j − pk−1
This is congruent to 0 mod p by Equation (3.1), we have
 k
p − pk−1
 k
p − pk−1
 
≡− mod p.
j j − pk−1
 k
p − pk−1

If j 6= cpk−1 for some c, then is congruent to 0 mod p by induction.
 k j k−1 
p −p
If j = cpk−1 for some c, then is equivalent to −(−1)c−1 mod p or
j
(−1)c mod p and the lemma follows.


Next, we would like to look at the ar,s coefficient for a particular r in Lemmas
6 and 7.
Lemma 6. Let n = pk n1 where p is prime, n1 > 1 and c ≥ 1. Then for s 6= bpk + 1
and 0 ≤ b < n1 , acpk ,s ≡ 0 mod p
Proof. We prove this via induction on c.
Basis Step c = 1:
 k 
p
apk ,s = ≡ 0 mod p
s−1
precisely when s 6= 1, pk + 1.
Inductive Step: Assume
a(c−1)pk ,s ≡ 0 mod p

for s 6≡ b′ pk + 1 mod n, 0 ≤ b′ ≤ n1 − 1. Using Theorem 5 of [12]

n
X
acpk ,s = apk ,i a(c−1)pk ,s−i+1 .
i=1

pk
 
Using apk ,i = , this sum is equivalent to
i−1
apk ,1 a(c−1)pk ,s + apk ,pk +1 a(c−1)pk ,s−pk mod p.

Notice that for s 6≡ bpk + 1 mod n, this is ≡ 0 mod p where 0 ≤ b ≤ n1 − 1 by

induction, and the lemma follows. 

For the remaining cases where s = bpk + 1, we have this lemma:

Lemma 7. Let n = pk n1 for some k and n1 > 1, ar,s be the coefficients for n, and
a∗r,s be the coefficients for n1 . Then, for c ≥ 1 and 0 ≤ b < n1 ,
acpk ,bpk +1 ≡ a∗c,b+1 mod p.
8 MARK L. LEWIS AND SHANNON M. TEFFT

Proof. We prove this via induction on c:  k

k p
Basis Step c = 1: Notice that because p < n, we have apk ,1 = , which is
  0
∗ 1
1. Since a1,1 = = 1, we have that
0
apk ,1 ≡ a∗1,1 mod p.
Similarly,
 k
p
apk ,pk +1 = =1
pk
and  
1
a∗1,2 = = 1,
1
 k
p
so apk ,pk +1 ≡ a∗1,2 mod p. Finally, for 2 ≤ b < n1 , because ≡ 0 mod p when
  j1
1
j1 6= 1, pk and = 0 when j2 > 1, we have
j2
apk ,bpk +1 ≡ a∗1,b+1 mod p
for every 2 ≤ b < n1 . The basis case follows.
Inductive Step: Assume
a(c−1)pk ,bpk +1 ≡ a∗c−1,b+1 mod p
when 0 ≤ b < n1 . Then,
n
X
acpk ,bpk +1 = apk ,i a(c−1)pk ,bpk +2−i . (3.2)
i=1

pk

Notice that apk ,s = ≡ 0 mod p when s 6= 1, pk + 1. Therefore, our
s−1
remaining pieces tell us Equation (3.2) is
apk ,1 a(c−1)pk ,bpk +1 + apk ,pk +1 a(c−1)pk ,(b−1)pk +1 mod p.
By induction, this is
a∗c−1,b+1 + a∗c−1,b mod p,
which is a∗c,b+1 . The lemma follows.

k
Putting Lemmas 6 and 7 together allows us to visualize what Dcp (0, 0, ..., 0, 1)
looks like in Znp for n = pk n1 :
k
Dcp (0, 0, ..., 0, 1) = (0, 0, ..., 0, a∗c,n1 , 0, ..., 0, a∗c,n1 −2 , 0, ..., 0, a∗c,1).
Bear in mind that the last set of ... covers a much larger area then the first two.
We now have the pieces we need to prove Theorem 2:
Proof of Theorem 2. (1): We would like to first note that when m is prime, this
case follows from Lemma 5 of [2].
Assume that gcf (n, m) = 1. We want to prove
(0, 0, ..., 0, 1, 1) ∈ K(Znm )
 THE MAXIMUM LENGTH FOR DUCCI SEQUENCES ON Zn
m WHEN n IS EVEN 9

and
(0, 0, ..., 0, 1) 6∈ K(Znm ).
We first use Theorem 3 to note that since −1 6≡ 0 mod m, (0, 0, ..., 0, 1) does not
have a predecessor and therefore (0, 0, ..., 0, 1) 6∈ K(Znm ).
We now note that (0, 0, ..., 0, 1, 1) has m predecessors and that if any of these
predecessors is in the cycle, then so is (0, 0, ..., 0, 1, 1). In addition to this, if there
exists u, v ∈ Znm such that D2 (v) = D(u) = (0, 0, ..., 0, 1, 1), then u ∈ K(Znm )
because otherwise we would have
Len(v) > Len(u) = Len(0, 0, ..., 0, 1) = Lm (n),
which cannot happen.
Since (0, 0, ..., 0, 1) is a predecessor for (0, 0, ..., 0, 1, 1), then by Theorem 4 of [12],
the other predecessors of (0, 0, ..., 0, 1, 1) will be of the form
u = (z, m − z, z, ..., z, 1 − z)
for some nonzero z ∈ Zm , so we only need to prove that there exists such a z where
u has a predecessor. By Theorem 3, u has a predecssor if and only if
z − (m − z) + z − (m − z) + · · · + z − (1 − z) ≡ 0 mod m,
or equivalently,
nz − 1 ≡ 0 mod m.
Since gcf (n, m) = 1, there exists a unique z such that nz ≡ 1 mod m. Therefore
we have a z that satisfies the above and (z, m − z, z, ..., z, 1 − z) has a predecessor.
Therefore, Lm (n) = 1.
(2): It is worth noting that if m = p, then this case follows from Theorem 4 of
[2]. Assume n = pk n1 , m = pm1 where gcf (n1 , m1 ) = 1 and p ∤ n1 , m1 . We must
then start with proving that Lm (n) = pk .
Let Pm (n) = d. From the first case of this theorem, we know L m p
(n) = 1, which
means
m
ad+1,s ≡ a1,s mod
p
or  m
1 mod
 s = 1, 2
p
ad+1,s ≡ m .
0 mod
 otherwise
p
We will use this to write
 m
δs + 1 mod m
 s = 1, 2
p
ad+1,s ≡ m

 δs mod m otherwise
p
where 0 ≤ δs < p. We start by showing apk +d,s ≡ apk ,s mod m for every s. First,
n
X
apk +d,s = ad+1,i apk −1,s−i+1 .
i=1

Substituting in our values for ad+1,s , we see this is equivalent to

n
m m mX
(δ1 + 1)apk −1,s + (δ2 + 1)apk −1,s−1 + δi apk −1,s−i+1 mod m,
p p p i=3
10 MARK L. LEWIS AND SHANNON M. TEFFT

which after some rearranging is

n
mX
apk −1,s + apk −1,s−1 + δi apk −1,s−i+1 mod m.
p i=1
Using ar,s = ar−1,s +ar−1,s−1 from Theoremm 5 of [12] and substituting apk −1,s−i+1 ,
this is
n  k 
mX p −1
apk ,s + δi mod m.
p i=1 s−i
n  k 
mX p −1
Notice that this basis case will follow if δi ≡ 0 mod m, which
p i=1 s−i
n  k 
X p −1
will follow if δi ≡ 0 mod p.
i=1
s−i
 k 
p −1
Note that in this sum, 6= 0 for only pk many consecutive terms for
s−i
every s. We would like to use this and the following claim to prove
n  k 
X p −1
δi ≡ 0 mod p.
i=1
s−i
Claim:
n
(1) δs = 0 as long as s 6= bpk + 1, bpk + 2 for some 0 ≤ b < k .
p
n
(2) δbpk +1 = δbpk +2 , when 0 ≤ b < k .
p
n
(3) δbpk +1 + δ(b−1)pk +2 ≡ 0 mod p where 0 ≤ b < k .
p
n  k 
X p −1
Notice that δi ≡ 0 mod p will follow if the claim is true: the claim
i=1
s−i
will give us that most of the δi will be congruent to 0 mod p, and since at most pk
terms in the sum will already be nonzero, there will only be 2 nonzero terms in the
entire sum, as for every pk consecutive δi you pick, only 2 will be nonzero. This
leaves us with 2 cases:
Case 1: The two nonzero terms in the sum are adjacent to each other.
n  k 
X p −1
• If p is odd, then because of the claim and Lemma 4, we have δi
i=1
s−i
is either congruent to
δbpk +1 − δbpk +2 mod p
or
−δbpk +1 + δbpk +2 mod p,
both of which are equivalent to 0 mod p.

• If p = 2, then by the claim and the well-known Lucas’s Theorem (a proof

of which can be found in Theorem 1 of [9]), the sum
n  k 
X 2 −1
δi ≡ δ2k b+1 + δ2k b+2 mod 2,
i=1
s−i
 THE MAXIMUM LENGTH FOR DUCCI SEQUENCES ON Zn
m WHEN n IS EVEN 11

which is equivalent to 0 mod 2.

and Lm (n) ≤ pk would follow.
Case 2: The two nonzero terms are pk terms apart. This will only happen if
n  k 
X p −1
the remaining terms of δi are equivalent to
i=1
s−i
 k   k 
p −1 p −1
δbpk +1 + δ(b−1)pk +2 k mod p,
0 p −1
which, by the claim, would be congruent to 0 mod p and Lm (n) ≤ pk would
follow from here as well.
Proof of Claim: Without loss of generality, we may assume that pk |d and write
n
d = cpk . By Lemma 6, ad,s ≡ 0 mod p where s 6= bpk + 1 for some 0 ≤ b ≤ k .
p
Then for s 6= bpk + 1, bpk + 2,
ad+1,s = ad,s + ad,s−1 ≡ 0 mod p
which implies δs = 0 for s 6= bpk + 1, bpk + 2 and Part (1) of the Claim follows.
For Part (2) of the Claim,
ad+1,bpk +1 − ad+1,bpk +2 = ad,bpk +1 + ad,bpk − ad,bpk +2 − ad,bpk +1 ,
which is
ad,bpk − ad,bpk +2 ≡ 0 mod p,
because of Lemma 6 and because pk |d. Therefore, Part (2) of the Claim follows.
As for Part (3) of the Claim, we have
ad+1,bpk +1 + ad+1,(b−1)pk +2 = ad,bpk +1 + ad,bpk + ad,(b−1)pk +2 + ad,(b−1)pk +1 ,
which is equivalent to
ad,bpk +1 + ad,(b−1)pk +1 mod p.
By Lemma 7, this is
a∗c,b+1 + a∗c,b mod p
or
a∗c+1,b+1 mod p,
where a∗r,s is the coefficient for n1 . By Proposition 4 of [2], Pp (n1 pk ) = pk Pp (n1 ).
Since
d = cpk = pk Pp (n1 ),
we conclude that c = Pp (n1 ). So by Part (1) of Theorem 2,
(
0 mod p b > 1
ad+1,bpk +1 + ad+1,(b−1)pk +2 ≡ .
1 mod p b = 0, 1
For b > 1,
m
ad+1,bpk +1 + ad+1,(b−1)pk +2 ≡ (δbpk +1 + δ(b−1)pk +2 ) mod m,
p
which will give us δbpk +1 + δ(b−1)pk +2 ≡ 0 mod p.
For b = 0, 1,
m
ad+1,bpk +1 + ad+1,(b−1)pk +2 ≡ (δbpk +1 + δ(b−1)pk +2 ) + 1 mod m
p
12 MARK L. LEWIS AND SHANNON M. TEFFT

gives us δbpk +1 + δ(b−1)pk +2 ≡ 0 mod p for b = 0, 1 and (3) follows. Since the whole
claim follows, this gives us Lm (n) ≤ pk .
We now need to prove that Lm (n) = pk . Suppose Lm (n) ≤ pk − 1. Then
ad+pk −1,s ≡ apk −1,s mod m for every s and
n
X
ad+pk −1,s = ad+1,i apk −2,s−i+1 .
i=1
If we separate out the terms where s = 1, 2, this is
n
X
ad+1,1 apk −2,s + ad+1,2 apk −2,s−1 + ad+1,i apk −2,s−i+1 .
i=3
Substituting in our values for ad+1,s and apk −2,s−i+1 in the sum and rearranging,
this is equivalent to
n  k 
mX p −2
apk −2,s + apk −2,s−1 + δs mod m
p i=1 s−i
or
n  k 
mX p −2
apk −1,s + δi mod m.
p i=1 s−i
n  k 
mX p −2
This implies that δi ≡ 0 mod m, which produces
p i=1 s−i
n  k 
X p −2
δi ≡ 0 mod p.
i=1
s−i
Substituting δi = 0 for i 6= bpk + 1, bpk + 2 from the Claim, we have
nX
1 −1
pk − 2 pk − 2
   
δbpk +1 + δ bpk +2 mod p.
s − bpk − 1 s − bpk − 2
b=0
Using our Claim, this is
nX
1 −1
pk − 2 pk − 2
   
δbpk +1 ( + ) mod p
s − bpk − 1 s − bpk − 2
b=0
or
nX
1 −1
pk − 1
 
δbpk +1 mod p.
s − bpk − 1
b=0
pk − 1
 
Notice that only 1 of the is not congruent to 0 mod p. Therefore,
s − bpk − 1
n  k 
X p −2
we get δi is congruent to either
i=1
s−i
δbpk +1 mod p
or
−δbpk +1 mod p
for some 0 ≤ b ≤ n1 − 1. Now as long as one of the δbpk +1 coefficients is nonzero,
we have a contradiction. Suppose then that δbpk +1 = 0 for every b. Then, we would
have Lm (n) = 1. Then (0, 0, ..., 0, 1, 1) has a predecessor that is also in the cycle.
 THE MAXIMUM LENGTH FOR DUCCI SEQUENCES ON Zn
m WHEN n IS EVEN 13

This is equivalent, to one of its predecessors having a predecessor itself. Since one
of (0, 0, ..., 0, 1, 1) is (0, 0, ..., 0, 1), all of its other predecessors will be of the form
(z, m − z, z, ..., z, 1 − z) for some z ∈ Zm . Suppose there exists nonzero z such that
this tuple has a predecessor. Then it must be true that z + z + z + · · · + z − 1 + z ≡
0 mod m, which would suggest nz ≡ 1 mod m. However, since gcf (n, m) > 1, we
cannot have this and we have a contradiction. Therefore, Lm (n) = pk .
(3) We prove this via induction on l, where part (2) of this theorem serves as
the basis case of l = 1.
Inductive step: Assume that if n = pk n1 , m∗ = pl−1 m∗1 , gcf (n1 , m∗1 ) = 1, and
p ∤ n1 , m∗1 then Lm∗ (n) ≤ pk−1 ((l − 1)(p − 1) + 1) = γ.
Now assume that n = pk n1 and m = pl m1 with gcf (n1 , m1 ) = 1 and p ∤ n1 , m1 .
We set out to prove that Lm (n) ≤ γ + pk − pk−1 . Let Pm (n) = d. Without loss of
generality, we may assume pk |d. Then
m
aγ+d,s ≡ aγ,s mod .
p
Use this to write
m
aγ+d,s ≡ aγ,s + δs mod m
p
for some 0 ≤ δs < p. Note also that
Xn
aγ+pk −pk−1 ,s = apk −pk−1 ,i aγ,s−i+1 .
i=1
Since apk −pk−1 ,i is a binomial coefficient for every i, plug these in to see this sum is
n  k
p − pk−1
X 
aγ,s−i+1 . (3.3)
i=1
i−1
Now consider aγ+pk −pk−1 +d,s :
n
X
aγ+pk −pk−1 +d,s = apk −pk−1 ,i aγ+d,s−i+1 .
i=1
Plugging in our values for the aγ+d,s−i+1 , this is equivalent to
n
X m
apk −pk−1 ,i (aγ,s−i+1 + δs−i+1 ) mod m.
i=1
p
Separating the sums and plugging in apk −pk−1 ,i , this is
n  k n 
p − pk−1 m X pk − pk−1
X  
aγ,s−i+1 + δs−i+1 mod m.
i=1
i−1 p i=1 i−1
Using Equation (3.3), this is
n 
m X pk − pk−1

aγ+pk −pk−1 ,s + δs−i+1 mod m.
p i=1 i−1
n  k
p − pk−1
X 
Therefore, we only need that δs−i+1 ≡ 0 mod p to see
i=1
i−1

Lm (n) ≤ γ + pk − pk−1 .
We consider two cases:
14 MARK L. LEWIS AND SHANNON M. TEFFT

Case 1 p is an odd prime: Note that by Lemma 5, we have

n  k
p − pk−1
X 
δs−i+1 ≡ δs − δs−pk−1 + δs−2pk−1 − · · · + δs−pk +pk−1 mod p
i=1
i−1

when p is an odd prime. Note that

(aγ+d,s − aγ,s ) − (aγ+d,s−pk−1 − aγ,s−pk−1 ) + · · · + (aγ+d,s−pk +pk−1 − aγ,s−pk +pk−1 )
(3.4)
is equivalent to
m
(δs − δs−pk−1 + · · · + δs−pk +pk−1 ) mod m.
p
We can show δs − δs−pk−1 + · · · + δs−pk +pk−1 ≡ 0 mod p by showing Equation (3.4)
is congruent to 0 mod m. Since we already know that this sum is equivalent to
m
0 mod , it suffices to show Equation (3.4) is congruent to 0 mod p. Rewriting
p
the sum in Equation (3.4) yields
p−1
X p−1
X
(−1)i aγ+d,s−ipk−1 − (−1)i aγ,s−ipk−1 . (3.5)
i=1 i=1

Note that if s 6= bpk−1 + 1 for some b, then this is equivalent to 0 mod p by Lemma
6 and because pk−1 |γ, d. Assume then that s = bpk−1 + 1 for some b. Then using
d = cpk , γ + d = pk−1 ((l − 1)(p − 1) + 1 + cp). So the first sum in Equation (3.5) is
p−1
X p−1
X
(−1)i aγ+d,s−ipk−1 = aγ+d,(b−i)pk−1 +1 ,
i=1 i=1

which by Lemma 7, is congruent to

p−1
X
(−1)i a∗(l−1)(p−1)+1+cp,b−i+1 mod p. (3.6)
i=1

By Proposition 4 of [2], Pp (n) = pk Pp (n1 ). By Proposition 3.1 of [7], Pp (n)|Pm (n).

So
pk Pp (n1 )|cpk
and we conclude Pp (n1 )|c. Using this yields that (3.6) is

p−1
X
(−1)i a∗(l−1)(p−1)+1,b−i+1 mod p.
i=1

Looking at our other sum in Equation (3.5),

p−1
X p−1
X
(−1)i aγ,s−ipk−1 = (−1)i aγ,(b−i)pk−1 +1 ,
i=1 i=1

which by Lemma 7 is
p−1
X
(−1)i a∗(l−1)(p−1)+1,b−i+1 mod p.
i=1
 THE MAXIMUM LENGTH FOR DUCCI SEQUENCES ON Zn
m WHEN n IS EVEN 15

So we have that Equation (3.5) is

p−1
X p−1
X
i
(−1) aγ+d,s−ipk−1 − (−1)i aγ,s−ipk−1 ≡ 0 mod p,
i=1 i=1

which gives us that Lm (n) ≤ pk−1 (l(p − 1) + 1).

Case 2 p = 2: We want to show Lm (n) ≤ 2k−1 (l + 1). Write d = 2k c. Then the
sum we are interested in is
n  k n  k−1 
p − pk−1

X X 2
δs−i+1 = δs−i+1 ,
i=1
i−1 i=1
i−1
which is equivalent to
δs + δs−2k−1 mod 2
Note that
m
(aγ+d,s − aγ,s ) + (aγ+d,s−2k−1 − aγ,s−2k−1 ) ≡ (δs + δs−2k−1 mod) m,
2
so similar to before, δs + δs−2k−1 ≡ 0 mod 2 if
(aγ+d,s + aγ+d,s−2k−1 ) − (aγ,s + aγ,s−2k−1 ) ≡ 0 mod 2.
Notice that this is equivalent to 0 mod 2 if s 6= 2k−1 b + 1 for some b. Assume then
that s = 2k−1 b + 1. Then

(aγ+d,s + aγ+d,s−2k−1 ) − (aγ,s + aγ,s−2k−1 )

= (aγ+d,2k−1 b+1 + aγ+d,2k−1 (b−1)+1 ) − (aγ,2k−1 b+1 + aγ,2k−1 (b−1)+1 )
Using γ + d = 2k−1 ((l − 1) + 1 + 2c), this is congruent to
(a∗(l−1)+1+2c,b+1 + a∗(l−1)+1+2c,b ) − (a∗(l−1)+1,b+1 + a∗(l−1)+1,b ) mod 2.
Like before, we still have that Pp (n1 )|c, so this is
(a∗(l−1)+1,b+1 + a∗(l−1)+1,b ) − (a∗(l−1)+1,b+1 + a∗(l−1)+1,b ) mod 2,
which is equivalent to 0 mod 2. Therefore, Lm (n) ≤ 2k−1 (l + 1).
(4): Assume n = pk11 pk22 · · · pkr t n1 and m = pl11 pl22 · · · plrt m1 with pi ∤ n1 , m1 for
every i and gcf (n1 , m1 ) = 1. We wish to show that
Lm (n) = max{Lpli (n) | 1 ≤ i ≤ t}.
i

Let γi = Lpli (n), γ = max{γi | 1 ≤ i ≤ t}, and d = Pm (n). We will have that
i

aγi +d,s ≡ aγi ,s mod plii

a1+d,s ≡ a1,s mod m1
for every s and every i. Then, since γ ≥ γi for every i, we have that
aγ+d,s ≡ aγ,s mod plii
aγ+d,s ≡ aγ,s mod m1 ,
which gives aγ+d,s ≡ aγ,s mod m.
If we had that Lm (n) < γ, then aγ+d−1,s ≡ aγ−1,s mod m would imply
l
aγ+d−1,s ≡ aγ−1,s mod plii for every i. But aγ+d−1,s 6≡ aγ−1,s mod pjj for some j,
which gives us a contradiction. Therefore, Lm (n) = γ.

16 MARK L. LEWIS AND SHANNON M. TEFFT

References
[1] Breuer, F. (1998). A Note on a Paper by Glaser and Schöffl. The Fibonacci Quarterly, 36(5),
463-466.

[2] Breuer, F. (1999). Ducci Sequences Over Abelian Groups. Communications in Algebra,
27(12), 5999-6013.

[3] Breuer, F. (2010). Ducci Sequences and Cyclotomic Fields. Journal of Difference Equations
and Applications, 16(7), 847-862.

[4] Brown, R. & Merzel, J. (2007). The Length of Ducci’s Four Number Game Rocky Mountain
Journal of Mathematics, 37(1), 45-65.

[5] Burmester, M., Forcade, R., & Jacobs, E. (1978) Circles of Numbers. Glasgow Mathematical
Journal, 19, 115-119.

[6] Chamberland, M. (2003). Unbounded Ducci Sequences. Journal of Difference Equations and
Applications, 9(10), 887-895.

[7] Dular, B. (2020). Cycles of Sums of Integers. Fibonacci Quarterly, 58(2), 126-139.

[8] Ehrlich, A. (1990). Periods in Ducci’s n-Number Game of Differences. Fibonacci Quarterly,
28(4), 302-305.

[9] Fine, N.J. (1947). Binomial Coefficients Modulo a Prime. The American Mathematical
Monthly, 54(10.1), 589-592.

[10] Freedman, B (1948). The Four Number Game. Scripta Mathematica, 14, 35-47.

[11] Glaser, H. & Schöffl, G. (1995). Ducci Sequences and Pascal’s Triangle. Fibonacci Quarterly,
33(4), 313-324.

[12] Lewis, M.L. & Tefft, S.M. (2024). The Period of Ducci Cycles on Z2l for Tuples of Length
2k . Submitted for Publication. <arXiv: 2401.17502>

[13] Lewis, M.L. & Tefft, S.M. (2024). Ducci on Zn m and the Maximum Length for n Odd.
Submitted for Publication. <arXiv: 2401.05319>

[14] Ludington Furno, A (1981). Cycles of differences of integers. Journal of Number Theory,
13(2), 255-261.

[15] Misiurewicz, M., & Schinzel, A. (1988). On n Numbers in a Circle. Hardy Ramanujan
Journal, 11, 30-39.

[16] Spivey, M. (2019) The Art of Proving Binomial Identities. Boca Raton, FL: Taylor and
Francis Group.

[17] Wong, F.B. (1982). Ducci Processes. The Fibonacci Quarterly, 20(2), 97-105.

Department of Mathematical Sciences, Kent State University, Kent, OH 44242

Email address: [email protected]

Department of Mathematical Sciences, Kent State University, Kent, OH 44242

Email address: [email protected]