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

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

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

Table of n, a(n) for n=0..76.

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

Sequence in context: A063655 A111234 A117248 * A343292 A079788 A146288

Adjacent sequences: A373621 A373622 A373623 * A373626 A373627 A373628

Keyword

nonn

Author

Thierry Banel, Jun 11 2024

Status

approved