A309414 -id:A309414 - cp's OEIS frontend

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

M. F. Hasler, Nov 10 2016

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.

			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

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

Cf. A000010, A000265, A309414.

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

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

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

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

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

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.

A381348 Irregular triangle read by rows in which row n lists the largest subset of Z/nZ fixed by x -> x^2.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 0, 1, 4, 7, 0, 1, 5, 6, 0, 1, 3, 4, 5, 9, 0, 1, 4, 9, 0, 1, 3, 9, 0, 1, 2, 4, 7, 8, 9, 11, 0, 1, 6, 10, 0, 1, 0, 1, 0, 1, 4, 7, 9, 10, 13, 16, 0, 1, 4, 5, 6, 7, 9, 11, 16, 17, 0, 1, 5, 16, 0, 1, 4, 7, 9, 15, 16, 18

Offset: 1

Aloe Poliszuk, Feb 20 2025

Row n has length A277847(n).
Repeated squaring (application of f: x -> x^2) of the set of integers mod n results in a set that is fixed under f. Row n lists this set for modulus n. The number of applications of f to reach this fixed set is A309414(n).
Equivalently, row n lists the set of elements x such that, for some k, x^(2^k) == x (mod n), i.e. those x which are part of a cycle under x -> x^2 mod n.
For prime p of the form 4k + 3 (A002145), row p gives exactly the set of quadratic residues mod p. As such, row p has (p + 1) / 2 elements.
When n is a prime power (A000961) the product of row n (excluding 0) is equivalent to 1 mod n. Otherwise this product is equivalent to 0.

			Triangle begins:
  (mod 1)     0;
  (mod 2)     0, 1;
  (mod 3)     0, 1;
  (mod 4)     0, 1;
  (mod 5)     0, 1;
  (mod 6)     0, 1, 3, 4;
  (mod 7)     0, 1, 2, 4;
  (mod 8)     0, 1;
  (mod 9)     0, 1, 4, 7;
  (mod 10)    0, 1, 5, 6;
  (mod 11)    0, 1, 3, 4, 5, 9;
  (mod 12)    0, 1, 4, 9;
  (mod 13)    0, 1, 3, 9;
  (mod 14)    0, 1, 2, 4, 7, 8, 9, 11;
  (mod 15)    0, 1, 6, 10;
  (mod 16)    0, 1;
  (mod 17)    0, 1;
              ...

Aloe Poliszuk, First 349 rows, flattened into a sequence of n, a(n) for n = 1..13345

Cf. A002145, A096008, A096088, A277847, A309414.

row(n)=my(p=[0..n>>1], c=[0..n>>1]); until(p==c, p=c; c=Set([lift(Mod(v, n)^2)|v<-c])); return(c);

def row(n):
    l = set(range((n >> 1) + 1))
    while True:
        newl = {x**2 % n for x in l}
        if newl == l: break
        l = newl
    return l

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A381348 Irregular triangle read by rows in which row n lists the largest subset of Z/nZ fixed by x -> x^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python