A274024 a(n) is the number of distinct residues generated by the recurrence b(k+1,n) = 2^b(k,n) (mod n), k = 1,2,...,n. The initial value is b(1,n) = 1.

2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 3, 9, 3, 3, 4, 4, 4, 10, 4, 4, 6, 8, 4, 12, 4, 6, 4, 10, 4, 4, 5, 5, 5, 4, 4, 26, 9, 4, 4, 8, 4, 4, 6, 4, 6, 6, 4, 5, 5, 4, 4, 42, 5, 14, 4, 7, 8, 21, 4, 32, 4, 4, 5, 4, 5, 52, 5, 18, 4, 7, 4, 5, 7, 5, 8, 11, 4, 10, 4, 18, 7, 73

Offset

1,1

Comments

If n > 1 is odd, a(n) <= A002326((n-1)/2). - Robert Israel, Jun 07 2016

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Example

a(13) = 9 because:
b(1,13) = 1; b(2,13) = 2^1 (mod 13) = 2; b(3,13) = 2^2 (mod 13) = 4; b(4,13) = 2^4 (mod 13) = 3; b(5,13) = 2^3 (mod 13) = 8; b(6,13) = 2^8 (mod 13) = 9; b(7,13) = 2^9 (mod 13) = 5; b(8,13) = 2^5 (mod 13) = 6; b(9,13) = 2^6 (mod 13) = 12; b(10,13) = 2^12 (mod 13) = 1.
So the set {b(k,13)} = {1, 2, 4, 3, 8, 9, 5, 6, 12, 1, 2, 4,...} becomes periodic and contains 9 distinct residues (mod 13).

Maple

for n from 1 to 100 do:
lst:={1}:x0:=1:
   for m from 1 to n do:
     q:=2^x0 mod(n):lst:=lst union {q}:
     x0:=q:
   od:
    n0:=nops(lst):printf(`%d, `, n0):
od:
% alternative:
f:= proc(n) local S, b;
  b:= 1; S:= {1}:
  do
    b:= 2 &^ b mod n;
    if member(b, S) then return nops(S) fi;
    S:= S union {b};
  od
end proc:
f(1):= 2: f(2):= 2:
map(f, [$1..1000]); # Robert Israel, Jun 07 2016

Prog

(PARI) a(n) = {m = 1; sr = [1]; ok = 1; while (ok, nm = lift(Mod(2, n)^m); if (! vecsearch(sr, nm), sr = vecsort(concat(sr, nm), , 8); m = nm, ok = 0; ); ); #sr; } \\ Michel Marcus, Jun 14 2016

Crossrefs

Cf. A002326.

Sequence in context: A226763 A050500 A076885 * A285189 A051889 A086707

Adjacent sequences: A274021 A274022 A274023 * A274025 A274026 A274027

Keyword

nonn

Author

Michel Lagneau, Jun 07 2016

Status

approved