login
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.
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
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
KEYWORD
nonn
AUTHOR
Michel Lagneau, Jun 07 2016
STATUS
approved