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

Author

Zhining Yang, Apr 29 2022

Keywords

• nonn
• base
• easy

Examples

			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}.
		

Links

• Zhining Yang, Table of n, a(n) for n = 1..300
• Project Euler, Problem 788. Dominating Numbers

Crossrefs

Cf. A353181, A353182 (first differences).

Programs

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 *)

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)])

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).