A277847 Size of the largest subset of Z/nZ fixed by x -> x^2.

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

David W. Wilson, Table of n, a(n) for n = 1..10000

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

Adjacent sequences: A277844 A277845 A277846 * A277848 A277849 A277850

Keyword

nonn,mult

Author

M. F. Hasler, Nov 10 2016

Status

approved