A002729 -id:A002729 - cp's OEIS frontend

A357001 a(n) = A002729(n) - A357000(n) - 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 43, 0, 12, 0, 0, 0, 0, 0, 1954, 8, 0, 342, 0, 0, 0, 0

Offset: 1

Pontus von Brömssen, Sep 08 2022

Cf. A002729, A357000, A357002.

a(30)-a(31) (using data in A002729 and A357000) from Pontus von Brömssen, Jun 28 2023

A062163 Duplicate of A002729.

Original entry on oeis.org

1, 2, 3, 4, 6, 6, 13, 10, 24, 22, 45, 30, 158, 74, 245, 368, 693, 522, 2637, 1610, 7386

Offset: 0

dead

A056371 Number of step shifted (decimated) sequences using a maximum of two different symbols.

Original entry on oeis.org

2, 4, 6, 12, 12, 40, 28, 96, 104, 280, 216, 1248, 704, 2800, 4344, 8928, 8232, 44224, 29204, 136032, 176752, 419872, 381492, 2150400, 1678256, 5594000, 7461168, 22553408, 19175160, 134391040, 71585136, 269510016, 429726240, 1073758360

Offset: 1

Marks R. Nester

nonn

All step shifts of a sequence are considered to be equivalent, where a step shift transformation is obtained by selecting every k-th element of a sequence for some k relatively prime to n. For example, 2 is relatively prime to 5 and a 2-step shift of abcde is bdace.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

G. C. Greubel, Table of n, a(n) for n = 1..1000
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.

Cf. A002729.

A row or column of A132191.

a[m_, n_] := (1/EulerPhi[n])*Sum[If[GCD[k, n] == 1, m^DivisorSum[n, EulerPhi[#] / MultiplicativeOrder[k, #]&], 0], {k, n}]; Table[a[2, n], {n, 34}] (* Jean-François Alcover, Dec 04 2015 *)

{ a(n) = sum(k=1,n, if(gcd(k,n)==1, 2^sumdiv(n,d,eulerphi(d)/znorder(Mod(k,d))), 0); ) / eulerphi(n) } /* Max Alekseyev, Jun 18 2007 */

The cycle index is implicit in Titsworth.

a(n) = ( Sum_{k=1..n : gcd(k,n)=1} 2^( Sum_{d|n} A000010(d)/ord_d(k) ) ) / A000010(n), where ord_d(k) is the multiplicative order of k modulo d. - Max Alekseyev, Jun 18 2007, corrected Nov 08 2007

More terms from Max Alekseyev, Jun 18 2007

A285548 Array read by antidiagonals: T(m,n) = number of step cyclic shifted sequences of length n using a maximum of m different symbols.

Original entry on oeis.org

1, 1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 6, 10, 10, 5, 1, 6, 21, 20, 15, 6, 1, 13, 24, 55, 35, 21, 7, 1, 10, 92, 76, 120, 56, 28, 8, 1, 24, 78, 430, 201, 231, 84, 36, 9, 1, 22, 327, 460, 1505, 462, 406, 120, 45, 10, 1, 45, 443, 2605, 2015, 4291, 952, 666, 165, 55, 11

Offset: 1

Andrew Howroyd, Apr 20 2017

See A056371, A002729 for an explanation of step shifts. Under step cyclic shifts, abcde, bdace, bcdea, cdeab and daceb etc. are equivalent.
Equivalently, the number of mappings with domain {0..n-1} and codomain {1..m} up to equivalence.  Mappings A and B are equivalent if there is a d, prime to n, and a t such that A(i) = B((i*d + t) mod n) for i in {0..n-1}.
All column sequences are polynomials of order n.

			Table starts:
1  1  1   1   1     1     1      1      1       1 ...
2  3  4   6   6    13    10     24     22      45 ...
3  6 10  21  24    92    78    327    443    1632 ...
4 10 20  55  76   430   460   2605   5164   26962 ...
5 15 35 120 201  1505  2015  14070  37085  246753 ...
6 21 56 231 462  4291  6966  57561 188866 1519035 ...
7 28 84 406 952 10528 20140 192094 752087 7079800 ...
...

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Andrew Howroyd, Table of n, a(n) for n = 1..1275
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.

Rows 2-6 are A002729, A056411, A056412, A056413, A056414.

Cf. A285522, A132191.

IsLeastPoint[s_, f_] := Module[{t=f[s]}, While[t>s, t=f[t]]; Boole[s==t]];
c[n_, k_, t_] := Sum[IsLeastPoint[u, Mod[#*k+t, n]&], {u, 0, n-1}];
a[n_, x_] := Sum[If[GCD[k, n] == 1, x^c[n, k, t], 0], {t, 0, n-1}, {k, 1,
n}] / (n*EulerPhi[n]);
Table[a[n-m+1, m], {n, 1, 11}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jun 05 2017, translated from PARI *)

IsLeastPoint(s,f)={my(t=f(s)); while(t>s,t=f(t));s==t}
C(n,k,t)=sum(u=0,n-1,IsLeastPoint(u,v->(v*k+t)%n));
a(n,x)=sum(t=0, n-1, sum(k=1, n, if (gcd(k, n)==1, x^C(n,k,t),0)))/(n * eulerphi(n));
for(m=1, 7, for(n=1, 10, print1( a(n,m), ", ") ); print(); );

A056411 Number of step cyclic shifted sequences using a maximum of three different symbols.

Original entry on oeis.org

3, 6, 10, 21, 24, 92, 78, 327, 443, 1632, 1698, 12769, 10464, 57840, 122822, 348222, 476052, 3597442, 3401970, 22006959, 41597374, 142677588, 186077886, 1476697627, 1694658003, 8147282460, 15690973754, 68149816689, 84520682160, 857935531804, 664166389302, 3620293575942, 8422974597554, 30656600391720, 59561470990362

Offset: 1

Marks R. Nester

nonn

See A056371 for an explanation of step shifts. Under step cyclic shifts, abcde, bdace, bcdea, cdeab and daceb etc. are equivalent.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

D. Z. Dokovic, I. Kotsireas et al., Charm bracelets and their application to the construction of periodic Golay pairs, arXiv:1405.7328 [math.CO], 2014.
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.

Row 3 of A285548.
Cf. A002729.
Cf. A056412, A056413, A056414.

M[j_, L_] := Module[{m=1}, While[Sum[j^i, {i, 0, m-1}] ~Mod~ L != 0, m++]; m]; c[j_, t_, n_] := Sum[1/M[j, n/GCD[n, u*(j-1)+t]], {u, 0, n-1}]; CB[n_, k_] = If [n==1, k, 1/(n*EulerPhi[n])*Sum[If[1==GCD[n, j], k^c[j, t, n], 0], {t, 0, n-1}, {j, 1, n-1}]]; Table[Print[cb = CB[n, 3]]; cb, {n, 1, 35}] (* Jean-François Alcover, Dec 04 2015, after Joerg Arndt *)

\\ see p.3 of the Dokovic et al. reference
M(j,  L)={my(m=1); while ( sum(i=0, m-1, j^i) % L != 0, m+=1 ); m; }
c(j, t, n)=sum(u=0,n-1, 1/M(j, n / gcd(n, u*(j-1)+t) ) );
CB(n, k)=if (n==1,k, 1/(n*eulerphi(n)) * sum(t=0,n-1, sum(j=1,n-1, if(1==gcd(n,j), k^c(j,t,n), 0) ) ) );
for(n=1, 66, print1(CB(n,3),", "));
\\ second argument k=3, 4, 5, 6 respectively gives A056411, A056412, A056413, A056414.
\\ Joerg Arndt, Aug 27 2014

Refer to Titsworth or slight "simplification" in Nester.

Added more terms, Joerg Arndt, Aug 27 2014

A056412 Number of step cyclic shifted sequences using a maximum of four different symbols.

Original entry on oeis.org

4, 10, 20, 55, 76, 430, 460, 2605, 5164, 26962, 38572, 367645, 431780, 3203430, 8993804, 33860125, 63177820, 636462350, 803796700, 6886280971, 17456594380, 79965550558, 139069427020, 1466861706095, 2251803181492, 14434628481170, 37066691779180, 214483458079665, 354963555781060, 4803855154772166

Offset: 1

Marks R. Nester

nonn

See A056371 for an explanation of step shifts. Under step cyclic shifts, abcde, bdace, bcdea, cdeab and daceb etc. are equivalent.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

D. Z. Dokovic, I. Kotsireas et al., Charm bracelets and their application to the construction of periodic Golay pairs, arXiv:1405.7328 [math.CO], 2014.
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.

Row 4 of A285548.

Cf. A002729.

M[j_, L_] := Module[{m = 1}, While[Sum[j^i, {i, 0, m-1}] ~Mod~ L != 0, m++]; m]; c[j_, t_, n_] := Sum[1/M[j, n / GCD[n, u*(j-1) + t]], {u, 0, n - 1}]; CB[n_, k_] = If[n==1, k, 1/(n*EulerPhi[n]) * Sum[ If[1 == GCD[n, j], k^c[j, t, n], 0] , {t, 0, n-1}, {j, 1, n-1}]]; Table[Print[cb = CB[n, 4]]; cb, {n, 1, 30}] (* Jean-François Alcover, Dec 04 2015, after Joerg Arndt *)

\\ see p.3 of the Dokovic et al. reference
M(j,  L)={my(m=1); while ( sum(i=0, m-1, j^i) % L != 0, m+=1 ); m; }
c(j, t, n)=sum(u=0,n-1, 1/M(j, n / gcd(n, u*(j-1)+t) ) );
CB(n, k)=if (n==1,k, 1/(n*eulerphi(n)) * sum(t=0,n-1, sum(j=1,n-1, if(1==gcd(n,j), k^c(j,t,n), 0) ) ) );
for(n=1, 66, print1(CB(n,4),", "));
\\ Joerg Arndt, Aug 27 2014

Refer to Titsworth or slight "simplification" in Nester.

Added more terms, Joerg Arndt, Aug 27 2014

A056413 Number of step cyclic shifted sequences using a maximum of five different symbols.

Original entry on oeis.org

5, 15, 35, 120, 201, 1505, 2015, 14070, 37085, 246753, 445515, 5205790, 7832185, 72703645, 254689657, 1196213445, 2805046965, 35322811755, 55770979195, 596439735024, 1892294578755, 10837223014665, 23559159229935, 310484619147940, 596046508875701, 4776013513099405, 15330413466776835, 110874578286500410

Offset: 1

Marks R. Nester

nonn

See A056371 for an explanation of step shifts. Under step cyclic shifts, abcde, bdace, bcdea, cdeab and daceb etc. are equivalent.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

D. Z. Dokovic, I. Kotsireas et al., Charm bracelets and their application to the construction of periodic Golay pairs, arXiv:1405.7328 [math.CO], 2014.
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.

Row 5 of A285548.

Cf. A002729.

M[j_, L_] := Module[{m = 1}, While[Sum[ j^i, {i, 0, m - 1}] ~Mod~ L != 0, m++]; m]; c[j_, t_, n_] := Sum[ 1/M[j, n / GCD[n, u*(j - 1) + t] ], {u, 0, n - 1} ]; CB[n_, k_] = If [n == 1, k, 1/(n*EulerPhi[n]) * Sum[ If[1 == GCD[n, j], k^c[j, t, n], 0] , {t, 0, n-1}, {j, 1, n-1}]]; Table[ Print[ cb = CB[n, 5]]; cb, {n, 1, 28}] (* Jean-François Alcover, Dec 04 2015, after Joerg Arndt *)

\\ see p.3 of the Dokovic et al. reference
M(j,  L)={my(m=1); while ( sum(i=0, m-1, j^i) % L != 0, m+=1 ); m; }
c(j, t, n)=sum(u=0,n-1, 1/M(j, n / gcd(n, u*(j-1)+t) ) );
CB(n, k)=if (n==1,k, 1/(n*eulerphi(n)) * sum(t=0,n-1, sum(j=1,n-1, if(1==gcd(n,j), k^c(j,t,n), 0) ) ) );
for(n=1, 66, print1(CB(n,5),", "));
\\ Joerg Arndt, Aug 27 2014

Refer to Titsworth or slight "simplification" in Nester.

Added more terms, Joerg Arndt, Aug 27 2014

A056414 Number of step cyclic shifted sequences using a maximum of six different symbols.

Original entry on oeis.org

6, 21, 56, 231, 462, 4291, 6966, 57561, 188866, 1519035, 3302922, 45921281, 83747286, 933081411, 3920355712, 22075451286, 62230996506, 940379310731, 1781757016326, 22856965214727, 87052415641136, 598280600648031, 1560731765058606, 24680195365765751, 56860576713326910, 546736312124316741, 2105947271634851386

Offset: 1

Marks R. Nester

nonn

See A056371 for an explanation of step shifts. Under step cyclic shifts, abcde, bdace, bcdea, cdeab and daceb etc. are equivalent.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

D. Z. Dokovic, I. Kotsireas et al., Charm bracelets and their application to the construction of periodic Golay pairs, arXiv:1405.7328 [math.CO], 2014.
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.

Row 6 of A285548.

Cf. A002729.

M[j_, L_] := Module[{m = 1}, While[Sum[ j^i, {i, 0, m - 1}] ~Mod~ L != 0, m++]; m]; c[j_, t_, n_] := Sum[ 1/M[j, n / GCD[n, u*(j - 1) + t] ], {u, 0, n - 1}]; CB[n_, k_] = If[n == 1, k, 1/(n*EulerPhi[n]) * Sum[ If[1 == GCD[n, j], k^c[j, t, n], 0], {t, 0, n-1}, {j, 1, n-1}]]; Table[ Print[ cb = CB[n, 6]]; cb, {n, 1, 27}] (* Jean-François Alcover, Dec 04 2015, after Joerg Arndt *)

\\ see p.3 of the Dokovic et al. reference
M(j,  L)={my(m=1); while ( sum(i=0, m-1, j^i) % L != 0, m+=1 ); m; }
c(j, t, n)=sum(u=0,n-1, 1/M(j, n / gcd(n, u*(j-1)+t) ) );
CB(n, k)=if (n==1,k, 1/(n*eulerphi(n)) * sum(t=0,n-1, sum(j=1,n-1, if(1==gcd(n,j), k^c(j,t,n), 0) ) ) );
for(n=1, 66, print1(CB(n,6),", "));
\\ Joerg Arndt, Aug 27 2014

Refer to Titsworth or slight "simplification" in Nester.

Added more terms, Joerg Arndt, Aug 27 2014

A285522 Array read by antidiagonals: T(m,n) = number of circulant digraphs up to Cayley isomorphism on n vertices with edges colored according to step value using a maximum of m-1 colors.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 6, 6, 4, 1, 1, 6, 18, 10, 5, 1, 1, 20, 24, 40, 15, 6, 1, 1, 14, 135, 70, 75, 21, 7, 1, 1, 48, 130, 544, 165, 126, 28, 8, 1, 1, 52, 648, 700, 1625, 336, 196, 36, 9, 1, 1, 140, 1137, 4480, 2635, 3996, 616, 288, 45, 10, 1

Offset: 1

Andrew Howroyd, Apr 20 2017

For the base case of m=2 the sequence counts circulant digraphs up to Cayley isomorphism. Two circulant graphs are Cayley isomorphic if there is a d, which is necessarily prime to n, that transforms through multiplication modulo n the step values of one graph into those of the other. For squarefree n this is the only way that two circulant graphs can be isomorphic. (See Liskovets reference for a proof.)
Alternatively, the number of mappings with domain {1..n-1} and codomain {1..m} up to equivalence. Mappings A and B are equivalent if there is a d, prime to n, such that A(i) = B(i*d mod n) for i in {1..n-1}. This sequence differs from A132191 only in that sequence also includes 0 in the domain which introduces an extra factor of m into the results since zero multiplied by anything is zero.
All column sequences are polynomials of order n-1 and these are the cycle index polynomials.
This sequence is also related to A075195(n, m) which counts necklaces and A285548(m, n) which is the sequence described in the Titsworth reference. In particular, A075195 is the analogous array with equivalence determined through the additive group instead of by multiplication whereas A285548 allows for both addition and multiplication.

			Table starts:
\n  1 2  3   4    5    6    7     8      9      10
m\ ---------------------------------------------------
1 | 1 1  1   1    1    1    1     1      1       1 ...
2 | 1 2  3   6    6   20   14    48     52     140 ...
3 | 1 3  6  18   24  135  130   648   1137    4995 ...
4 | 1 4 10  40   70  544  700  4480  11056   65824 ...
5 | 1 5 15  75  165 1625 2635 20625  65425  489125 ...
6 | 1 6 21 126  336 3996 7826 72576 280596 2521476 ...
...
Case n=10:
Only 1, 3, 7, 9 are prime to 10.
Multiplication modulo 10 is described by the following multiplication table.
  1, 2, 3, 4, 5, 6, 7, 8, 9  => (1)(2)(3)(4)(5)(6)(7)(8)(9) => m^9
  3, 6, 9, 2, 5, 8, 1, 4, 7  => (1397)(2684)(5)             => m^3
  7, 4, 1, 8, 5, 2, 9, 6, 3  => (1793)(2486)(5)             => m^3
  9, 8, 7, 6, 5, 4, 3, 2, 1  => (19)(28)(37)(46)(5)         => m^5
Each row of the multiplication table can be viewed as a permutation and together these form a commutative group on 4 elements. In this case the group is isomorphic to the cyclic group C_4. Each permutation can be represented in cycle notation. (shown above to the right of the corresponding multiplication table row). In order to count the equivalence classes using Polya's enumeration theorem only the number of cycles in each permutation is needed.
This gives the cycle index polynomial (1/4)*(m^9 + m^5 + 2*m^3). Putting m = 1..4 gives 1, 140, 4995, 65824.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders.
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.
Eric Weisstein's World of Mathematics, Circulant Graph.
Wikipedia, Polya enumeration theorem.

Row 2 is A056391.
Columns include A002411, A006528, A168178, A006565, A282613, A054624.
Cf. A132191, A075195, A285548, A002729.

A132191[m_, n_] := (1/EulerPhi[n])*Sum[If[GCD[k, n] == 1, m^DivisorSum[n, EulerPhi[#] / MultiplicativeOrder[k, #] &], 0], {k, 1, n}];
T[m_, n_] := A132191[m, n]/m;
Table[T[m - n + 1, n], {m, 1, 11}, {n, m, 1, -1}] // Flatten (* Jean-François Alcover, Jun 06 2017 *)

a(n,x)=sum(k=1, n, if(gcd(k, n)==1, x^(sumdiv(n, d, eulerphi(d)/znorder(Mod(k, d)))-1), 0))/eulerphi(n);
for(m=1, 6, for(n=1, 10, print1( a(n,m), ", ") ); print(); );

T(m, n) = A132191(m, n) / m.

A357000 Number of non-isomorphic cyclic Haar graphs on 2*n nodes.

Original entry on oeis.org

1, 2, 3, 5, 5, 12, 9, 22, 21, 44, 29, 157, 73, 244, 367, 649, 521, 2624, 1609, 7385, 8867, 19400, 16769, 92529, 67553, 216274, 277191, 815557, 662369, 4500266, 2311469

Offset: 1

Pontus von Brömssen, Sep 08 2022

The first value of n for which a(n) < A002729(n) - 1 is n = 8. This is because the first counterexample to the bicirculant analog to Ádám's conjecture occurs for n = 8. In the terminology of Hladnik, Marušič, and Pisanski, the smallest integer pair (i,j) such that i and j are Haar equivalent (i.e., the cyclic Haar graphs with indices i and j are isomorphic) but not cyclically equivalent (see A357005) is (141,147). See also A357001 and A357002.

Terms a(1)-a(29) were found by generating the cyclic Haar graphs with indices in A333764, and filtering out isomorphic graphs using Brendan McKay's software nauty.

Milan Hladnik, Dragan Marušič, and Tomaž Pisanski, Cyclic Haar graphs, Discrete Mathematics 244 (2002), 137-152.
Eric Weisstein's World of Mathematics, Haar Graph

Cf. A002729, A008965, A049287, A091696, A137706, A291166, A333764, A339502, A357001, A357002, A357003, A357004, A357005, A357006.

a(n) is the number of terms k of A137706 in the interval 2^(n-1) <= k < 2^n.
a(n) is the number of fixed points k of A357004 in the interval 2^(n-1) <= k < 2^n.
a(n) <= A002729(n)-1 <= A091696(n) <= A008965(n).

a(30) from Eric W. Weisstein, Jun 27 2023

a(31) from Eric W. Weisstein, Jun 28 2023

cp's OEIS Frontend

A357001 a(n) = A002729(n) - A357000(n) - 1.

Views

Author

Keywords

Crossrefs

Extensions

A062163 Duplicate of A002729.

Views

Author

Keywords

A056371 Number of step shifted (decimated) sequences using a maximum of two different symbols.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A285548 Array read by antidiagonals: T(m,n) = number of step cyclic shifted sequences of length n using a maximum of m different symbols.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A056411 Number of step cyclic shifted sequences using a maximum of three different symbols.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A056412 Number of step cyclic shifted sequences using a maximum of four different symbols.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A056413 Number of step cyclic shifted sequences using a maximum of five different symbols.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A056414 Number of step cyclic shifted sequences using a maximum of six different symbols.

Views

Author

Keywords

Comments