|
|
A373624
|
|
Number of distinct subsets of Z/nZ generated by powers.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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}.
|
|
LINKS
|
|
|
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 distinc 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
|
|
|
STATUS
|
approved
|
|
|
|