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

Author

M. F. Hasler, Nov 10 2016

Keywords

• nonn
• mult

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.

Examples

			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
		

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.)

Crossrefs

Cf. A000010, A000265, A309414.

Programs

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 *)

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

Python

from math import prod
from sympy import totient, factorint
def A277847(n): return prod(((m:=int(totient(p**e)))>>(~m&m-1).bit_length())+1 for p,e in factorint(n).items()) # Chai Wah Wu, Feb 24 2025

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.