OFFSET
0,3
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}.
EXAMPLE
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).
PROG
(C++)
#include <iostream>
#include <vector>
#include <set>
using namespace std;
// computes the number of power generated subsets of Z/nZ
int A (int n)
{
// all subsets are stored here
set<vector<bool>> subsets;
for (int p=0; p<n; p++) {
// a n-bits vector of already seen powers of p
vector<bool> powers(n);
// fill in powers
for (int q=1; !powers[q]; q = (q*p)%n)
powers[q] = true;
// store one subset,
// but only if it is not already stored
subsets.insert(powers);
}
// return number of distinct subsets
return subsets.size();
}
int main()
{
for (int n=0; n<30; n++)
cout<<A(n)<<"\n";
}
(PARI) a(n) = #Set(vector(n, i, Set(vector(n, j, Mod(i-1, n)^(j-1))))); \\ Michel Marcus, Jun 12 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Thierry Banel, Jun 11 2024
STATUS
approved