cp's OEIS Frontend

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

%I A277847 #37 Feb 25 2025 07:17:09
%S A277847 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 A277847 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 A277847 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 A277847 Size of the largest subset of Z/nZ fixed by x -> x^2.
%C A277847 Question raised by _David W. Wilson_, equivalent formulae given independently by _Don Reble_ and _Robert Israel_, cf. link to the SeqFan list.
%C A277847 "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 A277847 David W. Wilson, <a href="/A277847/b277847.txt">Table of n, a(n) for n = 1..10000</a>
%H A277847 Don Reble, in reply to D. Wilson, <a href="https://web.archive.org/web/*/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 A277847 Multiplicative with a(p^e) = oddpart(phi(p^e))+1, where oddpart = A000265, phi = A000010.
%F A277847 Multiplicative with a(p^e) = 2 if p = 2; oddpart(p-1)*p^(e-1) + 1 if p > 2.
%e A277847 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 A277847 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 A277847 oddpart[n_] := n/2^IntegerExponent[n, 2];
%t A277847 a[n_] := a[n] = Module[{p, e}, If[n == 1, 1, Product[{p, e} = pe; oddpart[ EulerPhi[p^e]] + 1, {pe, FactorInteger[n]}]]];
%t A277847 Array[a, 100] (* _Jean-François Alcover_, Jul 29 2020 *)
%o A277847 (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 A277847 (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
%o A277847 (Python)
%o A277847 from math import prod
%o A277847 from sympy import totient, factorint
%o A277847 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
%Y A277847 Cf. A000010, A000265, A309414.
%K A277847 nonn,mult
%O A277847 1,2
%A A277847 _M. F. Hasler_, Nov 10 2016