OFFSET
0,3
COMMENTS
a(n) is the smallest positive integer solution of the linear Diophantine equation 27*a(n) - 2^n*b(n) = 1 , n>= 0, with b(n) the period length 18 = phi(27) sequence repeat(26, 13, 20, 10, 5, 16, 8, 4, 2, 1, 14, 7, 17, 22, 11, 19, 23, 25). Here phi(n) = A000010(n) (Euler's totient). These 18 members are a permutation of the smallest nonnegative numbers of the reduced residue system modulo 27.
This is the instance m = 3 of an m-family of sequence pairs [x0(m, n), y0(m, n)], n>= 0, providing a special solution of the linear Diophantine equation 3^m*x - 2^n*y = 1; in fact the one with smallest positive x. The general formula is y0(m, n) = ((3^m+1)/2)^(n+3^(m-1)) (mod 3^m) and x0(m, n) = (1 + 2^n*y0(m, n))/3^m. For m = 0 this is x0(0, n) = 1 + 2^n with y0(0, n) = 1, n >= 0. Obviously, y0(m, n) is a positive integer (y0 = 0 is out). The proof that x0(m, n) is also a positive integer is done by showing that 1 + 2*y0(m, n) == 0 (mod 3^m). Because (3^m+1)/2 == 1/2 (mod 3^m) one shows that ((3^m+1)/2)^(3^(m-1)) + 1 == 0 (mod 3^m). This can be done writing (3^m+1)/2 = 3*q - 1, with q = (3^(m-1) + 1)/2, a natural number for m >= 1. Then the binomial theorem is used. Finally one has to show that binomial(3^(m-1) - 1, n -1)/n is a (positive) integer. Here the triangle A107711 helps (for a nice proof that A107711 is a positive integer triangle see the history with the remark by Peter Bala from Fri Feb 28, after #13).
The general family of positive solutions of 3^m*x - 2^n*y = c (c an integer) is then x(m, n; k) = x0(m, n) + 2^n*tmin(m, n) + 2^n*k and y(m, n; k) = y0(m, n) + 3^m*tmin(m, n) + 3^m*k for k>=0, with tmin(m, n) = ceiling(-c*y0(m, n)/3^m) if c>=0 and tmin(m, n) = ceiling(|c|*x0(m, n)/2^n) if c < 0.
See the Niven-Zuckerman-Montgomery reference, pp. 212-214, for integer solutions of a*x + b*y = c provided gcd(a,b)|c. Note that in their treatment of positive solutions a and b are assumed to be positive, but here we use b < 0.
For this instance m=3 one can prove directly that the a(n) formula given below in terms of b(n) produces (positive) integers. One uses 1/2 (mod 27) = 14 and 14^9 + 1 == 0 (mod 27).
REFERENCES
I. Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory Of Numbers, Fifth Edition, John Wiley and Sons, Inc., NY 1991.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Wolfdieter Lang, On Collatz' Words, Sequences and Trees, arXiv:1404.2710 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.11.7.
Index entries for linear recurrences with constant coefficients, signature (3,-2,0,0,0,0,0,0,-512,1536,-1024).
FORMULA
a(n) = (1 + 2^n*b(n))/27 with b(n) = 14^(n+9) (mod 27), n >= 0. The sequence b(n) has period length 18, and it is given in a comment above.
a(n) = 3*a(n-1) -2*a(n-2) -512*a(n-9) +1536*a(n-10) -1024*a(n-11) for n>10, with initial values as shown. [Bruno Berselli, Mar 15 2014]
G.f.: -(512*x^10-512*x^9+32*x^6-16*x^5+4*x^3-2*x^2+2*x-1) / ((x-1)*(2*x-1)*(2*x+1)*(4*x^2-2*x+1)*(64*x^6-8*x^3+1)). - Colin Barker, Mar 20 2014
EXAMPLE
a(0) = 1 because 27*1 - 1*b(0) = 27 - 26 = 1.
a(1) = 1 because 27*1 - 2*b(1) = 27 - 2*13 = 1.
a(5) = 19, because 27*19 - 32*b(5) = 27*19 - 32*16 = 1.
MATHEMATICA
LinearRecurrence[{3, -2, 0, 0, 0, 0, 0, 0, -512, 1536, -1024}, {1, 1, 3, 3, 3, 19, 19, 19, 19, 19, 531}, 40] (* Bruno Berselli, Mar 15 2014 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Wolfdieter Lang, Mar 13 2014
STATUS
approved