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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

Cf. A007583 (comment Feb 15 2014).

Sequence in context: A083562 A106542 A229934 * A325892 A127014 A073748

Adjacent sequences:  A239122 A239123 A239124 * A239126 A239127 A239128

KEYWORD

nonn,easy

AUTHOR

Wolfdieter Lang, Mar 13 2014

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 October 18 20:13 EDT 2019. Contains 328197 sequences. (Running on oeis4.)