On Arithmetic Progressions of Integers with a Distinct Sum of Digits

Carlo Sanna Italy

                   carlo.sanna.dev@gmail.com

Abstract Let b ≥ 2 be a fixed integer. Let s_{b}(n) denote the sum of digits of the nonnegative integer n in the base-b representation. Further let q be a positive integer. In this paper we study the length k of arithmetic progressions n, n + q, …, n + q(k − 1) such that s_{b}(n), s_{b}(n + q), …, s_{b}(n + q(k − 1)) are (pairwise) distinct. More specifically, let L_{b,q} denote the supremum of k as n varies in the set of nonnegative integers ℕ. We show that L_{b,q} is bounded from above and hence finite. Then it makes sense to define μ_{b,q} as the smallest n ∈ ℕ such that one can take k = L_{b,q}. We provide upper and lower bounds for μ_{b,q}. Furthermore, we derive explicit formulas for L_{b,1} and μ_{b,1}. Lastly, we give a constructive proof that L_{b,q} is unbounded with respect to q.

1 Introduction

Let b ≥ 2 be a fixed integer and let s_{b}(n) denote the sum of digits of the nonnegative integer n in the base-b representation. Further let q a positive integer, we are interested in the length k of arithmetic progressions n, n + q, …, n + q(k − 1) such that the integers s_{b}(n), s_{b}(n + q), …, s_{b}(n + q(k − 1)) are (pairwise) distinct.

There are known results on the asymptotic behavior of the sum of digits function [2, 4], and about its distribution along arithmetic progressions [3, 5]. But, to our knowledge, this particular problem has not been studied before.

More specifically, let L_{b,q} denote the supremum of k as n varies in the set of nonnegative integers ℕ. We show that L_{b,q} is bounded from above and hence finite. As a consequence, it makes sense to define μ_{b,q} as the smallest n ∈ ℕ such that one can take k = L_{b,q}. Then, we provide upper and lower bounds for μ_{b,q}. Everything allows for an effective computation of L_{b,q} and μ_{b,q} by checking a finite number of candidates, though this is feasible in a short amount of time only for small values of b and q. Furthermore, we derive explicit formulas for L_{b,1} and μ_{b,1}. Lastly, we give a constructive proof that L_{b,q} is unbounded with respect to q, in the sense that sup_{q∈ℕ^{+}} L_{b,q} = +∞.

2 Bounds for L_{b,q} and μ_{b,q}

Theorem 1. Let m be the least positive integer such that

m(b − 1) + 1 ≤ ⌊\frac{b^{m}}{q} ⌋ .  (1)

Then L_{b,q} ≤ 2⌊b^{m}/q⌋.

Proof. Let n ∈ ℕ, k ∈ ℕ^{+} and A := {n + qi : i = 0, 1, …, k − 1} such that s_{b}(n), s_{b}(n + q), …, s_{b}(n + q(k − 1)) are distinct. For any t ∈ ℕ we define A_{t} := A ∩ [tb^{m}, (t + 1)b^{m} − 1]. For convenience, take M := ⌊b^{m}/q⌋. Then for all nonnegative integers t < u the following statements are true:

(i). |A_{t}| ≤ M.

(ii). A_{t}, A_{u} ≠ ∅ ⇒ ∀v ∈ ℕ, t < v < u |A_{v}| = M.

(iii). |A_{t}| = M, t ≢ −1 (mod b) ⇒ ∀u ∈ ℕ, u > t A_{u} = ∅.

(iv). |A_{t}| = M, t ≢ 0 (mod b) ⇒ ∀u ∈ ℕ, u < t A_{u} = ∅.

(i). For all a ∈ A_{t} we have s_{b}(a) = s_{b}(t) + s_{b}(a mod b^{m}) and therefore

s_{b}(A_{t}) := {s_{b}(a) : a ∈ A_{t}} ⊆ {s_{b}(t), s_{b}(t) + 1, …, s_{b}(t) + m(b − 1)},  (2)

so by the hypotheses |A_{t}| = |s_{b}(A_{t})| ≤ m(b − 1) + 1 ≤ M.

(ii). Since A_{t}, A_{u} are nonempty we have n < vb^{m} and (v + 1)b^{m} − 1 < n + q(k − 1). Then

|A_{v}| = |{qi : i = 0, …, k − 1} ∩ [vb^{m} − n, (v + 1)b^{m} − n − 1] |
= |qℕ ∩ [vb^{m} − n, (v + 1)b^{m} − n − 1[ | ≥ ⌊\frac{b^{m}}{q} ⌋ = M,  (3)

because |qℕ ∩ [x, y]| ≥ ⌊(y − x + 1)/q⌋ for any integers y ≥ x ≥ 0. From point (i) it follows that |A_{v}| = M.

(iii). We have s_{b}(t + 1) = s_{b}(t) + 1. Suppose by contradiction that A_{t+1} is nonempty, so there exists a := min(A_{t+1}). Now s_{b}(a) = s_{b}(t) + 1 + s_{b}(a mod b^{m}) and, since |A_{t}| = M implies s_{b}(A_{t}) = {s_{b}(t), s_{b}(t) + 1, …, s_{b}(t) + m(b − 1)}, then necessarily s_{b}(a mod b^{m}) = m(b − 1), so that a = (t + 2)b^{m} − 1. In fact, s_{b}(a mod b^{m}) ≤ m(b − 1) and if we suppose s_{b}(a mod b^{m}) < m(b − 1) then s_{b}(a) ∈ s_{b}(A_{t}), in contradiction to our standing hypotheses. But q ≤ \frac{1}{M} b^{m} ≤ b^{m−1}, so a − q ≥ (t + 1)b^{m} and a − q ∈ A_{t+1}, a contradiction. In conclusion A_{t+1} = ∅ and, since q < b^{m}, this implies A_{u} = ∅.

(iv). Note that t ≥ 1, we have s_{b}(t − 1) = s_{b}(t) − 1. Suppose that A_{t−1} is nonempty, so there exists a := max(A_{t−1}). Then s_{b}(a) = s_{b}(t) − 1 + s_{b}(a mod b^{m}) and, since |A_{t}| = M implies s_{b}(A_{t}) = {s_{b}(t), s_{b}(t) + 1, …, s_{b}(t) + m(b − 1)}, then it must be s_{b}(a mod b^{m}) = 0 that is a = (t − 1)b^{m}. But a + q ≤ tb^{m} − 1 so a + q ∈ A_{t−1}, a contradiction. Thus A_{t−1} = ∅ and, since q < b^{m}, it follows that A_{u} = ∅.

The sets {A_{t}}_{t=0}^{∞} form a partition of A, hence A = ⋃_{t∈ℕ} A_{t}. On the other hand, for the statements proved, we have that at most two of the sets {A_{t}}_{t=0}^{∞} are nonempty and their cardinality is less than or equal to M. In conclusion k = |A| ≤ 2M.

Corollary 2. L_{b,1} = 2b, μ_{2,1} = 14 and μ_{b,1} = b^{3} − b if b ≥ 3.

Proof. From Theorem 1 we know that L_{b,1} ≤ 2b. It is easy to verify that L_{2,1} = 4 and μ_{2,1} = 14 (OEIS \underline{A000120}). If b ≥ 3 then L_{b,1} = 2b and μ_{b,1} ≤ b^{3} − b because

s_{b}(b^{3} − b + i) = \begin{cases}2(b − 1) + i, & if i = 0, 1, …, b − 1; \\ i − b + 1, & if i = b, b + 1, …, 2b − 1. \end{cases}  (4)

Now let n < b^{3} − b be a nonnegative integer. Write n = d_{2}b^{2} + d_{1}b + d_{0} with d_{0}, d_{1}, d_{2} ∈ {0, 1, …, b − 1}. If d_{1} ≠ b − 1 then let m be the least integer greater than or equal to n and not divisible by b. We have m ≤ n + 1 and s_{b}(m) = s_{b}(m + b − 1). If d_{1} = b − 1 and d_{0} = 0 then d_{2} ≤ b − 2, since n < b^{3} − b, and so s_{b}(n) = s_{b}(n + 2b − 2). If d_{1} = b − 1 and d_{0} ≠ 0 then let h := (d_{2} + 1)b^{2}. We have h ≤ n + b − 1 and s_{b}(h + 1) = s_{b}(h + b). In any case we have found two integers u, v such that n ≤ u < v ≤ n + 2b − 1 and s_{b}(u) = s_{b}(v). Therefore μ_{b,1} ≥ b^{3} − b and actually μ_{b,1} = b^{3} − b.

Theorem 3. L_{b,bq} = L_{b,q} and μ_{b,bq} = bμ_{b,q}.

Proof. For all n, i ∈ ℕ and d ∈ {0, 1, …, b−1} we have s_{b}(bn+d+bqi) = s_{b}(n+qi)+d. Then for any k ∈ ℕ we have that s_{b}(bn + d), s_{b}(bn + d + bq), …, s_{b}(bn + d + (k − 1)bq) are distinct if and only if s_{b}(bn), s_{b}(bn + bq), …, s_{b}(bn + (k − 1)bq) are distinct, which in turn holds if and only if s_{b}(n), s_{b}(n + q), …, s_{b}(n + (k − 1)q) are distinct. In conclusion L_{b,bq} = L_{b,q} and μ_{b,bq} = bμ_{b,q}.

Theorem 4. μ_{b,q} > b^{\frac{L_{b,q}−b}{b−1}} − q(L_{b,q} − 1).

Proof. Let r := ⌊log_{b}(μ_{b,q} + q(L_{b,q} − 1))⌋ + 1. Since s_{b}(μ_{b,q}), s_{b}(μ_{b,q} + q), … s_{b}(μ_{b,q} + q(k − 1)) are distinct and less than or equal to r(b − 1), then

L_{b,q} ≤ r(b − 1) + 1 < (b − 1) log_{b}(μ_{b,q} + q(L_{b,q} − 1)) + b.  (5)

Solving (5) for μ_{b,q} we get μ_{b,q} > b^{\frac{L_{b,q}−b}{b−1}} − q(L_{b,q} − 1).

Theorem 5. μ_{b,q} ≤ b^{3}[q(L_{b,q} − 1)]^{2} − 1.

Proof. Take r := ⌊log_{b}(q(L_{b,q} − 1))⌋ + 1, μ := (μ_{b,q} mod b^{r}), m := ⌊μ_{b,q}/b^{r}⌋, so that μ_{b,q} = mb^{r} + μ, and let i ∈ {0, 1, …, L_{b,q} − 1}. If μ + qi < b^{r} then

s_{b}(μ_{b,q} + qi) = s_{b}(m) + s_{b}(μ + qi),  (6)

else if μ + qi ≥ b^{r} then

s_{b}(μ_{b,q} + qi) = s_{b}(m + 1) + s_{b}(μ + qi − b^{r}),  (7)

for the fact that μ + qi ≤ 2b^{r} − 2. Define n := (b^{r+1} − 1)b^{r} + μ, if μ + qi < b^{r} then

s_{b}(n + qi) = s_{b}(b^{r+1} − 1) + s_{b}(μ + qi) = (r + 1)(b − 1) + s_{b}(μ + qi) > r(b − 1). (8)

On the other hand, if μ + qi ≥ b^{r} then

s_{b}(n + qi) = s_{b}(b^{r+1}) + s_{b}(μ + qi − b^{r}) = 1 + s_{b}(μ + qi − b^{r}) ≤ r(b − 1),  (9)

because μ + qi − b^{r} ≤ b^{r} − 2 and so s_{b}(μ + qi − b^{r}) ≤ r(b − 1) − 1. In conclusion s_{b}(n), s_{b}(n + q), …, s_{b}(n + q(L_{b,q} − 1)) are distinct and

μ_{b,q} ≤ n ≤ b^{2r+1} − 1 ≤ b^{3}[q(L_{b,q} − 1)]^{2} − 1,  (10)

this completes our proof.

3 Arbitrarily large values of L_{b,q}

For the next theorem we need a lemma about the sum of digits of multiples of b^{r} −1, r ∈ ℕ^{+}. Similar results has been considered by Stolarsky [6, Lemma 2.2] in the case b = 2, and by Balog and Dartyge [1, Lemma 1] for a generic base b.

Lemma 6. If r ∈ ℕ^{+} then s_{b}((b^{r} − 1)i) = r(b − 1) for all i = 1, 2, …, b^{r} − 1.

Proof. Let t be the greatest nonnegative integer such that b^{t} | i. If i_{0} := b^{−t} i then there exist d_{0}, d_{1}, …, d_{r−1} ∈ {0, 1, …, b − 1} with d_{0} ≠ 0 such that i_{0} = ∑_{j=0}^{r−1} d_{j}b^{j} is the base-b representation of i_{0}. We have

(b^{r} − 1)i_{0} = ∑_{j=r}^{2r−1} d_{j−r}b^{j} − ∑_{j=0}^{r−1} d_{j}b^{j}

= ∑_{j=r+1}^{2r−1} d_{j−r}b^{j} + (d_{0} − 1)b^{r} + b^{r} − ∑_{j=0}^{r−1} d_{j}b^{j}

= ∑_{j=r+1}^{2r−1} d_{j−r}b^{j} + (d_{0} − 1)b^{r} + ∑_{j=1}^{r−1}(b − 1 − d_{j})b^{j} + (b − d_{0}).  (11)

Then it is straightforward that

s_{b}((b^{r} − 1)i_{0}) = ∑_{j=r+1}^{2r−1} d_{j−r} + (d_{0} − 1) + ∑_{j=1}^{r−1}(b − 1 − d_{j}) + (b − d_{0}) = r(b − 1).  (12)

The claim follows from s_{b}((b^{r} − 1)i) = s_{b}((b^{r} − 1)i_{0}).

Theorem 7. sup_{q∈ℕ^{+}} L_{b,q} = +∞.

Proof. Let n ∈ ℕ and q, k ∈ ℕ^{+} such that s_{b}(n), s_{b}(n + q), …, s_{b}(n + q(k − 1)) are distinct. If t, r are the least positive integers such that n + qk < b^{t} and (b − 1)b^{r−1} ≥ k then we define

n′ = ((b^{t} − 1)b^{2r} + b^{2r−1} + (b^{r} − 1)((b − 1)b^{r−1} − k + 1))b^{t} + n
q′ = (b^{r} − 1)b^{t} + q.  (13)

For any i = 0, 1, …, k we have

n′ + q′i = ((b^{t} − 1)b^{2r} + b^{2r−1} + (b^{r} − 1)((b − 1)b^{r−1} + i − k + 1))b^{t} + n + qi,  (14)

and then

s_{b}(n′ + q′i) = s_{b}((b^{t} − 1)b^{2r} + b^{2r−1} + (b^{r} − 1)((b − 1)b^{r−1} + i − k + 1)) + s_{b}(n + qi). (15)

If i ≤ k − 1 then (b^{r} − 1)((b − 1)b^{r−1} + i − k + 1) < (b − 1)b^{2r−1} and

s_{b}(n′ + q′i) = t(b − 1) + 1 + s_{b}((b^{r} − 1)((b − 1)b^{r−1} + i − k + 1)) + s_{b}(n + qi),  (16)

so Lemma 6 implies that

s_{b}(n′ + q′i) = (t + r)(b − 1) + 1 + s_{b}(n + qi) > (t + r)(b − 1).  (17)

On the other hand, if i = k then

s_{b}(n′ + q′k) = s_{b}(b^{2r+t} + b^{r−1} − 1) + s_{b}(n + qk) = 1 + (r − 1)(b − 1) + s_{b}(n + qk)
≤ 1 + (t + r − 1)(b − 1) ≤ (t + r)(b − 1).  (18)

Therefore s_{b}(n′), s_{b}(n′ + q), …, s_{b}(n′ + qk) are distinct, it follows that L_{b,q′} > L_{b,q} and hence sup_{q∈ℕ^{+}} L_{b,q} = +∞.

4 Further developments

Thanks to Theorem 1 we know that L_{b,q} is not too large when q is small compared to b, e.g., if q ≤ \frac{1}{2}b then L_{b,q} ≤ 2b^{2}. Actually, it is likely that for small q there exist explicit formulas for L_{b,q} and μ_{b,q} analogous to those of Corollary 2. However, when q is much larger than b the question becomes more difficult. Theorem 1 and 5 allowed us, with the aid of a personal computer, to calculate some values of μ_{b,q} and L_{b,q}.

\begin{matrix}μ_{b,q}, L_{b,q} & q = 1 & q = 2 & q = 3 & q = 4 & q = 5 & q = 6 & q = 7 & q = 8 & q = 9 \\ b = 2 & 14, 4 & 28, 4 & 58, 4 & 56, 4 & 242, 6 & 116, 4 & 109, 5 & 112, 4 & 994, 6 \\ b = 3 & 24, 6 & 24, 3 & 72, 6 & 234, 5 & 705, 9 & 72, 3 & 697, 10 & 18, 3 & 216, 6 \\ b = 4 & 60, 8 & 56, 8 & 60, 3 & 240, 8 & 1004, 8 & 244, 4 & 977, 13 & 224, 8 & 239, 4 \end{matrix}

Table 1: Values of μ_{b,q} and L_{b,q} for b = 2, 3, 4 and q = 1, 2, …, 9.

Through these series of numerical experiments we have reason to believe that the upper bound given by Theorem 1 is in some sense “astronomical” and surely can be improved. Similarly, also the upper and lower bounds for μ_{b,q} can be improved.

Many other questions remain unsolved. For instance, let κ_{b,q} be the function sending the nonnegative integer n to the maximum k ∈ ℕ such that s_{b}(n), s_{b}(n + q), …, s_{b}(n + q(k − 1)) are distinct. We proved that the function κ_{b,q} is bounded. Is κ_{b,q} definitely periodic? Does it present a fractal behavior? What is its Fourier expansion? What is its mean, variance, etc.? On the other side, for which n ∈ ℕ is κ_{b,q}(n) particularly small? These and other questions will be the subject of future investigations.

5 Acknowledgements

I am grateful to Salvatore Tringali (LJLL, Université Pierre et Marie Curie) for his careful proofreading and, more generally, his valuable support in the field of Mathematics. I am also thankful to the anonymous referee for his constructive comments.

References

[1] A. Balog and C. Dartyge, On the sum of the digits of multiples, Moscow J. Comb. Number Th. 2 (2012), 3–15.

[2] L. E. Bush, An asymptotic formula for the average sum of the digits of integers, Amer. Math. Monthly 47 (1940), 154–156.

[3] M. Drmota, C. Mauduit, and J. Rivat, The sum of digits function of polynomial sequences, J. Lond. Math. Soc. 84 (2011), 81–102.

[4] Y. Fang, A theorem on the k-adic representation of positive integers, Proc. Amer. Math. Soc. 130 (2002), 1619–1622.

[5] A. O. Gelfond, Sur les nombres qui ont des propriété additives et multiplicative données, Acta Arith. 13 (1967/1968), 259–265.

[6] K. B. Stolarsky, Integers whose multiples have anomalous digital frequencies, Acta Arith. 38 (1980), 117–128.

2010 Mathematics Subject Classification: Primary 11A63; Secondary 11A25, 11B25. Keywords: Elementary number theory, radix representation, sum of digits, arithmetic progressions.

(Concerned with sequence \underline{A000120}.)

Received August 5 2012; revised version received September 23 2012. Published in Journal of Integer Sequences, October 2 2012.

Return to Journal of Integer Sequences home page.