A373624 - OEIS

%I #17 Oct 05 2024 10:13:19

%S 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 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 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 Number of distinct subsets of Z/nZ generated by powers.

%C 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 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 (C++)

%o #include <iostream>

%o #include <vector>

%o #include <set>

%o using namespace std;

%o // computes the number of power generated subsets of Z/nZ

%o int A (int n)

%o {

%o   // all subsets are stored here

%o   set<vector<bool>> subsets;

%o   for (int p=0; p<n; p++) {

%o     // a n-bits vector of already seen powers of p

%o     vector<bool> powers(n);

%o     // fill in powers

%o     for (int q=1; !powers[q]; q = (q*p)%n)

%o       powers[q] = true;

%o     // store one subset,

%o     // but only if it is not already stored

%o     subsets.insert(powers);

%o   }

%o   // return number of distinct subsets

%o   return subsets.size();

%o }

%o int main()

%o {

%o   for (int n=0; n<30; n++)

%o     cout<<A(n)<<"\n";

%o }

%o (PARI) a(n) = #Set(vector(n, i, Set(vector(n, j, Mod(i-1, n)^(j-1))))); \\ _Michel Marcus_, Jun 12 2024

%K nonn

%O 0,3

%A _Thierry Banel_, Jun 11 2024