A268839 a(n) = Sum_{j=1..10^n-1} 2^f(j) where f(j) is the number of zero digits in the decimal representation of j.

9, 108, 1197, 13176, 144945, 1594404, 17538453, 192922992, 2122152921, 23343682140, 256780503549, 2824585539048, 31070440929537, 341774850224916, 3759523352474085, 41354756877214944, 454902325649364393, 5003925582143008332, 55043181403573091661

Offset: 1

Author

Michel Lagneau, Feb 14 2016

Keywords

• nonn
• base
• easy

Comments

We calculate the number of integers between 1 and 10^n - 1 having k zeros in their decimal representation. To form a such number consisting of m digits (k < m), place k zeros in m-1 possible positions, then we must choose m-k digits different from zero. Thus, the number of integers between 1 and 10^n - 1 having k zeros in their decimal representation is: Sum_{m=k+1..n} binomial(m-1, k)*9^(m-k).

Hence the sum: Sum_{m=1..n} Sum_{k=0..m-1} binomial(m-1,k)*9^(m-k)*2^k = Sum_{m=1..n} 9^m*(11/9)*(m-1) = (9/10)*(11^n - 1).

Examples

			a(1) = 9 because 2^f(1) + 2^f(2) + ... + 2^f(9) = 2^0 + 2^0 + ... + 2^0 = 9;
a(2) = 108 because 2^f(1) + 2^f(2) + ... + 2^f(99) = 9*10 + 2*9 = 108, where f(10) = f(20) = ... = f(90) = 1 and f(i) = 0 otherwise.
		

Links

• Colin Barker, Table of n, a(n) for n = 1..950
• Index entries for linear recurrences with constant coefficients, signature (12,-11).

Crossrefs

Cf. A016123, A033713, A033714, A055641, A119291.

Programs

Magma

[(9/10)*(11^n-1): n in [1..20]]; // Vincenzo Librandi, Feb 15 2016

Maple

for n from 1 to 100 do: x:=(9/10)*(11^n-1):printf(‘%d, ‘,x):od:

Mathematica

Table[Table[(9/10) (11^n - 1), {n, 1, 20}]] (* Bruno Berselli, Feb 15 2016 *)
CoefficientList[Series[9/((1 - 11 x) (1 - x)), {x, 0, 33}], x] (* Vincenzo Librandi, Feb 15 2016 *)

PARI

Vec(9*x/((1-11*x)*(1-x)) + O(x^30)) \\ Colin Barker, Feb 22 2016

Formula

a(n) = (9/10)*(11^n-1) = 9*A016123(n-1).

From Vincenzo Librandi, Feb 15 2016: (Start)

G.f.: (9*x)/((1-11*x)*(1-x)).

a(n) = 11*a(n-1) + 9. (End)

E.g.f.: 9*exp(x)*(exp(10*x) - 1)/10. - Stefano Spezia, Sep 13 2023

Extensions

Name edited by Jon E. Schoenfield, Sep 13 2017