On the Base-b Expansion of the Number of Trailing Zeros of b^{k}!

Antonio M. Oller-Marcén Departamento de Matemáticas Universidad de Zaragoza C/Pedro Cerbuna 12 50009 Zaragoza Spain

                    oller@unizar.es

José María Grau Departamento de Matematicas Universidad de Oviedo Avda. Calvo Sotelo, s/n, 33007 Oviedo Spain

                    grau@uniovi.es

Abstract

Let Z_{b}(n) denote the number of trailing zeroes in the base-b expansion of n!. In this paper we study the connection between the expression of ϑ(b) := lim_{n→∞} Z_{b}(n)/n in base b, and that of Z_{b}(b^{k}).

In particular, if b is a prime power, we will show the equality between the k digits of Z_{b}(b^{k}) and the first k digits in the fractional part of ϑ(b). In the general case we will see that this equality still holds except for, at most, the last ⌊log_{b}(k) + 3⌋ digits. We finally show that this bound can be improved if b is square-free and present some conjectures about this bound.

1 Introduction

In what follows we let Z_{b}(n) denote the number of trailing zeroes in the base-b expansion of n!. It is a classic topic in elementary number theory to compute the number of trailing zeroes of the base-10 expansion of the factorial of an integer; i.e., Z_{10}(n) (see [1, 2, 5] for instance and \underline{A027868} of The On-Line Encyclopedia of Integer Sequences). In fact, this question can be extended to arbitrary bases and the first author [6] studied in detail the behavior of the function Z_{b} (see \underline{A054861} for b = 3 and \underline{A011371} for b = 2).

This is an old topic which has recently drawn attention due to the increasing computing possibilities and to the populary of computer algebra systems. In fact, we can find many sequences in the OEIS which are related to this topic. For instance: \underline{A000966} (number of zeroes that n! will never end in), \underline{A173558} (the smallest number whose factorial has 10^{n} trailing zeroes), \underline{A173292} (numbers whose factorial has exactly 10^{n} trailing zeroes), \underline{A181582} (smallest prime p such that p! ends with exactly 10^{n} trailing zeroes) or \underline{A173345} (the number of trailing zeroes of n superfactorial) just to name a few.

In recent work (Hart et al. [3], motivated by Schmuland [7]), the following particularity about the number of trailing zeroes in the factorial of the powers of 10 (see \underline{A173228}) was shown:

Z_{10}(10) = 2,
Z_{10}(10^{2}) = 24,
Z_{10}(10^{3}) = 249,
Z_{10}(10^{4}) = 2499,
Z_{10}(10^{5}) = 24999,
Z_{10}(10^{6}) = 249998,
Z_{10}(10^{7}) = 2499999,
Z_{10}(10^{8}) = 24999999,
Z_{10}(10^{9}) = 249999998,
Z_{10}(10^{10}) = 2499999997.

Although the sequence of final 9’s is broken for some values of the exponent, it seems clear that the number of 9’s grows indefinitely. For instance,

Z_{10}(10^{50}) = 24999999999999999999999999999999999999999999999989,
Z_{10}(10^{100}) = 2499999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999982.

This behavior and the fact that the number of digits of Z_{10}(10^{m}) is m, motivated the study

of the asymptotic behavior of \frac{Z_{10}(10^{k})}{10^{k}} by Treuden [8], where it was shown (as suggested by the previous examples) that

lim_{n→∞} \frac{Z_{10}(n)}{n} = \frac{1}{4}.

Also, in [8] it was suggested (and was proved in [3]) that if b = p_{1}^{r_{1}} ⋯ p_{s}^{r_{s}}, then

lim_{n→∞} \frac{Z_{b}(n)}{n} = min_{1≤i≤s} \frac{1}{r_{i}(p_{i} − 1)}.

Now, it is natural to wonder about what will be the behavior of the digits of Z_{b}(b^{k}) for other values of b. Let us have a look at the case k = 20 for various values of b.

Z_{2}(2^{20}) = 1048575,
Z_{3}(3^{20}) = 1743392200,
Z_{4}(4^{20}) = 549755813887,
Z_{5}(5^{20}) = 23841857910156,
Z_{6}(6^{20}) = 1828079220031481,
Z_{7}(7^{20}) = 13298711049602000,
Z_{8}(8^{20}) = 384307168202282325,
Z_{9}(9^{20}) = 3039416364764232200,
Z_{10}(10^{20}) = 24999999999999999996,
Z_{11}(11^{20}) = 67274999493256000920,
Z_{12}(12^{20}) = 1916879996223737561074,
Z_{13}(13^{20}) = 1583746981240066619900,
Z_{14}(14^{20}) = 13944709237547466926759,
Z_{15}(15^{20}) = 83131418251991271972652,
Z_{16}(16^{20}) = 302231454903657293676543,
Z_{17}(17^{20}) = 254014462915473282650100,
Z_{18}(18^{20}) = 3187059054099019543609340,
Z_{19}(19^{20}) = 2088331858752553232964200,
Z_{20}(20^{20}) = 26214399999999999999999991,
Z_{21}(21^{20}) = 46369738241158591439532728,
Z_{30}(30^{20}) = 87169610024999999999999999987.

In the light of this data, it may seem that the only interesting behavior takes place at the multiples of 10. Nevertheless, this is not the case, as can be seen having a look at the base-b expansion of the considered number:

Z_{2}(2^{20}) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}_{2},
Z_{3}(3^{20}) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}_{3},
Z_{4}(4^{20}) = {1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}_{4},
Z_{5}(5^{20}) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}_{5},
Z_{6}(6^{20}) = {2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 5}_{6},
Z_{7}(7^{20}) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}_{7},
Z_{8}(8^{20}) = {2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2, 5}_{8},
Z_{9}(9^{20}) = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}_{9},
Z_{10}(10^{20}) = {2, 4, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 6}_{10},

Z_{11}(11^{20}) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}_{11},
Z_{12}(12^{20}) = {5, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 10}_{12},
Z_{13}(13^{20}) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}_{13},
Z_{14}(14^{20}) = {2, 4, 9, 4, 9, 4, 9, 4, 9, 4, 9, 4, 9, 4, 9, 4, 9, 4, 9, 1}_{14},
Z_{15}(15^{20}) = {3, 11, 3, 11, 3, 11, 3, 11, 3, 11, 3, 11, 3, 11, 3, 11, 3, 11, 3, 7}_{15},
Z_{16}(16^{20}) = {3, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15}_{16},
Z_{17}(17^{20}) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}_{17,}
Z_{18}(18^{20}) = {4, 8, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 14}_{18},
Z_{19}(19^{20}) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}_{19},
Z_{20}(20^{20}) = {4, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 11}_{20},
Z_{21}(21^{20}) = {3, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 5}_{21},
Z_{22}(22^{20}) = {2, 4, 8, 17, 13, 4, 8, 17, 13, 4, 8, 17, 13, 4, 8, 17, 13, 4, 8, 14}_{22},
Z_{23}(23^{20}) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}_{23},
Z_{24}(24^{20}) = {7, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 18}_{24},
Z_{25}(25^{20}) = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}_{25}.

Of course, the origin of these cyclic repetitions is closely related to the periodic expression

of ϑ(b) = lim_{n→∞} \frac{Z_{b}(n)}{n} when expressed in the base b. In this paper we study the relation

between ϑ(b) and the base-b expansion of Z_{b}(b^{k}). If b is a prime power, we will show the equality between the k digits of Z_{b}(b^{k}) and the first k digits in the fractional part of ϑ(b) (i.e., ⌊ϑ(b)b^{k}⌋).

In the general case this equality does not hold. We are then interested in investigating the number of final digits of Z_{b}(b^{k}) which break the previous coincidence. To do so, let us consider η(b, k) := ⌊log_{b}(⌊ϑ(b)b^{k}⌋ − Z_{b}(b^{k})) + 1⌋. This represents the number of digits of the base-b expansion of ⌊ϑ(b)b^{k}⌋ − Z_{b}(b^{k}) and observe that the number of unequal final digits between ⌊ϑ(b)b^{k}⌋ and Z_{b}(b^{k}) is at most η(b, k) + 1. We will show that

η(b, k) ≤ ⌊log_{b} k + 2⌋

is the best possible upper bound for η(b, k). Nevertheless, we will improve this upper bound in the case when b is square-free and present some conjectures about this bound.

Observe that if ϑ(b) admits a finite expansion in base b (we will say that ϑ(b) is exact in base b), then it admits two different b-adic expansions: the finite natural one and the infinite one. Throughout the paper we will always consider the latter and we will understand the floor function as the truncation of the fractional part. Consequently, if ϑ(b) is exact, then ⌊ϑ(b)b^{k}⌋ is to be interpreted as ϑ(b)b^{k} − 1. For instance, if b = 10 and k = 6 then ϑ(10) = \frac{1}{4} and we will consider \frac{1}{4} = 0.24999 ⋯ Thus ⌊ϑ(10)10^{6}⌋ will be interpreted as 249999 = 250000 − 1 = ϑ(10)10^{6} − 1.

The paper is organized as follows. In Section 2 we present the basic facts and technical results that will be used in the rest of the paper. In Section 3 we study the prime-power case, establishing the equality between the k digits of Z_{b}(b^{k}) and the first k digits of the base-b expansion of ϑ(b). Finally, in Section 4, we study the general case, where the latter equality does not hold and give a bound to the number of unequal digits.

2 Technical results

In this section we present some technical results which will be very useful in the sequel. Some of them are well-known and are presented without proof. The section is divided into three parts, the first is devoted to results related to Z_{b}(b^{k}), the second mostly deals with the base-b expansion of ϑ(b) when b is a prime-power and the third one is devoted to present the main lemma which will be crucial in the paper.

2.1 Some results about Z_{b}(n)

We start this subsection with the following well-known lemma, which was first proved by Legendre [4], that we present without proof.

Lemma 1.

1. Z_{p}(n) = ∑_{i≥1} ⌊\frac{n}{p^{i}} ⌋ = \frac{n − σ_{p}(n)}{p − 1}, where σ_{p}(n) is the sum of the digits of the base-p ex-

pansion of n.

2. Z_{p^{r}}(n) = ⌊\frac{Z_{p}(n)}{r}⌋ for every r ≥ 1.

3. If b = p_{1}^{r_{1}} ⋯ p_{s}^{r_{s}}, then Z_{b}(n) = min_{1≤i≤s}Z_{p_{i}^{r_{i}}}(n).

As a straightforward consequence of the preceding lemma we obtain the following corollary.

Corollary 2. Let l be any integer and p be a prime. Then

Z_{p}(lp^{n}) = lZ_{p}(p^{n}) + Z_{p}(l).

Recall that ϑ(b) = lim_{n→∞} \frac{Z_{b}(n)}{n}. In previous work [3, 8] an explicit expression for ϑ(b) was given. Namely,

Proposition 3. If b = p_{1}^{r_{1}} ⋯ p_{s}^{r_{s}}, then

ϑ(b) = min_{1≤i≤s} \frac{1}{r_{i}(p_{i} − 1)}.

Remark 4. The sequence S_{n} = \frac{1}{ϑ(n)} appears in The On-Line Encyclopedia of Integer Se-

quences as sequence \underline{A090624}. It is interesting to observe that it was included in the Encyclopedia 5 years before the formula for ϑ(n) was found.

The following lemma will be of great importance in sections 3 and 4.

Lemma 5. Let k ≥ 0 be an integer.

1. If b > 1 is an integer, then:

0 < Z_{b}(b^{k+1}) − bZ_{b}(b^{k}).

2. If b is a prime power, then:

0 < Z_{b}(b^{k+1}) − bZ_{b}(b^{k}) < b.

Proof. 1. Fist of all observe that k⌊x⌋ ≤ ⌊kx⌋ for all k ∈ ℤ, x ∈ ℝ and that if x ∉ ℤ and kx ∈ ℤ the inequality is strict. Now, for some prime divisor of b (with exponent r in the decomposition of b) we have that:

bZ_{b}(b^{k}) = b ⌊\frac{1}{r}∑_{i≥1} ⌊\frac{b^{k}}{p^{i}} ⌋⌋ < ⌊\frac{1}{r} ∑_{i≥1} ⌊\frac{b^{k+1}}{p^{i}} ⌋⌋ = Z_{b}(b^{k+1}),

since \frac{b^{k}}{p^{r(k+1)}} is not an integer, while b\frac{b^{k}}{p^{r(k+1)}} is.

2. Put b = p^{n}. Then, Corollary 2 implies that Z_{p}(p^{(k+1)n}) = p^{n}Z_{p}(p^{kn}) + Z_{p}(p^{n}).

Now, if r is the reminder of the division between Z_{p}(p^{(k+1)n}) and n and s is the reminder of the division between Z_{p}(p^{kn}) and n it follows that

Z_{p^{n}}(p^{(k+1)n}) = \frac{Z_{p}(p^{(k+1)n}) − r}{n},

Z_{p^{n}}(p^{kn}) = \frac{Z_{p}(p^{kn}) − s}{n}.

Thus, since 0 ≤ r, s ≤ n − 1, we have

Z_{p^{n}}(p^{(k+1)n}) − p^{n}Z_{p^{n}}(p^{kn}) = \frac{Z_{p}(p^{n}) + p^{n}s − r}{n} ≤ \frac{Z_{p}(p^{n}) + p^{n}s}{n}

= \frac{\frac{p^{n}−1}{p−1} + p^{n}s}{n} < \frac{p^{n} + p^{n}s}{n}

≤ \frac{p^{n} + p^{n}(n − 1)}{n} = p^{n}.

2.2 The base-p^{n} expansion of ϑ(p^{n})

Let us start by introducing some notation. With q = \{d.d_{1}d_{2} ⋯ d_{t} \overbrace{d_{t+1} ⋯ d_{t+s}}\}_{b} we mean that the fractional part of q in base b consists of t digits followed by a periodic sequence of s digits (d_{t+i} = d_{t+i+s} for all i > 0). Clearly t can be arbitrarily large and the length of the period can be any multiple of s, so we will usually assume that t and s are minimal. We will say that q is exact in base b if there exists k ≥ 1 such that d_{i} = 0 for every i ≥ k or d_{i} = b − 1 for every i ≥ k; i.e.,

q = \{d.d_{1}d_{2} ⋯ d_{t} \overbrace{b − 1} \}_{b} = \{d.d_{1}d_{2} ⋯ d_{t} + 1 \overbrace{0} \}_{b}

Lemma 6. Let p be a prime and 1 ≤ r ∈ ℤ. Then \frac{1}{r(p − 1)} is exact in base p^{r} if and only

if p = 2 and r is a power of 2.

Proof. This is a straightforward consequence from the fact that \frac{1}{n} is exact in base p^{r} if and only if rad(n) = p; i.e., if and only if n is a power of p.

Now we will present some results about the base-b expansion of ϑ(b) when b = p^{n} is a prime-power.

Lemma 7. Let p be a prime and b = p^{n} with n ∈ ℕ. Then

ϑ(p^{n}) = \{0.d_{1}d_{2} ⋯ d_{t} \overbrace{d_{t+1} ⋯ d_{t+s}}\}_{b} ⟺ \frac{p^{nt}}{n} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ.

Proof. First of all observe that

\frac{p^{nt}}{n} ∑_{i=0}^{sn−1} p^{i} = \frac{p^{nt}(p^{sn} − 1)}{n(p − 1)} = b^{t}ϑ(p^{n})(b^{s} − 1).

Let us suppose that ϑ(p^{n}) = \{0.d_{1}d_{2} ⋯ d_{t} \overbrace{d_{t+1} ⋯ d_{t+s}}\}_{b}. Then we have that

b^{t}ϑ(p^{n}) = \{d_{1}d_{2} ⋯ d_{t}. \overbrace{d_{t+1} ⋯ d_{t+s}}\}_{b},
b^{t+s}ϑ(p^{n}) = \{d_{1}d_{2} ⋯ d_{t}d_{t+1} ⋯ d_{t+s}. \overbrace{d_{t+1} ⋯ d_{t+s}}\}_{b}.

and it is enough to subtract both expressions to obtain that b^{t}ϑ(p^{n})(b^{s} − 1) ∈ ℤ.

Conversely, assume that b^{t}ϑ(p^{n})(b^{s} − 1) ∈ ℤ. It is easy to see that there exists a sequence {d_{i}}_{i∈ℕ} ⊂ ℕ, not eventually null, such that

ϑ(p^{n}) = ∑_{i=1}^{∞} d_{i}p^{−ni} with 0 ≤ d_{i} < b, ∀i ∈ ℕ.

Consequently,

b^{t}ϑ(p^{n}) = z_{1} + ∑_{i=1}^{∞} d_{t+i}p^{−ni} with z_{1} ∈ ℤ,
b^{(t+s)}ϑ(p^{n}) = z_{2} + ∑_{i=1}^{∞} d_{t+s+i}p^{−ni} with z_{2} ∈ ℤ,

where

0 < ∑_{i=1}^{∞} d_{t+i}p^{−ni} ≤ 1,

0 < ∑_{i=1}^{∞} d_{t+s+i}p^{−ni} ≤ 1.

Since b^{(t+s)}ϑ(p^{n}) − b^{t}ϑ(p^{n}) = b^{t}ϑ(p^{n})(b^{s} − 1) ∈ ℤ we have that

∑_{i=1}^{∞} d_{t+s+i}p^{−ni} = ∑_{i=1}^{∞} d_{t+i}p^{−ni}.

From this fact it readily follows that d_{t+i} = d_{t+s+i} and the proof is complete. Lemma 8. Let p be a prime, b = p^{n}, and (n, s, k) ∈ ℕ^{3}. Then

\frac{b^{k}}{n} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ ⟺ \frac{b}{n} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ.

Or, in other words,

\frac{p^{nk}(p^{sn} − 1)}{n(p − 1)} ∈ ℤ ⟺ \frac{p^{n}(p^{sn} − 1)}{n(p − 1)} ∈ ℤ.

Proof. We can write n = p^{r}n′ with r ≥ 0 and gcd(p, n′) = 1. Then b^{k} = p^{kn} = p^{p^{r}n′k} and observe that r < p^{r} < p^{r}n′ < p^{r}n′k.

Assume that \frac{b^{k}}{n} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ, then \frac{p^{p^{r}n′k−r}}{n′} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ and, since gcd(p, n′) = 1 it follows

that \frac{1}{n′} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ and \frac{p^{p^{r}n′−r}}{n′} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ. But \frac{p^{p^{r}n′−r}}{n′} = \frac{b}{n} and we are done.

The converse is obvious. Corollary 9. The base-p^{n} expansion of ϑ(p^{n}) is pure periodic or mixed periodic with only one non-periodic figure; i.e., either ϑ(p^{n}) = \{0.d_{1} \overbrace{d_{2} ⋯ d_{s+1}}\}_{p^{n}} with d_{s+1} ≠ d_{1} or ϑ(p^{n}) = \{0. \overbrace{d_{1} ⋯ d_{s}}\}_{p^{n}}

Proof. If ϑ(p^{n}) = \{0.d_{1}d_{2} ⋯ d_{t} \overbrace{d_{t+1} ⋯ d_{t+s}}\}_{p^{n}}, then we have that \frac{p^{nt}}{n} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ. By the pre-

vious lemma this implies that \frac{p^{n}}{n} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ and, consequently, ϑ(p^{n}) = \{0.d_{1} \overbrace{d_{2} ⋯ d_{s+1}}\}_{p^{n}}.

Finally, if d_{s+1} = d_{1}, then ϑ(p^{n}) is pure periodic and this completes the proof.

2.3 The main lemma

The following lemma will be crucial in the next section. Lemma 10. Let {S_{n}}_{n∈ℕ} be a sequence of integers and define Δ_{1} := S_{1} and Δ_{n} := S_{n+1}−bS_{n}. If 0 < Δ_{n} < b, for all n ∈ ℕ, then the following items hold:

1. S_{n} = ∑_{i=1}^{n} b^{n−i}Δ_{i}.

2. ⌊log_{b} S_{n}⌋ + 1 = n.

3. ℓ := lim_{n→∞} \frac{S_{n}}{b^{n}} = ∑_{i=1}^{∞} b^{−i}Δ_{i}.

4. If Δ_{i} = (b − 1) for all i > 1, then S_{k} = ℓb^{k} − 1 for every k > 1.

5. If ℓ is not exact in base b, then S_{k} = ⌊ℓb^{k}⌋ for every k.

6. If ℓ = ∑_{i=1}^{∞} b^{−i}Δ_{n} ∈ ℚ, then there exists (t, s) ∈ ℕ^{2} with s > 0 such that Δ_{n+s} = Δ_{n}

(and S_{n+s} = S_{n}) for all n > t. Proof. 1. It follows from inductive arguments, since S_{1} = Δ_{1}.

2. Consequence of (1).

3. Observe that \frac{S_{n}}{b^{n}} = ∑_{i=1}^{n} b^{−i}Δ_{i} and take limits.

4. We must consider two cases.

If Δ_{1} < (b − 1), then ℓ = \frac{(Δ_{1}+1)}{b}, ℓb^{k} − 1 = (Δ_{1} + 1)b^{k−1} − 1 and also

S_{k} = ∑_{i=1}^{k} b^{k−i}Δ_{i} = Δ_{1}b^{k−1} + ∑_{i=2}^{k} b^{k−i}(b − 1) = Δ_{1}b^{k−1} + b^{k−1} − 1.

Now, if Δ_{1} = b − 1, then ℓ = 1 and

S_{k} = ∑_{i=1}^{k} b^{k−i}(b − 1) = ∑_{i=1}^{k} b^{k+1−i} − ∑_{i=1}^{k} b^{k−i} = b^{k} − 1.

5. Observe that

ℓb^{k} = ∑_{i=1}^{∞} b^{k−i}Δ_{i} = ∑_{i=1}^{k} b^{k−i}Δ_{i} + ∑_{i=1}^{∞} b^{−i}Δ_{i+k}.

Now, if ℓ is not exact, it follows that ∑_{i=1}^{∞} b^{−i}Δ_{i+k} < 1 and consequently,

⌊ℓb^{k}⌋ = ⌊∑_{i=1}^{k} b^{k−i}Δ_{i} + ∑_{i=1}^{∞} b^{−i}Δ_{i}⌋ = ∑_{i=1}^{k} b^{k−i}Δ_{i} = S_{k}.

6. It is clear since the base-b expansion of any rational number is periodic.

3 The prime power case

The next theorem establishes the equality between the digits of the base-b expansion of Z_{b}(b^{k}) and the first k digits of the base-b expansion of ϑ(b) if b is a prime power. In passing we will also prove some other interesting properties.

Theorem 11. Let p be a prime and b = p^{n}. Consider the sequence a_{1} = Z_{b}(b), a_{k} :=

Z_{b}(b^{(k+1)}) − bZ_{b}(b^{k}) and let s be the smallest integer such that θ := \frac{b}{n} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ. Then, the

following items hold:

1. Z_{b}(b^{k}) = ∑_{i=1}^{k} a_{i}b^{k−i}.

2. ϑ(b) = lim_{n→∞} \frac{Z_{b}(b^{n})}{b^{n}} = ∑_{i=1}^{∞} b^{−i}a_{i}.

3. The base-b expansion of ϑ(b) is

ϑ(b) = \begin{cases}\{0.a_{1} \overbrace{a_{2} ⋯ a_{s+1}}\}_{b}, & if \frac{θ}{b} ∉ ℤ ; \\ \{0. \overbrace{a_{1}a_{2} ⋯ a_{s}}\}_{b} & if \frac{θ}{b} ∈ ℤ . \end{cases}

4. a_{k} = a_{k+s} for all k > 1. Moreover, if \frac{θ}{b} ∈ ℤ, then a_{k} = a_{k+s} for all k > 0.

5.

#\{a_{k}\}_{i∈ℕ} = \begin{cases}s, & if \frac{θ}{b} ∈ ℤ; \\ s + 1, otherwise. \end{cases}

6. If \frac{θ}{b} ∈ ℤ, then Z_{b}(b^{s}) = \frac{θ}{b}. Otherwise, Z_{b}(b^{s+1}) = θ + Z_{b}(b).

7. If b + 1 is not a Fermat number, then Z_{b}(b^{k}) = ⌊b^{k}ϑ(b)⌋.

8. If b + 1 is a Fermat number, then Z_{b}(b^{k}) = b^{k}ϑ(b) − 1.

Proof. First of all observe that, due to Corollary 9, there exists an integer s such that

θ = \frac{b}{n} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ or, equivalently, such that ϑ(p^{n}) = \{0.d_{1} \overbrace{d_{2} ⋯ d_{s+1}}\}_{b}. Moreover, if \frac{1}{n} ∑_{i=0}^{sn−1} p^{i} ∈ ℤ,

then ϑ(p^{n}) = \{0. \overbrace{d_{1} ⋯ d_{s}}\}_{b}. Also, by Lemma 2, we have that 0 < a_{k} < b so we are in the conditions of Lemma 10.

After these considerations we can proceed to the proof of the theorem.

1. Apply Lemma 10(1).

2. Apply Lemma 10(3).

3. Due to Corollary 9.

4. Idem.

5. Obvious by the minimality of s.

6. If \frac{θ}{b} ∈ ℤ, then \frac{1}{n} ∑_{i=0}^{sn−1} p^{i} = \frac{θ}{b} ∈ ℤ. This implies that ϑ(b) = \{0. \overbrace{a_{1}a_{2} ⋯ a_{s}}\}_{b}, so b^{s}ϑ(b) =

\{a_{1}a_{2} ⋯ a_{s}. \overbrace{a_{1}a_{2} ⋯ a_{s}}\}_{b} and, consequently,

\frac{θ}{b} = ϑ(b)(b^{s} − 1) = ∑_{i=1}^{s} a_{i}b^{k−i} = Z_{b}(b^{s}).

Now, if \frac{θ}{b} ∉ ℤ then \frac{b}{n} ∑_{i=0}^{sn−1} p^{i} = θ ∈ ℤ so ϑ(b) = \{0.a_{1} \overbrace{a_{2}a_{3···}a_{s+1}}\}_{b} and it follows that

b^{s+1}ϑ(b) = \{a_{1}a_{2} ⋯ a_{s+1}. \overbrace{a_{2}a_{3} ⋯ a_{s+1}}\}_{b},
bϑ(b) = \{a_{1}. \overbrace{a_{2}a_{3} ⋯ a_{s+1}}\}_{b}.

Consequently,

θ = \frac{b}{n} ∑_{i=0}^{sn−1} p^{i} = bϑ(b)(b^{s} − 1) = ∑_{i=1}^{s+1} a_{i}b^{k−i} − a_{1} = Z_{b}(b^{s+1}) − Z_{b}(b).

7. If p^{n} + 1 is not a Fermat number, then ϑ(p^{n}) is not exact due to Lemma 7. Then, it is enough to apply Lemma 10(5).

8. If p^{n} + 1 is a Fermat number; then p = 2 and n is a power of 2. In this case ϑ(p^{n}) is exact and Lemma 10(4) applies.

Let us recall that a base-b repunit with k digits, R_{k}^{(b)}, is an integer whose base-b expansion consists exactly of k ones; i.e.,

R_{k}^{(b)} := \{ \overbrace{1, 1, …, 1}^{k} \}_{b} = ∑_{i=0}^{k−1} b^{i} = \frac{b^{k} − 1}{b − 1}.

In the same way, a base-b repdigit with k digits is a multiple of a base-b repunit with k digits, i.e., an integer of the form αR_{k}^{(b)} = \{ \overbrace{α, α, …, α}^{k} \}_{b} with 1 ≤ α ≤ b − 1.

Proposition 12. Let p be a prime. If \frac{1}{n} ∑_{i=0}^{n−1} p^{i} = \frac{R_{n}^{(p)}}{n} ∈ ℤ, then Z_{p^{n}}(p^{nk}) is a base-p^{n} repdigit

with k digits for all k ∈ ℤ. Namely,

Z_{p^{n}}(p^{nk}) = \frac{R_{n}^{(p)}R_{k}^{(p^{n})}}{n} .

Proof. Theorem 11 implies that ϑ(p^{n}) = \{0. \overbrace{a_{1}}\}_{p^{n}}, where a_{1} = \frac{R_{n}^{(p)}}{n}. Consequently,

Z_{p^{n}}(p^{nk}) = \{ \overbrace{a_{1}, a_{1}, …, a_{1}}^{k} \}_{p^{n}} = \frac{R_{n}^{(p)}}{n} R_{k}^{(p^{n})}.

It is interesting to particularize the previous result for n = 1, 2.

Corollary 13. Let p be a prime. Then Z_{p}(p^{k}) is a base-p repunit with k digits for every integer k.

Proof. Follows immediately from the previous proposition, since \frac{R_{1}^{(p)}}{1} = 1 ∈ ℤ.

Corollary 14. Let p be an odd prime, then Z_{p^{2}}(p^{2k}) is a base-p^{2} repdigit.

Proof. If p is odd, then \frac{R_{2}^{(p)}}{2} = \frac{p + 1}{2} ∈ ℤ.

If p is odd, the above corollary can be generalized for any power of 2. Namely, we have the following.

Proposition 15. If p is an odd prime, then Z_{p^{2^{m}}}(p^{2^{m}k}) is a base-p^{2^{m}k} repdigit.

Proof. \frac{R_{2^{m}}^{(p)}}{2^{m}} = \frac{1}{2^{m}} ∏_{i=0}^{m−1}(1 + p^{2^{i}}) ∈ ℤ.

Remark 16. We have seen that ϑ(p) = \{ 0. \overbrace{1} \}_{p} for every prime p. Nevertheless, the set of pairs (b_{1}, b_{2}) ∈ ℤ^{2} such that the base-b_{1} expansion of ϑ(b_{1}) and the base b_{2} expansion of ϑ(b_{2}) coincide seems to be very small. In fact for b_{i} ≤ 40000 there are only two such couples. Namely,

ϑ(81) = \{ 0. \overbrace{10} \}_{81} and ϑ(361) = \{0. \overbrace{10} \}_{361}.
ϑ(343) = \{ 0. \overbrace{19} \}_{343} and ϑ(1369) = \{ 0. \overbrace{19} \}_{1369}.

4 The general case

If b is not a prime power, there is no equality between the k digits of Z_{b}(b^{k}) and the first k digits of the base-b expansion of ϑ(b). As a consequence, Z_{b}(b^{k}) presents certain anomalies in its final digits (see \underline{A174807}). For instance,

Z_{10}(10^{9}) = 249999998,
Z_{10}(10^{99}) = 249999999 ⋯ 99999980,
Z_{10}(10^{999}) = 249999999 ⋯ 99999791,
Z_{10}(10^{9999}) = 249999999 ⋯ 999997859.

Or, in a different base,

Z_{6}(6^{5}) = {2, 5, 5, 5, 4}_{6},
Z_{6}(6^{6^{2}−1}) = {2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, …, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1}_{6},
Z_{6}(6^{6^{3}−1}) = {2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, …, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 5}_{6},
Z_{6}(6^{6^{4}−1}) = {2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, …, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 0, 3, 4}_{6},
Z_{6}(6^{6^{5}−1}) = {2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, …, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 0, 3, 3, 4}_{6}.

If ϑ(b) is not exact it is clear that any convergent sequence with limit ϑ(b) will share with this value an increasing number of digits. To prove that this is still true even if ϑ(b) is exact (like in the previous examples, where ϑ(10) = {0.25}_{10} and ϑ(6) = {0.3}_{6}) we need to prove the following result.

Proposition 17. The sequence \{γ_{k}\}_{k≥1} := \{\frac{Z_{b}(b^{k})}{b^{k}}\}_{k≥1} is strictly increasing. As a conse-

quence, \frac{Z_{b}(b^{k})}{b^{k}} < lim_{n→∞} \frac{Z_{b}(n)}{n} for every k > 0.

Proof. \frac{γ_{k+1}}{γ_{k}} = \frac{Z_{b}(b^{k+1})}{bZ_{b}(b^{k})} > 1 due to Lemma 5(1).

We have already seen in the previous section that if b is a prime power, then the number of digits of the base-b expansion of Z_{b}(b^{k}) is exactly k. Now we will see that this is also true for a general b.

Proposition 18. The number of digits of the base-b expansion of Z_{b}(b^{k}) is exactly k; i.e.,

⌊log_{b} Z_{b}(b^{k})⌋ + 1 = k.

Proof. By Lemma 2 (1), we know that bZ_{b}(b^{k}) < Z_{b}(b^{(k+1)}). Taking logarithms we have 1 + log_{b} Z_{b}(b^{k}) < log_{b} Z_{b}(b^{k+1}), which clearly implies that ⌊log_{b} Z_{b}(b^{k})⌋ < ⌊log_{b} Z_{b}(b^{k+1})⌋.

Thus, the number of digits of the base-b expansion of Z_{b}(b^{k+1}) is greater than that of Z_{b}(b^{k}). Since ⌊log_{b} Z_{b}(b)⌋ = 0, it follows that 1 + ⌊log_{b} Z_{b}(b^{k})⌋ ≥ k.

Let us see now that the equality holds. Assume, on the contrary, that 1+⌊log_{b} Z_{b}(b^{k_{0}})⌋ > k_{0} for certain k_{0}. Then 1 + ⌊log_{b} Z_{b}(b^{m})⌋ > m for every m ≥ k_{0}. This clearly implies that \frac{Z_{b}(b^{m})}{b^{m}} > 1 for every m > k_{0} and ϑ(b) = lim_{n→∞} \frac{Z_{b}(b^{m})}{b^{m}} ≥ 1, which is clearly a contradiction

since by definition ϑ(b) ≤ 1, the equality only holds for b = 2 and \frac{Z_{2}(2^{m})}{2^{m}} = \frac{2^{m} − 1}{2^{m}} < 1.

We have seen that in the general case the equality between the k digits of Z_{b}(b^{k}) and the first k digits of the base-b expansion of ϑ(b) does not hold. It is then interesting to study how many digits differ.

To do so, let us introduce some notation:

α(b, k) = ⌊ϑ(b)b^{k}⌋ − Z_{b}(b^{k}).
η(b, k) = ⌊log_{b} α(b, k) + 1⌋.

Observe that the number of different digits that we are studying is, at most, η(b, k)+1. Now we can give an upper bound for η(b, k).

Theorem 19. The number of digits of the base-b expansion of α(b, k) is smaller or equal than the number of digits of the base-b expansion of k, plus 1; i.e.,

η(b, k) ≤ ⌊log_{b} k + 2⌋.

Proof. If k = 1, then ⌊ϑ(b)b⌋ − Z_{b}(b) ≤ b, since ϑ(b) ≤ 1 and Z_{b}(b) ≥ 0. This implies that η(b, 1) = ⌊log_{b} (⌊ϑ(b)b⌋ − Z_{b}(b)) + 1⌋ ≤ ⌊log_{b} b + 1⌋ = 2 = ⌊log_{b} k + 2⌋, as claimed.

Now, let k ≥ 2. Put b = p_{1}^{r_{1}} ⋯ p_{s}^{r_{s}} and assume, without loss of generality, that p_{1} is

such that min_{1≤i≤s} \frac{1}{r_{i}(p_{i} − 1)} = \frac{1}{r_{1}(p_{1} − 1)}. In that case Z_{b}(b^{k}) = ⌊\frac{b^{k} − σ_{p_{1}}(b^{k})}{r_{1}(p_{1} − 1)}⌋ and ϑ(b) =

\frac{1}{r_{1}(p_{1} − 1)}. Also observe that if β = \frac{b}{p_{1}^{r_{1}}} , then σ_{p_{1}}(b^{k}) = σ_{p_{1}}(β^{k}). Now

⌊ϑ(b)b^{k}⌋ − Z_{b}(b^{k}) = ⌊ϑ(b)b^{k}⌋ − ⌊\frac{b^{k} − σ_{p_{1}}(b^{k})}{r_{1}(p_{1} − 1)}⌋ ≤ \frac{b^{k} − (b^{k} − σ_{p_{1}}(b^{k}))}{r_{1}(p_{1} − 1)} + 1

= 1 + \frac{σ_{p_{1}}(β^{k})}{r_{1}(p_{1} − 1)} ≤ 1 + \frac{(p_{1} − 1)(1 + ⌊log_{p_{1}} β^{k}⌋}{r_{1}(p_{1} − 1)}

= 1 + \frac{1 + ⌊log_{p_{1}} β^{k}⌋}{r_{1}} ≤ 2 + ⌊log_{p_{1}} β^{k}⌋ = ⌊log_{p_{1}} p_{1}^{2}β^{k}⌋

≤ ⌊log_{p_{1}} b^{k}⌋.

Consequently we find

η(b, k) = ⌊log_{b} (⌊ϑ(b)b^{k}⌋ − Z_{b}(b^{k})) + 1⌋ ≤ ⌊log_{b} (⌊log_{p_{1}} b^{k}⌋)⌋ + 1 ≤ ⌊log_{b}(k log_{p_{1}} b)⌋ + 1
= ⌊log_{b} k + log_{b} log_{p_{1}} b⌋ + 1 ≤ ⌊log_{b} k⌋ + 2 = ⌊log_{b} k + 2⌋.

Remark 20. The bound obtained in the previous theorem is the best possible one. In fact, there exists values of the pair (b, k) such that η(b, k) = ⌊log_{b} k + 2⌋. Namely, if k = b − 1 and b < 1000 the following values:

b = 120, 180, 240, 336, 360, 378, 420, 448, 504, 560, 630, 672, 720, 756, 840, 945

satisfy the equation η(b, b − 1) = 2 = ⌊log_{b}(b − 1) + 2⌋.

Corollary 21. The number of unequal digits between Z_{b}(b^{k}) and the first k digits of the base-b expansion of ϑ(b) is smaller or equal than the number of digits of k plus 2.

Proof. The number of unequal digits is, at most, η(b, k) + 1 which, by the previous theorem, is smaller or equal than (⌊log_{b} k⌋ + 1) + 2.

Remark 22. It is interesting to observe that, as far as the authors have been able to test computationally, the inequality given in the preceding corollary is strict. Nevertheless we have not found a proof for this fact, so it remains a conjecture.

Conjecture 23. The number of unequal digits between Z_{b}(b^{k}) and the first k digits of the base-b expansion of ϑ(b) is smaller or equal than the number of digits of k plus 1.

If b is square-free, we can improve the bound given in Theorem 19.

Proposition 24. Let b = p_{1} ⋯ p_{s} be a square-free integer (s ≥ 2). Then ϑ(b)b^{k} − Z_{b}(b^{k}) ≤ k(s − 1) for every k. As a consequence η(b, k) ≤ ⌊log_{b} k + log_{b}(s − 1) + 1⌋ ≤ ⌊log_{b} k + 1.21⌋.

Proof. We can suppose, without loss of generality, that p_{1} is the greatest prime in the decom-

position of b. Then ϑ(b)b^{k} = \frac{b^{k}}{p_{1} − 1} and also Z_{b}(b^{k}) = Z_{p_{1}}(b^{k}) = \frac{b^{k} − σ_{p_{1}}(b^{k})}{p_{1} − 1}. Consequently

ϑ(b)b^{k} − Z_{b}(b^{k}) = \frac{σ_{p_{1}}(b^{k})}{p_{1} − 1} = \frac{σ_{p_{1}}(p_{2}^{k} ⋯ p_{s}^{k})}{p_{1} − 1}.

Now, since (p_{2} ⋯ p_{s})^{k} < p_{1}^{k(s−1)} it follows that σ_{p_{1}}(p_{2}^{k} ⋯ p_{s}^{k}) ≤ (p_{1} − 1)k(s − 1) so we get that ϑ(b)b^{k} − Z_{b}(b^{k}) ≤ k(s − 1).

To end the proof it is enough to recall the definition of η(b, k) and to observe that log_{b}(s − 1) ≤ log_{30}(2) < 0.21.

Remark 25. The previous proposition can be refined in some special cases. For instance,

1. If b is the product of 2 distinct primes; i.e., if s = 2 in the proposition, then η(b, k) ≤ ⌊log_{b} k + 1⌋.

2. If b is square-free and k is a power of b, then

η(b, k) = η(b, b^{m}) ≤ ⌊m + 1.21⌋ = m + 1 = ⌊log_{b} k + 1⌋.

This remark motivates this final conjecture, which remains open, that closes the paper.

Conjecture 26. If b is a square-free integer, then η(b, k) ≤ ⌊log_{b} k + 1⌋.

5 Acknowledgement

The authors would like to thank the referee for his/her useful suggestions and improvements.

References

[1] Harriet Griffin. Elementary Theory of Numbers. McGraw-Hill, 1954.

[2] Hansraj Gupta. Selected Topics in Number Theory. Abacus Press, 1980.

[3] D. S. Hart, J. E. Marengo, D. A. Narayan, and D. S. Ross. On the number of trailing zeros in n! College Math. J., 39 (2008), 139–145.

[4] A. M. Legendre. Essai sur la Théorie des Nombres. Cambridge University Press, 2009.

[5] I. Niven, H. S. Zuckerman, and H. L. Montgomery. An Introduction to the Theory of Numbers. John Wiley & Sons Inc., 1991.

[6] A. M. Oller-Marcén. A new look at the trailing zeroes of n!. Preprint, June 26 2009.

   Available at http://arxiv.org/abs/0906.4868.

[7] B. Schmuland. Shouting factorials. Pi in the Sky, 7 (2003), 10–12.

[8] M. L. Treuden. Frequencies of digits in factorials: an experimental approach. College Math. J., 25 (1994), 48–55.

2010 Mathematics Subject Classification: Primary 11B99; Secondary 11A99. Keywords: Factorial, trailing zeroes, base-b expansion.

(Concerned with sequences \underline{A000966}, \underline{A011371}, \underline{A027868}, \underline{A054861}, \underline{A090624}, \underline{A173228}, \underline{A173292}, \underline{A173293}, \underline{A173345}, \underline{A173558}, \underline{A174807}, and \underline{A181582}.)

Received February 25 2011; revised version received June 7 2011. Published in Journal of Integer Sequences, June 10 2011.

Return to Journal of Integer Sequences home page.