|
| |
|
|
A117644
|
|
Number of distinct pairs a < b with nonzero decimal digits such that a + b = 10^n.
|
|
2
|
|
|
|
4, 45, 369, 2961, 23697, 189585, 1516689, 12133521, 97068177, 776545425, 6212363409, 49698907281, 397591258257, 3180730066065, 25445840528529, 203566724228241, 1628533793825937, 13028270350607505, 104226162804860049, 833809302438880401, 6670474419511043217, 53363795356088345745
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
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.
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.
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).
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).
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.
(End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 9*a(n-1) - 8*a(n-2) for n > 3.
G.f.: x*(-4*x^2 + 9*x + 4)/((x - 1)*(8*x - 1)). (End)
a(n) = 9*(9*8^n-16)/112 for n>1. - Colin Barker, Sep 22 2016
E.g.f.: (63 - 144*exp(x) + 81*exp(8*x) - 56*x)/112. - Stefano Spezia, Nov 16 2022
|
|
|
EXAMPLE
|
10 = 1 + 9 = 2 + 8 = 3 + 7 = 4 + 6 making 4 different pairs, thus a(1) = 4.
|
|
|
MAPLE
|
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);
|
|
|
MATHEMATICA
|
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 *)
LinearRecurrence[{9, -8}, {4, 45, 369}, 30] (* Harvey P. Dale, Nov 05 2023 *)
|
|
|
PROG
|
(PARI) nonzerodigits(n)=while(n, if(n%10, n\=10, return(0))); 1
a(N)=N=10^N; sum(n=1, N/2-1, nonzerodigits(n)&nonzerodigits(N-n))
(PARI) Vec(x*(-4*x^2 + 9*x + 4)/((x - 1)*(8*x - 1)) + O(x^30)) \\ Colin Barker, Sep 22 2016
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,base,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
