# [seqfan] Re: functions f:[n]->[n] such that f[(2*x) mod n]=[2*f(x)]

Max Alekseyev maxale at gmail.com
Tue Jun 9 09:48:51 CEST 2009

Joerg,

I've got the following formula for A117987:

Let m = 2^t * s where s is odd, and r be the multiplicative order of 2
modulo s. Then

A117987(m) = \prod_{d|r}  ( \sum_{q|d} q*c(m,q) )^c(m,d) * 2^( (2^t -
1) * d * c(m,d) )

where
c(m,d) = \sum_{k|d} moebius(d/k) * gcd(m,2^k-1) / d
btw, the function c(m,d) gives the number of cycles modulo under the
mapping x -> 2*x as discussed in our joint (unpublished) manuscript
with Maximilian Hasler and Tony Reix.

A corresponding PARI/GP code is:

{ A117987(m) = r=1; fordiv(znorder(Mod(2,m\2^valuation(m,2))),d,
r*=sumdiv(d,q,q*c(m,q))^c(m,d)*2^((2^valuation(m,2)-1)*d*c(m,d))   );
r }

The first 50 terms of A117987 are:

1, 2, 3, 8, 5, 24, 49, 128, 27, 160, 11, 1536, 13, 6272, 10125, 32768,
289, 13824, 19, 163840, 64827, 22528, 529, 6291456, 125, 106496, 729,
102760448, 29, 331776000, 887503681, 2147483648, 107811, 37879808,
300125, 3623878656, 37, 9961472, 177957, 171798691840, 1681,
135952072704, 79507, 94489280512, 184528125, 4437573632, 2209,
105553116266496, 117649, 4194304000

They match your calculations of vector(29,n,yPhi(x^n-1)), except for n=15.
Could you please check what can be a reason of this disagreement? Is
it an error somewhere or simply different sequences?

Regards,
Max

On Mon, Jun 8, 2009 at 10:38 PM, Joerg Arndt<arndt at jjj.de> wrote:
> Sequence A117987
> "Number of functions f:[n]->[n] such that f[(2*x) mod n]=[2*f(x)]
>  mod n for all x in [n], for n=1,2,3,... Here [n] denotes {0,1,2,...,n-1}"
> should get the "more" keyword, also seqs A117986 and A117988.
>
> CC author of these three seqs.
>
> Regarding A117987:
> The condition induces a graph on the set [n], this should allow
> for the computation of more terms (but my attempt failed).
>
> It appears the seq can be computed similarly to
> A003473 (Generalized Euler PHI function).
> Compute A003473 as follows (pari/gp):
>
> xPhi(p)=
> {
>    local(F, Fp, Fx, ret, dg);
>    p *= Mod(1,2);
>    F = factor(p);
>    Fp = F[,1];  \\ polys
>    Fx=F[,2]; \\ exponents
>    ret = 1;
>    for (j=1, #Fp, dg=poldegree(Fp[j]);  ret *= ( 1-2^(-dg) )^1  );
>    ret *= 2^n;
>    return( ret );
> } /* ----- */
>
> vector(23,n,xPhi(x^n-1))
> \\ A003473 Generalized Euler PHI function.
> \\ [1, 2, 3, 8, 15, 24, 49, 128, 189, 480, 1023, 1536, 4095, 6272, 10125, ...]
>
> vector(23,n,xPhi(x^n-1)/n)
> \\ A027362 Define a directed graph with 2n nodes {0..2n-1} and edges from each i to 2i (mod 2n) and to 2i+1 (mod 2n); a(n) is number of Hamiltonian cycles.
> \\ [1, 1, 1, 2, 3, 4, 7, 16, 21, 48, 93, 128, 315, 448, 675, 2048,...]
>
>
> Now modify the routine to account for the ORDER of the polynomials:
> \\ needs my files polorder.inc.gp and mersfact.inc.gp
> \\ from http://www.jjj.de/pari/
>
> \r polorder.inc.gp
>
> yPhi(p)=
> {
>    local(F, Fp, Fx, ret, dg, e);
>    p *= Mod(1,2);
>    F = factor(p);
>    Fp = F[,1];  \\ polys
>    Fx=F[,2]; \\ exponents
>
>    ret = 1;
>    for (j=1, #Fp,
>        dg = poldegree(Fp[j]);
>        setup_fact(dg);
> \\        ret *= ( (2^dg-1)/2^dg  );  \\ computes xPhi();
>        ret *= ( polorder(Fp[j])/2^dg );  \\ (2^dg-1) --> polorder
>    );
>    ret *= 2^n;
>    e = valuation(n,2);
>
>    return( ret );
> } /* ----- */
>
>
> tt=vector(29,n,yPhi(x^n-1))
> \\ [1, 2, 3, 8, 5, 24, 49, 128, 27, 160, 11, 1536, 13, 6272, 3375, 32768, 289, 13824, 19, 163840, 64827, 22528, 529, 6291456, 125, 106496, 729, 102760448, 29]
>
> \\ ***** NOTE: *****  Matches start of
> \\ A117987 Number of functions f:[n]->[n] such that f[(2*x) mod n]=[2*f(x)] mod n for all x in [n], for n=1,2,3,... Here [n] denotes {0,1,2,...,n-1}.
>
>
> tt=vector(29,n,yPhi(x^n-1)/n)
> \\ [1, 1, 1, 2, 1, 4, 7, 16, 3, 16, 1, 128, 1, 448, 225, 2048, 17, 768, 1, 8192, 3087, 1024, 23, ...]
> \\ not in OEIS
>
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>