A094798 - OEIS

A094798

Number of times 1 is used in writing out all the numbers 1 through n.

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,10

COMMENTS

The number of 1's required to write all integers of n or fewer digits (i.e., the sequence a(9), a(99), a(999), ...) is 1, 20, 300, 4000, ..., which is A053541. - Jason D. W. Taff (jtaff(AT)jburroughs.org), Dec 05 2004

A014778 gives the fixed points. - David Wasserman, Feb 22 2005

Partial sums of A268643. - Robert Israel, Oct 28 2016

LINKS

Harvey P. Dale, Table of n, a(n) for n = 1..1000

FORMULA

G.f. g(x) satisfies g(x) = x/((1-x)*(1-x^10)) + ((1-x^10)/(1-x))^2*g(x^10). - Robert Israel, Oct 28 2016 [corrected by Fabio Visonà, Aug 10 2022]

MAPLE

nones:=proc(n) local nn, c, j: nn:=convert(n, base, 10): c:=0: for j to nops(nn) do if nn[j]=1 then c:=c+1 else end if end do: c end proc: a:=proc(n) options operator, arrow: add(nones(k), k=1..n) end proc: seq(a(n), n=1..75); # Emeric Deutsch, Mar 01 2008

ListTools:-PartialSums([seq(numboccur(1, convert(n, base, 10)), n=1..100)]); # Robert Israel, Oct 28 2016

MATHEMATICA

Accumulate[Table[DigitCount[n, 10, 1], {n, 80}]] (* Harvey P. Dale, Sep 27 2013 *)

PROG

(Python)

from itertools import accumulate, count, islice

def f(_, n): return _ + str(n).count("1")

def agen(): yield from accumulate(count(1), f)

print(list(islice(agen(), 75))) # Michael S. Branicky, Aug 09 2022

(PARI) a(n) = sum(k=1, n, #select(x->(x==1), digits(k))); \\ Michel Marcus, Oct 03 2023

CROSSREFS

Cf. A014778, A053541, A268643.