

A277847


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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(p1)*p^(e1) + 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


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 A074912
Adjacent sequences: A277844 A277845 A277846 * A277848 A277849 A277850


KEYWORD

nonn,mult


AUTHOR

M. F. Hasler, Nov 10 2016


STATUS

approved



