A277847 - OEIS

%I #27 Jan 02 2023 12:30:52

%S 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,

%T 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,

%U 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

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

%C Question raised by _David W. Wilson_, equivalent formulae given independently by _Don Reble_ and _Robert Israel_, cf. link to the SeqFan list.

%C "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.

%H David W. Wilson, <a href="/A277847/b277847.txt">Table of n, a(n) for n = 1..10000</a>

%H Don Reble, in reply to D. Wilson, <a href="http://list.seqfan.eu/oldermail/seqfan/2016-November/016878.html">Mapping problem</a>, SeqFan list, Nov. 2016. (Click "Next" twice for R. Israel's reply.)

%F Multiplicative with a(p^e) = oddpart(phi(p^e))+1, where oddpart = A000265, phi = A000010.

%F Multiplicative with a(p^e) = 2 if p = 2; oddpart(p-1)*p^(e-1) + 1 if p > 2.

%e 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

%p 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

%t oddpart[n_] := n/2^IntegerExponent[n, 2];

%t a[n_] := a[n] = Module[{p, e}, If[n == 1, 1, Product[{p, e} = pe; oddpart[ EulerPhi[p^e]] + 1, {pe, FactorInteger[n]}]]];

%t Array[a, 100] (* _Jean-François Alcover_, Jul 29 2020 *)

%o (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))}

%o (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

%Y Cf. A000010.

%K nonn,mult

%O 1,2

%A _M. F. Hasler_, Nov 10 2016