|
%I #33 Nov 05 2023 02:28:08
%S 4,45,369,2961,23697,189585,1516689,12133521,97068177,776545425,
%T 6212363409,49698907281,397591258257,3180730066065,25445840528529,
%U 203566724228241,1628533793825937,13028270350607505,104226162804860049,833809302438880401,6670474419511043217,53363795356088345745
%N Number of distinct pairs a < b with nonzero decimal digits such that a + b = 10^n.
%C From _Chai Wah Wu_, Sep 21 2016: (Start)
%C Proof that a(n) = 9*a(n-1) - 8*a(n-2) for n > 3: Here x and y denote numbers with no zero decimal digits. Decompose a(n) as a(n) = b(n) + c(n) where b(n) is the numbers of pairs x > y such that x and y have the same number of digits and x + y = 10^n. Note that if n > 1 and x + y = 10^n, then x <> y. If x > y are pairs of numbers of n digits that add to 10^n, then prepending x with the digit 8 and y with the digit 1 creates a pair of numbers of n+1 digits that add to 10^n. Similarly if we prepend x with 1 and y with 8.
%C We can also prepend the pairs of digits (7,2), (6,3) and (5,4) to x and y and to y and x. All pairs that contribute to b(n+1) can be constructed this way. This means that b(n+1) = 8*b(n) for n > 1.
%C Similarly prepending the digit 9 to x or y will result in a pair of numbers with n + 1 and n digits respectively that add to 10^(n+1). If x > y and x has n digits and y has < n digits with x + y = 10^n, then prepending the digit 9 to x results in a pair of numbers with n+1 and < n digits respectively that add to 10^(n+1). All pairs of numbers that contribute to the count c(n+1) can be constructed this way. This means that c(n+1) = 2*b(n) + c(n) for n > 1. Thus a(n+1) = b(n+1) + c(n+1) = 9*b(n) + b(n) + c(n) = 9*(a(n) - c(n)) + 8*b(n-1) + 2*b(n-1) + c(n-1) = 9*a(n) - 9*(2*b(n-1)+c(n-1)) + 10*b(n-1) + c(n-1) = 9*a(n) - 8*b(n-1) - 8*c(n-1) = 9*a(n) - 8*a(n-1).
%C The reason the recurrence relation a(n) = 9*a(n-1) - 8*a(n-2) fails for n = 3 is because for n = 1 there are two numbers, 5 and 5, which sums to 10, but they are equal to each other. This pair does not contribute to b(1), but they can be used to construct pairs in the counts b(2) and c(2).
%C In particular, for b(2) we have the pairs (85, 15), (75, 25), (65, 35), (55, 45) and for c(2) we have the pair (95,5). Thus these extra pairs results in b(2) = 8*b(1) + 4 and c(2) = 2*b(1) + c(1) + 1.
%C (End)
%H Chai Wah Wu, <a href="/A117644/b117644.txt">Table of n, a(n) for n = 1..500</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (9,-8).
%F From _Chai Wah Wu_, Sep 19 2016: (Start)
%F a(n) = 9*a(n-1) - 8*a(n-2) for n > 3.
%F G.f.: x*(-4*x^2 + 9*x + 4)/((x - 1)*(8*x - 1)). (End)
%F a(n) = 9*(9*8^n-16)/112 for n>1. - _Colin Barker_, Sep 22 2016
%F E.g.f.: (63 - 144*exp(x) + 81*exp(8*x) - 56*x)/112. - _Stefano Spezia_, Nov 16 2022
%e 10 = 1 + 9 = 2 + 8 = 3 + 7 = 4 + 6 making 4 different pairs, thus a(1) = 4.
%p P:=proc(n)local i,j,k,ok,count; count:=0; for i from 1 by 1 to n/2-1 do ok:=0; k:=i; while k>0 do j:=frac(k/10)*10; if j=0 then ok:=1; fi; k:=trunc(k/10); od; k:=n-i; while k>0 do j:=frac(k/10)*10; if j=0 then ok:=1; fi; k:=trunc(k/10); od; if ok=1 then count:=count+1; fi; od; print(n/2-1-count); end: P(1000);
%t Table[Function[n, Length@ DeleteCases[Transpose@ {#, n - #}, w_ /; Or[MatchQ @@ w, Total@ Boole@ Map[DigitCount[#, 10, 0] > 0 &, w] > 0]] &@ Range@ Floor[n/2]][10^n], {n, 6}] (* _Michael De Vlieger_, Sep 19 2016 *)
%t LinearRecurrence[{9,-8},{4,45,369},30] (* _Harvey P. Dale_, Nov 05 2023 *)
%o (PARI) nonzerodigits(n)=while(n,if(n%10,n\=10,return(0)));1
%o a(N)=N=10^N;sum(n=1,N/2-1,nonzerodigits(n)&nonzerodigits(N-n))
%o (PARI) Vec(x*(-4*x^2 + 9*x + 4)/((x - 1)*(8*x - 1)) + O(x^30)) \\ _Colin Barker_, Sep 22 2016
%K nonn,base,easy
%O 1,1
%A _Paolo P. Lava_ and _Giorgio Balzarotti_, Apr 10 2006
%E Extension, new description and program from _Charles R Greathouse IV_, Aug 05 2010
%E a(9)-a(13) from _Donovan Johnson_, Aug 27 2010
%E More terms from _Chai Wah Wu_, Sep 22 2016
| 