User talk:M. F. Hasler/Digits d in 0 through 123...n

This is a short writeup concerning sequences A277830 - A277838 and A277849, motivated by A277635 (special case for d=7), in turn motivated by "How many sevens?" on Puzzling Stack Exchange.

Some comments and definitions

Introduction and study of these sequence were motivated by A277635, which is the special case for d = 7, at least for 1 <= n <= 9. The idea is to count the number of occurrences of a given digit, here '7', within the set of numbers in the range from 1 (or 0) to the upper limit L(n) = 123...n = A007908(n) in the original A277635.

There are several variants and considerations.

1. First and most obviously, the problem could and should be studied for any digit 'd' instead of '7'.
2. One could consider the problem in bases other than b = 10. One benefit from this would illustration and possible empirical verifications for counts of large (multi-digit) n, which is impracticable for b = 10, where n = 10 is close to the upper limit of what can be done in reasonable time with the most naïve brute-force approach, i.e., considering each of the numbers from 0 to L(n), splitting it up in digits, and counting the digits equal to d.
3. One may choose 0 or 1 as lower limit of the range of numbers to consider. This obviously makes a difference only for d = 0. It turns out that 0 is (arguable) the more natural choice.
4. For the upper limit, L(n) = 1...n becomes ambiguous for n > 9 (or in general, for n >= b, the base).
   1. The most "literal" choice seems to append n, regardless of its number of digits. (This corresponds to A007908, in base 10.) However, this implies that from n = b (= 10) on (and then from n = b^2 = 100 on, etc), the range suddenly grows by one more order of magnitude than before. It can be expected that this destroys a simple regularity that might be observed up to n = b-1.
   2. An alternate choice would be to extend L(n) through the formula L(n) = sum_{i=1..n} i*b^(n-i) (satisfying the recurrence L(n) = L(n-1)*b + n, cf. A014824). This sequence has, in some sense, "better mathematical properties" than the previous one. Among which, a simpler explicit formula and recurrence relation, and more regular growth, namely, ~ 10^n. However, since rightmost digits become "scrambled", in some sense, from n = 10 on, previously observed regularities might also break up sooner (for small digits 0 and 1) or later (for larger digits).

More details and definitions

Following conventions adopted above and during submission of the sequences A277830, ..., A277838 and A277849 to OEIS,

let us denote by a[d](n) the count of digits 'd' within { 0, ..., L(n) = A014824(n) }.

In the following table we will also use Ad(n) for this, in order to simplify typesetting. [Should be replaced by use of indices.]

We get the following counts a[d](n), and relations:

 \ n =
d \0 1  2   3   4     5     6       7       8    ... 	   relation to a[d ± 1](n)                            and on diagonal n=d & above/below diagonal 
0: 1,1, 2, 23, 344, 4665, 58986, 713307, 8367628,... = A1(n) [+ 2*10^(n-1), n≥1] = A9(n) + 1 (n < 9) = A083449(n) = A272525(n-2) (n>1), a(0) = A1(0) + 1,
1: 0,1, 5, 57, 689, 8121, 93553,1058985,   ...       = A2(n) [+ 3*10^(n-2), n≥2] = A0(n) [- 2*10^(n-1), n≥1], a(0) = A0(0) - 1, a(1) = A0(1) = A2(1) + 1,
2: 0,0, 2, 27, 389, 5121, 63553, 758985,   ...       = A3(n) [+ 4*10^(n-3), n≥3] = A1(n) [- 3*10^(n-2), n≥2], a(1) = A1(1) - 1, a(2) = A0(2) = A3(2) + 1,
3: 0,0, 1, 23, 349, 4721, 60453, 718985,   ...       = A4(n) [+ 5*10^(n-4), n≥4] = A2(n) [- 4*10^(n-3), n≥3], a(2) = A2(2) - 1, a(3) = A0(3) = A4(3) + 1,
4: 0,0, 1, 22, 344, 4671, 59053, 713985,   ...       = A5(n) [+ 6*10^(n-5), n≥5] = A3(n) [- 5*10^(n-4), n≥4], a(3) = A3(3) - 1, a(4) = A0(4) = A5(4) + 1,
5: 0,0, 1, 22, 343, 4665, 58993, 713385, 8368417,... = A6(n) [+ 7*10^(n-6), n≥6] = A4(n) [- 6*10^(n-5), n≥5], a(4) = A4(4) - 1, a(5) = A0(5) = A6(5) + 1,	 
6: 0,0, 1, 22, 343, 4664, 58986, 713315, 8367717,... = A7(n) [+ 8*10^(n-7), n≥7] = A5(n) [- 7*10^(n-6), n≥6], a(5) = A5(5) - 1, a(6) = A0(6) = A7(6) + 1,	 
7: 0,0, 1, 22, 343, 4664, 58985, 713307, 8367637,... = A8(n) [+ 9*10^(n-8), n≥8] = A6(n) [- 8*10^(n-7), n≥7], a(6) = A6(6) - 1, a(7) = A0(7) = A8(7) + 1,
8: 0,0, 1, 22, 343, 4664, 58985, 713306, 8367628,... = A9(n)        (n < 8)      = A7(n) [- 9*10^(n-8), n≥8], a(7) = A7(7) - 1, a(8) = A0(8) = A9(8) + 1,
9: 0,0, 1, 22, 343, 4664, 58985, 713306, 8367627,... = A0(n) - 1    (n < 9)      = A8(n)        (n < 8),      a(8) = A8(8) - 1, a(9) = A0(9).

We observe the general relations:

a[0](n) = a[n](n) = a[d](n) + 1 for all 9 >= d > n >= 0,

and (*)

a[d-1](n) = a[d](n) + (d+1)*10^(n-d) for all 9 >= n >= d > 1.

which allow tho compute any intermediate elements from those of the first line.

(*) Illustration: Observe that, looking at the underlined diagonal terms, the term below is smaller by 1, and the difference with terms above grows column-/line-wise by 1 resp. by a factor 10: e.g., 23 -> 27 (+ 4) -> 57 (+ 30), 344 -> 349 (+ 5) -> 389 (+ 40) -> 689 (+ 300), 4665 -> 4671 (+ 6), ...

Work to do

• Extend the results to other bases
• Extend the results to n > 9.
• Check where the above relations break.

Generalizations

There is no direct sense in defining a[d](n) for d >= b, but maybe some regularity that can be observed for d < b (recurrence relation, ...) allows to find one (or more) 'natural' ways to extend the definition of a[d](n) to d >= b.

Authorship

Revision history

Writeup of initial version. — MFH 16:47, 2 November 2016 (UTC)