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