A277847 -id:A277847 - cp's OEIS frontend

A381702 a(n) is the least k such that A277847(k) = 2*n.

2, 6, 11, 14, 19, 22, 53, 31, 137, 38, 43, 46, 101, 81, 59, 62, 67, 71, 149, 79, 83, 86, 181, 94, 197, 103, 107, 121, 229, 118, 977, 127, 131, 134, 139, 142, 293, 151, 617, 158, 163, 166, 1361, 258, 179, 362, 373, 191, 389, 199, 809, 206, 211, 214, 6977, 223, 227, 458, 937, 239, 30977, 1954, 251, 254, 1033, 262

Offset: 1

Aloe Poliszuk, Mar 03 2025

nonn

			Table of n, a(n), A277847(a(n)), [row(a(n))] starts (where row(n) is row n of A381348):
  1, 2,  2,  [0,1]
  2, 6,  4,  [0,1,3,4]
  3, 11, 6,  [0,1,3,4,5,9]
  4, 14, 8,  [0,1,2,4,7,8,9,11]
  5, 19, 10, [0,1,4,5,6,7,9,11,16,17]
  6, 22, 12, [0,1,3,4,5,9,11,12,14,15,16,20]
  ...

Cf. A381348, A277847.

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())
def a(n):
    n,i = 2*n,1
    while True:
        if A277847(i) == n: return i; i += 1

A382017 Record positions in A277847.

Original entry on oeis.org

1, 2, 6, 11, 14, 19, 22, 31, 38, 43, 46, 59, 62, 67, 71, 79, 83, 86, 94, 103, 107, 118, 127, 131, 134, 139, 142, 151, 158, 163, 166, 179, 191, 199, 206, 211, 214, 223, 227, 239, 251, 254, 262, 271, 278, 283, 302, 307, 311, 326, 331, 334, 347, 358, 367, 379, 382, 398, 419, 422, 431, 439, 443, 446

Offset: 1

Aloe Poliszuk, Mar 11 2025

nonn

Cf. A277847.

\\ uses A277847 by M. F. Hasler
a(n)=my(m=1,cn=1,cl=1,j=1);until(cn==n,cl=A277847(j);if(cl>m,m=cl;cn++,);j++);return(j-1)

A309414 Number of squaring iterations necessary to achieve the minimal residue class (mod n).

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 4, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 1, 2, 2, 1, 3, 1, 4, 2, 1, 2, 1, 2, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 4, 2, 2, 2, 2, 2, 1, 2, 1, 2, 2, 1, 1, 4, 2, 1, 1, 4, 1, 2, 1, 2, 3, 2, 2, 1, 1, 2, 1, 2, 2, 3, 1, 1, 4, 1, 2, 2, 3, 2, 2, 1, 1, 1, 2, 3, 5, 1, 1, 2, 2, 4, 1, 2, 2

Offset: 1

Brian Barsotti, Jul 29 2019

nonn

Starting with the integers {0, 1, ..., n-1}, a(n) represents the number of times you must apply the function f = (x)-> x^2 mod n to each element of a set in order to reach the smallest possible residue class modulo n.

			Under modulo 5, {0,1,2,3,4} becomes {0,1,4} through the first squaring iteration, which itself becomes {0,1} through the second iteration. This residue class cannot be reduced any further, so a(5) = 2.

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Cf. A277847.

a:= proc(n) local c, s, i, h; c, s:= n, {$0..n-1};
      for i from 0 do s:= map(x-> irem(x^2, n), s);
        h:= nops(s); if c=h then return i else c:= h fi
      od
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Jul 30 2019

a[n_] := Module[{c = n, s = Range[0, n-1], i, h}, For[i = 0, True, i++, s = Mod[#^2, n]& /@ s // Union; h = Length[s]; If[c==h, Return[i], c = h]]];
Array[a, 120] (* Jean-François Alcover, Nov 27 2020, after Alois P. Heinz *)

A343721 a(n) is the number of starting residues r modulo n from which repeated iterations of the mapping r -> r^2 mod n reach a fixed point.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 3, 8, 5, 10, 3, 12, 5, 6, 15, 16, 17, 10, 3, 20, 9, 6, 3, 24, 9, 10, 11, 12, 5, 30, 3, 32, 9, 34, 15, 20, 5, 6, 15, 40, 9, 18, 3, 12, 25, 6, 3, 48, 9, 18, 51, 20, 5, 22, 15, 24, 9, 10, 3, 60, 5, 6, 15, 64, 25, 18, 3, 68, 9, 30, 3, 40, 9, 10

Offset: 1

Jon E. Schoenfield, Apr 26 2021

nonn

			For every n >= 1, the residue r = 0 is a fixed point under the mapping r -> r^2 mod n, since we have 0 -> 0^2 mod n = 0. Also, for every n >= 2, the residue r = 1 is a fixed point, since we have 1 -> 1^2 mod n = 1.
For n=1, the only residue mod n is 0 (a fixed point), so a(1) = 1.
For n=2, the only residues are 0 and 1 (each a fixed point), so a(2) = 2.
For n=3, the only residue other than 0 and 1 is 2; 2 -> 2^2 mod 3 = 4 mod 3 = 1, a fixed point, so a(3) = 3.
For n=4, we have 0 -> 0, 1 -> 1, 2 -> 2^2 mod 4 = 4 mod 4 = 0, and 3 -> 3^2 mod 4 = 9 mod 4 = 1, each trajectory ending at a fixed point, so a(4) = 4.
For n=5, we have
  0 -> 0
  1 -> 1
  2 -> 4 -> 1 -> 1
  3 -> 4 -> 1 -> 1
  4 -> 1 -> 1
(each ending at a fixed point), so a(5) = 5.
For n=6, we have
  0 -> 0
  1 -> 1
  2 -> 4 -> 4
  3 -> 3
  4 -> 4
  5 -> 1 -> 1
(each ending at a fixed point), so a(6) = 6.
For n=7, however, we have
  0 -> 0
  1 -> 1
  2 -> 4 -> 2 -> ...       (a loop)
  3 -> 2 -> 4 -> 2 -> ...  (a loop)
  4 -> 2 -> 4 -> ...       (a loop)
  5 -> 4 -> 2 -> 4 -> ...  (a loop)
  6 -> 1 -> 1
so only 3 of the 7 trajectories reach a fixed point, so a(7)=3.

Michel Marcus, Table of n, a(n) for n = 1..2000

Cf. A277847, A343720, A343722.

pos(list, r) = forstep (k=#list, 1, -1, if (list[k] == r, return (#list - k + 1)););
isok(r, n) = {my(list = List()); listput(list, r); for (k=1, oo, r = lift(Mod(r, n)^2); my(i = pos(list, r)); if (i==1, return (1)); if (i>1, return(0)); listput(list, r); );} \\ reaches a fixed point
a(n) = sum(r=0, n-1, isok(r, n)); \\ Michel Marcus, May 02 2021

a(n) + A343722(n) = n. - Michel Marcus, May 02 2021

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

A381702 a(n) is the least k such that A277847(k) = 2*n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python

A382017 Record positions in A277847.

Views

Author

Keywords

Crossrefs

Programs

PARI

A309414 Number of squaring iterations necessary to achieve the minimal residue class (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A343721 a(n) is the number of starting residues r modulo n from which repeated iterations of the mapping r -> r^2 mod n reach a fixed point.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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