login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

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