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

Joerg Arndt arndt at jjj.de
Tue Jun 9 04:38:25 CEST 2009

```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

```

More information about the SeqFan mailing list