A239125 Smallest positive integer solution x of (3^3)*x - 2^n*y = 1 for n >= 0.

1, 1, 3, 3, 3, 19, 19, 19, 19, 19, 531, 531, 2579, 6675, 6675, 23059, 55827, 121363, 252435, 252435, 776723, 776723, 776723, 4971027, 4971027, 4971027, 4971027, 4971027, 139188755, 139188755, 676059667, 1749801491, 1749801491, 6044768787, 14634703379

Offset: 0

Author

Wolfdieter Lang, Mar 13 2014

Keywords

• nonn
• easy
• changed

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).

Examples

			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.
		

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).

Crossrefs

Cf. A007583 (comment Feb 15 2014).

Programs

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 *)

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