A256349 -id:A256349 - cp's OEIS frontend

A248218 Period in residues modulo n in iteration of x^2 + 1 starting at 0.

1, 2, 1, 2, 3, 2, 1, 2, 3, 6, 2, 2, 4, 2, 3, 2, 6, 6, 1, 6, 1, 2, 2, 2, 3, 4, 3, 2, 2, 6, 1, 2, 2, 6, 3, 6, 1, 2, 4, 6, 7, 2, 1, 2, 3, 2, 4, 2, 6, 6, 6, 4, 2, 6, 6, 2, 1, 2, 3, 6, 10, 2, 3, 2, 12, 2, 2, 6, 2, 6, 11, 6, 6, 2, 3, 2, 2, 4, 4, 6, 9, 14, 5, 2, 6

Offset: 1

Vaclav Kotesovec, Oct 04 2014

nonn

a(n) is a period in the sequence A003095 modulo n.
For n <= 10000 is the maximal period a(7921) = 1232.
For n <= 100000 is the maximal period a(73205) = 7260.
For n <= 500000 is the maximal period a(357911) = 54670.
From Hermann Stamm-Wilbrandt, Jun 21 2021: (Start)
357911 = 71^3; a(71^2) = 770; a(71^3) = 71 * a(71^2); a(71^4) = 71 * a(71^3); a(71^5) = 71 * a(71^4); a(71^6) = 71 * a(71^5). 770/71^2 = 0.15274747073993255306, so cycle length is linear in n for these composite numbers. a(71^6) = 19566994370.
Let A(n) be number of start values that end on same cycle as start value 0. A(71^2) = 3711; A(71^3) = 71 * A(71^2); A(71^4) = 71 * A(71^3); A(71^5) = 71 * A(71^4). 3711/71^2 = 0.73616345963102559016, so majority of start values end on start value 0 cycle. (End)
Linear cycle length for a(71^i) with 2 <= i <= 5 sounds bad for runtime of Pollard-Rho factorization algorithm (heuristic claim assumes square root cycle length). The opposite is true, every value on start value 0 cycle has same remainder mod 71 as the value after applying "x -> (x^2 + 1) mod n" 11 times, so factorization completes quickly. - Hermann Stamm-Wilbrandt, Jun 29 2021

			n=5, residues are 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, ..., period is 3, a(5)=3.
n=7, residues are 1, 2, 5, 5, 5, 5, 5, ..., final period is 1, therefore a(7)=1.
n=10, residues are 1, 2, 5, 6, 7, 0, 1, 2, 5, 6, 7, 0, 1, 2, ..., a(10)=6.
n=43, residues are 1, 2, 5, 26, 32, 36, 7, 7, 7, 7, ..., a(43) = 1.
n=229, residues are 1, 2, 5, 26, 219, 101, 126, 76, 52, 186, 18, 96, 57, 44, 105, 34, 12, 145, 187, 162, 139, 86, 69, 182, 149, 218, 122, 0, 1, 2, 5, 26, 219, 101, 126, 76, 52, 186, 18, 96, 57, 44, 105, 34, 12, 145, 187, 162, 139, 86, 69, 182, 149, 218, 122, 0, 1, 2, 5, 26, ..., period is 28, a(229)=28.
This program is for experiments (n<100): Rest[NestList[Mod[#^2+1, n] &, 0, 100]]

Vaclav Kotesovec, Table of n, a(n) for n = 1..100000
Hermann Stamm-Wilbrandt, analyze.c
Hermann Stamm-Wilbrandt, period.c
Wikipedia, Pollard's Rho algorithm.

Cf. A248219, A256342-A256349, A003095, A247981, A001175.

/* See analyze.c in the Links section. This program computes a(n) for n < 2^31, all periods for any starting value. See also period.c which only computes period length, but with arbitrary precision gmplib. This allowed to compute a(71^6). - Hermann Stamm-Wilbrandt, Jun 22 2021 */

Table[m=Rest[NestList[Mod[#^2+1,n]&,0,1000]]; period=0; j=1; While[j<=Length[m] && period==0,If[m[[Length[m]-j]]==m[[Length[m]]],period=j]; j++]; period,{n,1,1000}]

A248218(m,t=0,u=[t])=until(#Set(u=concat(u,t=(t^2+1)%m))<#u,);for(i=1,#u,t==u[#u-i]&&return(i)) \\ M. F. Hasler, Mar 25 2015

a(LCM(i,j)) = LCM(a(i),a(j)). - Robert Israel, Mar 08 2021

A256342 Moduli n for which A248218(n) = 2 (length of the terminating cycle of 0 under x -> x^2+1 modulo n).

Original entry on oeis.org

2, 4, 6, 8, 11, 12, 14, 16, 22, 23, 24, 28, 29, 32, 33, 38, 42, 44, 46, 48, 53, 56, 58, 62, 64, 66, 67, 69, 74, 76, 77, 84, 86, 87, 88, 92, 96, 106, 107, 109, 112, 114, 116, 124, 127, 128, 132, 134, 138, 148, 152, 154, 159, 161, 163, 168, 172, 174, 176, 184, 186, 192

Offset: 1

M. F. Hasler, Mar 25 2015

nonn

If x is a member and y is a member of this sequence or A248219, then LCM(x,y) is a member. - Robert Israel, Mar 09 2021

			In Z/mZ with m = 2, the iteration of x -> x^2+1 starting at x = 0 yields (0, 1, 0, ...), and m = 2 is the least positive number for which there is such a cycle of length 2, here [0, 1], therefore a(1) = 2.
For m = 3, the iteration yields (0, 1, 2, 2, ...), i.e., a cycle [2] of length 1, therefore 3 is not in this sequence.
For m = 4, the iterations yield (0, 1, 2, 1, ...), and since there is again a cycle [1, 2] of length 2, a(2)=4.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A248218, A248219, A256343 - A256349, A003095, A247981.

filter:= proc(n) local x, k, R,p;
  x:= 0; R[0]:= 0;
  for k from 1 do
    x:= x^2+1 mod n;
    if assigned(R[x]) then return evalb(k-R[x] = 2)
    else R[x]:= k
    fi
  od;
end proc:
select(filter, [$1..1000]); # Robert Israel, Mar 09 2021

filterQ[n_] := Module[{x, k, R}, x = 0; R[0] = 0; For[k = 1, True, k++, x = Mod[x^2 + 1, n]; If[IntegerQ[R[x]], Return[k - R[x] == 2], R[x] = k]]];
Select[Range[1000], filterQ] (* Jean-François Alcover, Feb 01 2023, after Robert Israel *)

for(i=1,200,A248218(i)==2&&print1(i","))

A256343 Moduli k for which A248218(k) = 3 (length of the terminating cycle of 0 under x -> x^2+1 modulo k).

Original entry on oeis.org

5, 9, 15, 25, 27, 35, 45, 59, 63, 75, 95, 97, 105, 125, 135, 155, 171, 175, 177, 185, 189, 215, 225, 251, 279, 285, 291, 295, 315, 333, 375, 379, 387, 413, 419, 465, 475, 485, 513, 525, 531, 555, 617, 625, 645, 665, 675, 679, 753, 775, 785, 837, 855, 863, 873, 875, 885

Offset: 1

M. F. Hasler, Mar 25 2015

nonn

All terms are odd. - Robert Israel, Dec 09 2020

If x is a term and y is a term of this sequence or A248219, then LCM(x,y) is a term. - Robert Israel, Mar 09 2021

Robert Israel, Table of n, a(n) for n = 1..7000

Cf. A248218, A248219, A256342 - A256349, A003095, A247981.

f:= proc(n) local x, S, R,i;
  R:= Array(0..n,-1):
  R[0]:= 0: x:= 0;
  for i from 1 do
    x:= x^2+1 mod n;
    if R[x] >= 0 then return i - R[x] fi;
    R[x]:= i;
  od
end proc:
select(f=3, [seq(i,i=1..1000,2)]); # Robert Israel, Dec 09 2020

f[n_] := Module[{x, R, i}, R[_] = -1; R[0] = 0; x = 0; For[i = 1, True, i++, x = Mod[x^2+1, n]; If[R[x] >= 0, Return[i - R[x]]]; R[x] = i]];
Select[Table[i, {i, 1, 1000, 2}], f[#] == 3&] (* Jean-François Alcover, Feb 03 2023, after Robert Israel *)

for(i=1,900,A248218(i)==3&&print1(i","))

A256348 Moduli n for which A248218(n) = 8.

Original entry on oeis.org

193, 386, 461, 523, 579, 772, 887, 922, 1019, 1046, 1158, 1351, 1383, 1544, 1569, 1774, 1844, 1861, 2038, 2092, 2123, 2153, 2269, 2316, 2509, 2661, 2702, 2766, 2887, 3057, 3088, 3138, 3227, 3391, 3449, 3541, 3548, 3661, 3667, 3688, 3722, 3919

Offset: 1

M. F. Hasler, Mar 25 2015

nonn

If x and y are members, then so is LCM(x,y). - Robert Israel, Mar 08 2021

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A248218, A248219, A256342 - A256349, A003095, A247981.

filter:= proc(n) local x,k,R;
  x:= 0; R[0]:= 0;
  for k from 1 do
    x:= x^2+1 mod n;
    if assigned(R[x]) then return evalb(k-R[x] = 8)
    else R[x]:= k fi
  od;
end proc:
select(filter, [$1..5000]); # Robert Israel, Mar 08 2021

filter[n_] := Module[{x, k, R}, x = 0; R[0] = 0; For[k = 1, True, k++, x = Mod[x^2+1, n]; If[IntegerQ[R[x]], Return[k - R[x] == 8], R[x] = k]]];
Select[Range[4000], filter] (* Jean-François Alcover, May 15 2023, after Robert Israel *)

for(i=1,3000,A248218(i)==8&&print1(i","))

A256344 Moduli n for which A248218(n) = 4 (length of the terminating cycle of 0 under x -> x^2+1 modulo n).

Original entry on oeis.org

13, 26, 39, 47, 52, 78, 79, 91, 94, 104, 113, 141, 143, 156, 158, 169, 173, 182, 188, 197, 208, 226, 237, 247, 273, 282, 286, 299, 312, 316, 329, 338, 339, 346, 353, 364, 376, 377, 394, 403, 416, 429, 439, 452, 474, 481, 494, 507, 517, 519, 546, 553, 559, 564, 572, 591, 598

Offset: 1

M. F. Hasler, Mar 25 2015

nonn

If x is a member and y is a member of this sequence or A248219 or A256342, then LCM(x,y) is a member. - Robert Israel, Mar 09 2021

			See A256342 or A256349.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A248218, A248219, A256342 - A256349, A003095, A247981.

filter:= proc(n) local x, k, R,p;
  x:= 0; R[0]:= 0;
  for k from 1 do
    x:= x^2+1 mod n;
    if assigned(R[x]) then return evalb(k-R[x] = 4)
    else R[x]:= k
    fi
  od;
end proc:
select(filter, [$1..1000]); # Robert Israel, Mar 09 2021

for(i=1,600,A248218(i)==4&&print1(i","))

A256345 Moduli n for which A248218(n) = 5 (length of the terminating cycle of 0 under x -> x^2+1 modulo n).

Original entry on oeis.org

83, 151, 167, 223, 249, 257, 283, 359, 373, 453, 501, 563, 581, 607, 669, 677, 771, 821, 849, 953, 1057, 1077, 1119, 1169, 1321, 1561, 1577, 1689, 1743, 1799, 1821, 1981, 1987, 2017, 2031, 2463, 2513, 2573, 2611, 2833, 2859, 2869

Offset: 1

M. F. Hasler, Mar 25 2015

nonn

If x is a member and y is a member of this sequence or A248219, then LCM(x,y) is a member. - Robert Israel, Mar 09 2021

			See A256342 or A256349.

Robert Israel, Table of n, a(n) for n = 1..5000

Cf. A248218, A248219, A256342 - A256349, A003095, A247981.

filter:= proc(n) local x, k, R,p;
  x:= 0; R[0]:= 0;
  for k from 1 do
    x:= x^2+1 mod n;
    if assigned(R[x]) then return evalb(k-R[x] = 5)
    else R[x]:= k
    fi
  od;
end proc:
select(filter, [$1..3000]); # Robert Israel, Mar 09 2021

for(i=1,2900,A248218(i)==5&&print1(i","))

A256346 Moduli n for which A248218(n) = 6.

Original entry on oeis.org

10, 17, 18, 20, 30, 34, 36, 40, 49, 50, 51, 54, 55, 60, 68, 70, 72, 73, 80, 85, 90, 98, 99, 100, 102, 108, 110, 115, 118, 119, 120, 126, 136, 140, 144, 145, 146, 147, 150, 153, 160, 165, 170, 180, 187, 190, 194, 196, 198, 199, 200, 204, 207, 210, 211, 216, 219, 220, 230, 236, 238, 240, 245, 250

Offset: 1

M. F. Hasler, Mar 25 2015

nonn

If x is a member of this sequence, and y is a member of this sequence or A248219 or A256342 or A256343, then LCM(x,y) is a member of this sequence. - Robert Israel, Mar 09 2021

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A248218, A248219, A256342 - A256349, A003095, A247981.

filter:= proc(n) local x, k, R,p;
  x:= 0; R[0]:= 0;
  for k from 1 do
    x:= x^2+1 mod n;
    if assigned(R[x]) then return evalb(k-R[x] = 6)
    else R[x]:= k
    fi
  od;
end proc:
select(filter, [$1..1000]); # Robert Israel, Mar 09 2021

for(i=1,250,A248218(i)==6&&print1(i","))

A256347 Moduli n for which A248218(n) = 7.

Original entry on oeis.org

41, 123, 131, 287, 317, 393, 503, 547, 727, 779, 861, 917, 951, 1091, 1237, 1271, 1277, 1509, 1517, 1627, 1637, 1641, 1681, 1763, 2089, 2181, 2219, 2239, 2337, 2357, 2383, 2489, 2531, 2671, 2751, 2789

Offset: 1

M. F. Hasler, Mar 25 2015

nonn

If x is a member, and y is a member of this sequence or A248219, then LCM(x,y) is a member. - Robert Israel, Mar 09 2021

Robert Israel, Table of n, a(n) for n = 1..4000

Cf. A248218, A248219, A256342 - A256349, A003095, A247981.

filter:= proc(n) local x, k, R,p;
  x:= 0; R[0]:= 0;
  for k from 1 do
    x:= x^2+1 mod n;
    if assigned(R[x]) then return evalb(k-R[x] = 7)
    else R[x]:= k
    fi
  od;
end proc:
select(filter, [$1..10000]); # Robert Israel, Mar 09 2021

for(i=1,3000,A248218(i)==7&&print1(i","))

cp's OEIS Frontend

A248218 Period in residues modulo n in iteration of x^2 + 1 starting at 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Mathematica

PARI

Formula

A256342 Moduli n for which A248218(n) = 2 (length of the terminating cycle of 0 under x -> x^2+1 modulo n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A256343 Moduli k for which A248218(k) = 3 (length of the terminating cycle of 0 under x -> x^2+1 modulo k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A256348 Moduli n for which A248218(n) = 8.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A256344 Moduli n for which A248218(n) = 4 (length of the terminating cycle of 0 under x -> x^2+1 modulo n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

A256345 Moduli n for which A248218(n) = 5 (length of the terminating cycle of 0 under x -> x^2+1 modulo n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

A256346 Moduli n for which A248218(n) = 6.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI