A090129 - OEIS

%I #44 May 01 2024 09:02:06

%S 1,2,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,

%T 131072,262144,524288,1048576,2097152,4194304,8388608,16777216,

%U 33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184

%N Smallest exponent such that -1 + 3^a(n) is divisible by 2^n.

%C A131577 and A011782 are companions, A131577(n) + A011782(n) = 2^n, (and differences each other). - _Paul Curtz_, Jan 18 2009

%C A090127 with offset 0: (1, 2, 2, 4, 8, ...) = A(x) / A(x^2), when A(x) = (1 + 2x + 4x^2 + 8x^3 + ...). - _Gary W. Adamson_, Feb 20 2010

%C From _Wolfdieter Lang_, Apr 18 2012: (Start)

%C a(n) is the order of 3 modulo 2^n. For n=1 and 2 this is obviously 1 and 2, respectively, and for n >= 3 it is 2^(n-2).

%C For a proof see, e.g., the Graeme McRae link under A068531, the section 'A Different Approach', proposed by Alexander Monnas, the first part, where the result from the expansion of (4-1)^(2^(k-2)) holds only for k >= 3. See also the Charles R Greathouse IV program below where this result has been used.

%C This means that the cycle generated by 3, taken modulo 2^n, has length a(n), and that 3 is not a primitive root modulo 2^n, if n >= 3 (because Euler's phi(2^n) = 2^(n-1), n >= 1, see A000010).

%C (End)

%C Let r(x) = (1 + 2x + 2x^2 + 4x^3 + ...). Then (1 + 2x + 4x^2 + 8x^3 + ...) = (r(x) * r(x^2) * r(x)^4 * r(x^8) * ...). - _Gary W. Adamson_, Sep 13 2016

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

%F a(n) = 2^(n-2) if n >= 3, 1 for n=1 and 2 for n=2 (see the order comment above).

%F a(n+2) = A152046(n) + A152046(n+1) = 2*A011782(n). - _Paul Curtz_, Jan 18 2009

%e a(1) = 1 since -1 + 3 = 2 is divisible by 2^1;

%e a(2) = a(3) = 2 since -1 + 9 = 8 is divisible by 4 = 2^2 and also by 8 = 2^3;

%e a(5) = 8 since -1 + 6561 = 6560 = 32*205 is divisible by 2^5.

%e From _Wolfdieter Lang_, Apr 18 2012: (Start)

%e n=3: the order of 3 (mod 8) is a(3)=2 because the cycle generated by 3 is [3, 3^2==1 (mod 8)].

%e n=5: a(5) = 2^3 = 8 because the cycle generated by 3 is [3^1=3, 3^2=9, 3^3=27, 17, 19, 25, 11, 1] (mod 32).

%e   The multiplicative group mod 32 is non-cyclic (see A033949(10)) with the additional four cycles  [5, 25, 29, 17, 21, 9, 13, 1], [7, 17, 23, 1], [15, 1], and [31, 1]. This is the cycle structure of the (Abelian) group Z_8 x Z_2 (see one of the cycle graphs shown in the Wikipedia link 'List of small groups' for the order phi(32)=16, given under A192005).

%e (End)

%t t=Table[Part[Flatten[FactorInteger[ -1+3^(n)]], 2], {n, 1, 130}] Table[Min[Flatten[Position[t, j]]], {j, 1, 10}]

%t Join[{1,2},2^Range[30]] (* or *) Join[{1,2},NestList[2#&,2,30]] (* _Harvey P. Dale_, Nov 08 2012 *)

%o (PARI) a(n)=2^(n+(n<3)-2) \\ _Charles R Greathouse IV_, Apr 09 2012

%o (Python)

%o def A090129(n): return n if n<3 else 1<<n-2 # _Chai Wah Wu_, Jul 11 2022

%Y Cf. A068531, A069895, A088660, A090739, A090740, A091512.

%K nonn,easy

%O 1,2

%A _Labos Elemer_ and _Ralf Stephan_, Jan 19 2004

%E a(11) through a(20) from _R. J. Mathar_, Aug 08 2008

%E More terms (powers of 2, see a comment above) from _Wolfdieter Lang_, Apr 18 2012