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

%I #58 Jun 25 2022 22:13:42

%S 9,18,270,603,8307,19737,265257,653742,8672022,21893256,288028728,

%T 739651770,9675345546,25164110070,327788101782,860977172187,

%U 11178969569667,29595164756157,383284574197677,1021259144052675,13198843891723059,35357274978994503,456176418630573735,1227566989710948393

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

%H Zhining Yang, <a href="/A353183/b353183.txt">Table of n, a(n) for n = 1..300</a>

%H Project Euler, <a href="https://projecteuler.net/problem=788">Problem 788. Dominating Numbers</a>

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

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

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

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

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

%o (Python)

%o import math

%o def a(n):

%o 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)))

%o print([a(i) for i in range(1, 21)])

%o (Python)

%o def a(n):

%o r=[0, 9, 18, 270, 603]

%o for i in range(n):

%o 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))

%o return r[n]

%o print([a(i) for i in range(1, 21)])

%Y Cf. A353181, A353182 (first differences).

%K nonn,base,easy

%O 1,1

%A _Zhining Yang_, Apr 29 2022