This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 From Chai Wah Wu, Sep 21 2016: (Start) 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 Chai Wah Wu, Table of n, a(n) for n = 1..500 FORMULA From Chai Wah Wu, Sep 19 2016: (Start) 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 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 *) 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 Sequence in context: A273848 A123650 A122910 * A232729 A055602 A073565 Adjacent sequences:  A117641 A117642 A117643 * A117645 A117646 A117647 KEYWORD nonn,base,easy AUTHOR Paolo P. Lava and Giorgio Balzarotti, Apr 10 2006 EXTENSIONS Extension, new description and program from Charles R Greathouse IV, Aug 05 2010 a(9)-a(13) from Donovan Johnson, Aug 27 2010 More terms from Chai Wah Wu, Sep 22 2016 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 20 14:54 EST 2019. Contains 329337 sequences. (Running on oeis4.)