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

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

Author

Marks R. Nester

Keywords

• nonn

Comments

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.

References

• 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]

Links

• 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.

Crossrefs

Cf. A002729.

A row or column of A132191.

Programs

Mathematica

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 *)

PARI

{ 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 */

Formula

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

Extensions

More terms from Max Alekseyev, Jun 18 2007