cp's OEIS Frontend

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

%I A373624 #17 Oct 05 2024 10:13:19
%S A373624 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,
%T A373624 22,7,24,9,24,15,12,20,30,10,14,21,35,9,30,9,26,30,10,5,42,15,22,18,
%U A373624 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
%N A373624 Number of distinct subsets of Z/nZ generated by powers.
%C A373624 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}.
%e A373624 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).
%o A373624 (C++)
%o A373624 #include <iostream>
%o A373624 #include <vector>
%o A373624 #include <set>
%o A373624 using namespace std;
%o A373624 // computes the number of power generated subsets of Z/nZ
%o A373624 int A (int n)
%o A373624 {
%o A373624   // all subsets are stored here
%o A373624   set<vector<bool>> subsets;
%o A373624   for (int p=0; p<n; p++) {
%o A373624     // a n-bits vector of already seen powers of p
%o A373624     vector<bool> powers(n);
%o A373624     // fill in powers
%o A373624     for (int q=1; !powers[q]; q = (q*p)%n)
%o A373624       powers[q] = true;
%o A373624     // store one subset,
%o A373624     // but only if it is not already stored
%o A373624     subsets.insert(powers);
%o A373624   }
%o A373624   // return number of distinct subsets
%o A373624   return subsets.size();
%o A373624 }
%o A373624 int main()
%o A373624 {
%o A373624   for (int n=0; n<30; n++)
%o A373624     cout<<A(n)<<"\n";
%o A373624 }
%o A373624 (PARI) a(n) = #Set(vector(n, i, Set(vector(n, j, Mod(i-1, n)^(j-1))))); \\ _Michel Marcus_, Jun 12 2024
%K A373624 nonn
%O A373624 0,3
%A A373624 _Thierry Banel_, Jun 11 2024