# [seqfan] Extending count of cyclotomic cosets to other moduli

Richard Mathar mathar at strw.leidenuniv.nl
Sat Jun 19 21:25:20 CEST 2010

```http://oeis.org/classic/A006694 looks at cycles of the permutation
[2 mod 2n+1, 4 mod 2n+1, 6 mod 2n+1,..., 4n mod 2n+1]. It can
also be generated by the formula (See the Allouche article)
a(n) = sum_{d| 2n+1, d>1} A000010(d) / A002326(d/2) .

One is tempted to look at A006694 as a sequence defined for the prime p=2,
which might be generalized to other primes p according to both methods
of computation --which generate different results:

i)
For p=3 we may define the number of cyclotomic cosets of 3 mod 3n+1,
1,1,2,4,5,1,4,2,5,1,2,2,11,1,4,2,13,5,2,6,9,3,8,6,5,1,10,6,13,17,4,2,9,3,2,4,
17,5,4,24,5,1,18,8,11,1,4,6,9,3,...

or
sum_{d| 3n+1, d>1} A000010(d) / multipl_order_3_mod_d
=
2,1,3,4,6,1,5,2,6,1,3,2,12,1,5,2,14,5,3,6,10,3,9,6,6,1,11,6,14,17,5,2,10,3,3,4,
18,5,5,24,6,1,19,8,12,1,5,6,10,3..

where the multipl_order_3_mod_n is the multiplicative order represented
by A053446 and A050975. (Index notation does not work for their staggering arguments...)
The difference between these two sequences seems to be the periodically
extended row in A093057: 1,0,1,0,1,0,1,0,1,0

ii)
For p=5 we may define the number of cyclotomic cosets of 5 mod 5n+1,
2,2,4,4,6,10,8,2,2,4,10,2,10,14,8,4,2,10,22,4,2,4,8,4,22,2,10,4,2,2,40,4,2,12,
20,12,42,10,8,10,2,6,26,16,2,14,8,6,14,10

or
sum_{d| 5n+1, d>1} A000010(d) / multipl_order_5_mod_d
=
3,2,7,4,7,10,11,2,3,4,13,2,11,14,11,4,3,10,25,4,3,4,11,4,23,2,13,4,3,2,43,4,
3,12,23,12,43,10,11,10,3,6,29,16,3,14,11,6,15,10

where the multipl_order_5_mod_n is the multiplicative order represented
by A050977 and A053448.
The difference between these two sequences seems to be the periodically
extended row in A093057: 1,0,3,0,1,0,3,0,1

iii)
For p=7 we may define the number of cyclotomic cosets of 7 mod 7n+1,
3,3,2,4,9,7,12,18,15,1,6,6,5,7,4,8,33,1,2,6,13,5,12,2,23,3,26,2,15,1,8,32,23,
1,6,4,25,3,4,14,59,5,2,6,5,13,24,6,59,19

or
sum_{d| 7n+1, d>1} A000010(d) / multipl_order_7_mod_d
=
4,5,3,4,14,7,13,20,16,1,11,6,6,9,5,8,38,1,3,8,14,5,17,2,24,5,27,2,20,1,9,34,
24,1,11,4,26,5,5,14,64,5,3,8,6,13,29,6,60,21

where the multipl_order_7_mod_n is the multiplicative order represented
by A050979 and A053450.
The difference between these two sequences seems to be a periodically
extended 6h row in A093057: 1,2,1,0,5,0,1,2,1,0,5,0,1,2,1,0,5,0

Generally, the "filler"-difference for the two variants of a general definition
seems to be the (p-1)st row in A093057, periodically extended.

The question that let me look at these: what is the generalization of
A137576 and/or A141232 to primes other than 2? Are these in the OEIS, for
example?

Richard Mathar

# Maple implementation, for the books:
A093057 := proc(n,p)
igcd((n-1) mod (p-1),p-1)-1 ;
end proc:

# The analog of the Allouche function f in "Suites infinie a repetitiones bonnes"
# Sem. Theorie Nombres Bordeaux 20 (1984)
# http://resolver.sub.uni-goettingen.de/purl?GDZPPN002545357
f := proc(n,p)
a := 0 ;
for d in numtheory[divisors](p*n+1) do
if d <> 1  then
a := a+numtheory[phi](d)/numtheory[order](p,d) ;
end if:
end do;
a ;
end proc:

with(group) ;
# The number of disjoint cycles in the permutation
# [p mod pn+1, 2p mod pn+1, 4p mod pn+1,... p^2n mod pn+1], see A006694.
A := proc(n,p)
a := [] ;
for i from 1 to p*n do
a := [op(a), (p*i) mod (p*n+1) ] ;
end do:
convert(a,'disjcyc') ;
nops(%) ;
end proc:

# a fixed prime, p=2 for A006694
p := 7 ;

# Print the sequence of multiplicative orders
seq(numtheory[order](p,n),n=2..50) ;

# Print the sequence of cylotomic cosets of p mod pn+1.
# First variant of a generalization.
seq(A(n,p),n=1..50) ;

# Print a generalized Allouche function f
# Second variant of a generalization.
seq(f(n,p),n=1..50) ;

# Check that the sum of the count of cosets and a line of A093057
# is the same as the generalized Allouche function.
seq(A(n,p)+A093057(n+2,p),n=1..50) ;

```