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