A353183 Number of numbers < 10^n in which more than half of the digits are the same.

9, 18, 270, 603, 8307, 19737, 265257, 653742, 8672022, 21893256, 288028728, 739651770, 9675345546, 25164110070, 327788101782, 860977172187, 11178969569667, 29595164756157, 383284574197677, 1021259144052675, 13198843891723059, 35357274978994503, 456176418630573735, 1227566989710948393

Offset

1,1

Links

Zhining Yang, Table of n, a(n) for n = 1..300

Project Euler, Problem 788. Dominating Numbers

Formula

a(n) = Sum_{m=1..n} Sum_{k=floor(m/2)+1..m} C(m,k)*9^(m-k+1).

a(n+4) = ((16560 + 14040*n + 2880*n^2)*a(n) - (18036 + 15444*n + 3168*n^2)*a(n+1) + (858 + 934*n + 208*n^2)*a(n+2) + (678 + 517*n + 88*n^2)*a(n+3))/(60 + 47*n + 8*n^2).

a(n+5) = -((1440 + 720*n)*a(n) + (-3024 - 1152*n)*a(n+1) + (1668 + 448*n)*a(n+2) + (-28 - 4*n)*a(n+3) + (-61 - 13*n)*a(n+4))/(5+n).

Example

a(2) = 18 because there are 18 numbers less than 10^2 in which more than half of the digits are the same: {1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99}.

Mathematica

a[n_]:=Sum[Sum[Binomial[m, k]9^(m-k+1), {k, Floor[m/2]+1, m}], {m, 1, n}]; Array[a, 24] (* Stefano Spezia, Apr 29 2022 *)

Prog

(Python)
import math
def a(n):
    return(sum(sum(math.comb(m, i)*9**(m-i+1) for i in range(m//2+1, m+1)) for m in range(1, n+1)))
print([a(i) for i in range(1, 21)])
(Python)
def a(n):
    r=[0, 9, 18, 270, 603]
    for i in range(n):
        r.append(-((1440+720*i)*r[i]+(-3024-1152*i)*r[1+i]+(1668+448*i)*r[2+i]+(-28-4*i)*r[3+i]+(-61-13*i)*r[4+i])//(5+i))
    return r[n]
print([a(i) for i in range(1, 21)])

Crossrefs

Cf. A353181, A353182 (first differences).

Sequence in context: A050685 A278588 A133361 * A005400 A134115 A071587

Adjacent sequences: A353180 A353181 A353182 * A353184 A353185 A353186

Keyword

nonn,base,easy

Author

Zhining Yang, Apr 29 2022

Status

approved