|
%I #30 Mar 06 2018 14:40:34
%S 1,1,3,3,3,19,19,19,19,19,531,531,2579,6675,6675,23059,55827,121363,
%T 252435,252435,776723,776723,776723,4971027,4971027,4971027,4971027,
%U 4971027,139188755,139188755,676059667,1749801491,1749801491,6044768787,14634703379
%N Smallest positive integer solution x of (3^3)*x - 2^n*y = 1 for n >= 0.
%C 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.
%C 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).
%C 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.
%C 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.
%C 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).
%D 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.
%H Vincenzo Librandi, <a href="/A239125/b239125.txt">Table of n, a(n) for n = 0..1000</a>
%H Wolfdieter Lang, <a href="http://arxiv.org/abs/1404.2710">On Collatz' Words, Sequences and Trees</a>, arXiv:1404.2710 [math.NT], 2014 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Lang/lang6.html">J. Int. Seq. 17 (2014) # 14.11.7</a>.
%H <a href="/index/Rec#order_11">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,0,0,0,0,0,0,-512,1536,-1024).
%F 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.
%F 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]
%F 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
%e a(0) = 1 because 27*1 - 1*b(0) = 27 - 26 = 1.
%e a(1) = 1 because 27*1 - 2*b(1) = 27 - 2*13 = 1.
%e a(5) = 19, because 27*19 - 32*b(5) = 27*19 - 32*16 = 1.
%t 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 *)
%Y Cf. A007583 (comment Feb 15 2014).
%K nonn,easy
%O 0,3
%A _Wolfdieter Lang_, Mar 13 2014
|
