

A239125


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


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 mfamily 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^(m1)) (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^(m1)) + 1 == 0 (mod 3^m). This can be done writing (3^m+1)/2 = 3*q  1, with q = (3^(m1) + 1)/2, a natural number for m >= 1. Then the binomial theorem is used. Finally one has to show that binomial(3^(m1)  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 NivenZuckermanMontgomery reference, pp. 212214, 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(n1) 2*a(n2) 512*a(n9) +1536*a(n10) 1024*a(n11) for n>10, with initial values as shown. [Bruno Berselli, Mar 15 2014]
G.f.: (512*x^10512*x^9+32*x^616*x^5+4*x^32*x^2+2*x1) / ((x1)*(2*x1)*(2*x+1)*(4*x^22*x+1)*(64*x^68*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

Cf. A007583 (comment Feb 15 2014).
Sequence in context: A106542 A342363 A229934 * A341752 A325892 A127014
Adjacent sequences: A239122 A239123 A239124 * A239126 A239127 A239128


KEYWORD

nonn,easy


AUTHOR

Wolfdieter Lang, Mar 13 2014


STATUS

approved



