[seqfan] Re: Extending count of cyclotomic cosets to other moduli

[Vladimir Shevelev]

Sequences A141350 and A141390 list overpseudoprimes to bases 3 and 5 correspondingly.

Regards,
Vladimir

----- Original Message -----
From: Richard Mathar <mathar at strw.leidenuniv.nl>
Date: Saturday, June 19, 2010 22:31
Subject: [seqfan]  Extending count of cyclotomic cosets to other moduli
To: seqfan at seqfan.eu

> 
> 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 
> representedby A053446 and A050975. (Index notation does not work 
> for their staggering arguments...)
> The difference between these two sequences seems to be the 
> periodicallyextended 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 
> representedby A050977 and A053448.
> The difference between these two sequences seems to be the 
> periodicallyextended 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 
> representedby 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) ;
> 
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 

 Shevelev Vladimir‎