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,1

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.

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

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

Prog

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

Crossrefs

Cf. A002729.

A row or column of A132191.

Sequence in context: A137387 A137394 A062856 * A271822 A067874 A015733

Adjacent sequences: A056368 A056369 A056370 * A056372 A056373 A056374

Keyword

nonn

Author

Marks R. Nester

Extensions

More terms from Max Alekseyev, Jun 18 2007

Status

approved