login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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(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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 26 04:55 EDT 2019. Contains 322469 sequences. (Running on oeis4.)