login
A277847
Size of the largest subset of Z/nZ fixed by x -> x^2.
3
1, 2, 2, 2, 2, 4, 4, 2, 4, 4, 6, 4, 4, 8, 4, 2, 2, 8, 10, 4, 8, 12, 12, 4, 6, 8, 10, 8, 8, 8, 16, 2, 12, 4, 8, 8, 10, 20, 8, 4, 6, 16, 22, 12, 8, 24, 24, 4, 22, 12, 4, 8, 14, 20, 12, 8, 20, 16, 30, 8, 16, 32, 16, 2, 8, 24, 34, 4, 24, 16, 36, 8, 10, 20, 12, 20, 24, 16, 40, 4, 28, 12, 42, 16, 4, 44
OFFSET
1,2
COMMENTS
Question raised by David W. Wilson, equivalent formulae given independently by Don Reble and Robert Israel, cf. link to the SeqFan list.
"Fixed" means that f(S) = S, for the subset S and f = x -> x^2. The largest stable or "invariant" subset would be Z/nZ itself.
LINKS
Don Reble, in reply to D. Wilson, Mapping problem, SeqFan list, Nov. 2016. (Click "Next" twice for R. Israel's reply.)
FORMULA
Multiplicative with a(p^e) = oddpart(phi(p^e))+1, where oddpart = A000265, phi = A000010.
Multiplicative with a(p^e) = 2 if p = 2; oddpart(p-1)*p^(e-1) + 1 if p > 2.
EXAMPLE
a(25) = 6 is the cardinal of S = {0, 1, 6, 11, 16, 21}, the largest set of residues modulo 25 fixed by the mapping n -> n^2. - David W. Wilson, Nov 08 2016
MAPLE
f:= proc(n) local F; F:= ifactors(n)[2]; convert(map(proc(t) local p; p:=numtheory:-phi(t[1]^t[2]); 1+p/2^padic:-ordp(p, 2) end proc, F), `*`) end proc: # Robert Israel, Nov 09 2016
MATHEMATICA
oddpart[n_] := n/2^IntegerExponent[n, 2];
a[n_] := a[n] = Module[{p, e}, If[n == 1, 1, Product[{p, e} = pe; oddpart[ EulerPhi[p^e]] + 1, {pe, FactorInteger[n]}]]];
Array[a, 100] (* Jean-François Alcover, Jul 29 2020 *)
PROG
(PARI) A277847(n)={prod( i=1, #n=factor(n)~, if(n[1, i]>2, 1 + n[1, i]>>valuation(n[1, i]-1, 2) * n[1, i]^(n[2, i]-1), 2))}
(PARI) a(n, f=factor(n)~)=prod(i=1, #f, (n=eulerphi(f[1, i]^f[2, i]))>>valuation(n, 2)+1) \\ about 10% slower than the above
CROSSREFS
Cf. A000010.
Sequence in context: A224516 A023161 A023155 * A085311 A052273 A369291
KEYWORD
nonn,mult
AUTHOR
M. F. Hasler, Nov 10 2016
STATUS
approved