A373624 Number of distinct subsets of Z/nZ generated by powers.

0, 1, 2, 3, 4, 4, 6, 5, 8, 7, 8, 5, 12, 7, 10, 12, 14, 6, 14, 7, 17, 15, 10, 5, 24, 11, 14, 15, 22, 7, 24, 9, 24, 15, 12, 20, 30, 10, 14, 21, 35, 9, 30, 9, 26, 30, 10, 5, 42, 15, 22, 18, 34, 7, 30, 20, 46, 21, 14, 5, 51, 13, 18, 43, 42, 30, 30, 9, 35, 15, 40, 9, 62, 13, 20, 33, 40

Offset: 0

Author

Thierry Banel, Jun 11 2024

Keywords

• nonn

Comments

Choose p in Z/nZ, then generate the finite subset {1,p,p^2,p^3,p^4,...}. It often happens that two different p give the same subset. Therefore, there may be less distinct subsets than n. a(n) gives the numbers of distinct subsets generated by all p in Z/nZ. Note that the subsets generated by 0, 1, -1 are counted. Those subsets are {1,0}, {1}, {1,-1}.

Examples

			a(7) = 5 because there are 5 distinct power generated subsets of Z/7Z, namely 0^i = {1,0}, 1^i = {1}, 2^i = {1,2,4}, 3^i = {1,3,2,6,4,5}, 6^i = {1,6}. 4^i generates the same subset as 2^i (in a different order, but that is irrelevant). 5^i generate the same subset as 3^i (in a different order).
		

Programs

PARI

a(n) = #Set(vector(n, i, Set(vector(n, j, Mod(i-1, n)^(j-1))))); \\ Michel Marcus, Jun 12 2024