cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 12 results. Next

A003095 a(n) = a(n-1)^2 + 1 for n >= 1, with a(0) = 0.

Original entry on oeis.org

0, 1, 2, 5, 26, 677, 458330, 210066388901, 44127887745906175987802, 1947270476915296449559703445493848930452791205, 3791862310265926082868235028027893277370233152247388584761734150717768254410341175325352026
Offset: 0

Views

Author

N. J. A. Sloane and Richard Stanley

Keywords

Comments

Number of binary trees of height less than or equal to n. [Corrected by Orson R. L. Peters, Jan 03 2020]
The rightmost digits cycle (0,1,2,5,6,7,0,1,2,5,6,7,...). - Jonathan Vos Post, Jul 21 2005
Apart from the initial term, a subsequence of A008318. - Reinhard Zumkeller, Jan 17 2008
Partial sums of A001699. - Jonathan Vos Post, Feb 17 2010
Corresponds to the second and second last diagonals of A119687. - John M. Campbell, Jul 25 2011
This is a divisibility sequence. - Michael Somos, Jan 01 2013
Sum_{n>=1} 1/a(n) = 1.739940825174794649210636285335916041018367182486941... . - Vaclav Kotesovec, Jan 30 2015
From Vladimir Vesic, Oct 03 2015: (Start)
Forming Herbrand's domains of formula: (∃x)(∀y)(∀z)(∃k)(P(x)∨Q(y)∧R(k))
where: x->a
k->f(y,z)
we get:
H0 = {a}
H1 = {a, f(a,a)}
H2 = {a, f(a,a), f(a,f(a,a)), f(f(a,a),a), f(f(a,a),f(a,a))}
...
The number of elements in each domain follows this sequence.
(End)
It is an open question whether or not this sequence satisfies Benford's law [Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017
This is a strong divisibility sequence; see A329429. - Clark Kimberling, Nov 13 2019
From Peter Bala, Oct 31 2022: (Start)
Let k be a positive integer. Clearly, the sequence obtained by reducing a(n) modulo k is eventually periodic. Conjectures:
1) The sequence obtained by reducing a(n) modulo 2^k is eventually periodic with period 2.
2) The sequence obtained by reducing a(n) modulo 10^k is eventually periodic with period 6 (the case k = 1 is noted above).
3) The sequence obtained by reducing a(n) modulo 20^k is eventually periodic with period 6.
4) For n >= floor(k/2) and for 1 <= i <= 6, the value of a(6*n+i) mod 10^k is a constant independent of n. The digits of these 6 constant integers, when read from right to left, are the first k digits of the 10-adic numbers A318135 (i = 1), A318136 (i = 2), A318137 (i = 3), A318138 (i = 4), A318139 (i = 5) and A318140 (i = 6), respectively. An example is given below.
n a(6*n+1) mod 10^11
1 10066388901
2 72084948901
3 67988948901
4 61588948901
5 01588948901
6 01588948901
7 01588948901
... ...
A318135 begins 1, 0, 9, 8, 4, 9, 8, 8, 5, 1, 0, 2, .... (End)

References

  • Mordechai Ben-Ari, Mathematical Logic for Computer Science, Third edition, 173-203.
  • S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 443-448.
  • R. K. Guy, How to factor a number, Proc. 5th Manitoba Conf. Numerical Math., Congress. Num. 16 (1975), 49-89.
  • R. Penrose, The Emperor's New Mind, Oxford, 1989, p. 122.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A001699, A004019, A038044, A056207, A076949, A077496, A091980, A143848.
Cf. A143849, A213437, A247981, A248218, A248219, A318135, A318136, A318137.
Cf. A318138, A318139, A318140, A355108.
Cf. A137560, which enumerates binary trees of height less than n and exactly j leaf nodes. - Robert Munafo, Nov 03 2009

Programs

Formula

a(n) = B_{n-1}(1) where B_n(x) = 1 + x*B_{n-1}(x)^2 is the generating function of trees of height <= n.
a(n) is asymptotic to c^(2^n) where c=1.2259024435287485386279474959130085213... (see A076949). - Benoit Cloitre, Nov 27 2002
c = b^(1/4) where b is the constant in Bottomley's formula in A004019. a(n) appears very asymptotic to c^(2^n) - Sum_{k>=1} A088674(k)/(2*c^(2^n))^(2*k-1). - Gerald McGarvey, Nov 17 2007
a(n) = Sum_{i=1..n} A001699(i). - Jonathan Vos Post, Feb 17 2010
G.f. = x + 2*x^2 + 5*x^3 + 26*x^4 + 677*x^5 + 458330*x^6 + 210066388901*x^7 + ... . - Michael Somos, Jan 01 2013
a(2n) mod 2 = 0 ; a(2n+1) mod 2 = 1. - Altug Alkan, Oct 04 2015
a(n) + a(n-1) = A213437(n). - Peter Bala, Feb 03 2017
0 = a(n)^2*(+a(n+1) + a(n+2)) + a(n+1)^2*(-a(n+1) - a(n+2) - a(n+3)) + a(n+2)^3 for all n>=0. - Michael Somos, Feb 10 2017
a(n) = A091980(2^(n-1)) for n > 0. - Alois P. Heinz, Jul 11 2019

Extensions

Additional comments from Cyril Banderier, Jun 05 2000
Minor edits by Vaclav Kotesovec, Oct 04 2014
Initial term clarified by Clark Kimberling, Nov 13 2019

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

Original entry on oeis.org

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

Views

Author

Vaclav Kotesovec, Oct 04 2014

Keywords

Comments

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

Examples

			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]]

Links

Crossrefs

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

Programs

  • C
    /* 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 */
  • Mathematica
    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}]
  • PARI
    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

Formula

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

A248219 Indices where A248218(n) = 1.

Original entry on oeis.org

1, 3, 7, 19, 21, 31, 37, 43, 57, 93, 111, 129, 133, 157, 217, 259, 301, 307, 313, 399, 463, 471, 499, 589, 613, 651, 703, 777, 817, 903, 921, 939, 967, 1099, 1147, 1333, 1389, 1497, 1591, 1767, 1839, 2109, 2149, 2191, 2451, 2683, 2901, 2983, 3241, 3297, 3441
Offset: 1

Views

Author

Vaclav Kotesovec, Oct 04 2014

Keywords

Comments

n is in the sequence if there exists a number k0 such that A003095(k) mod n = A003095(k0) mod n for all k >= k0.
Conjecture: a(n) ~ n^2.

Examples

			7 is in the sequence since A003095 mod 7 is {1, 2, 5, 5, 5, 5, ...}, k0 = 3, A003095(k) mod 7 = 5 for all k >= k0. The period is 1.
10 is not in the sequence since A003095 mod 10 is {1, 2, 5, 6, 7, 0, 1, 2, 5, 6, 7, 0, 1, 2, ...} and the period is 6, not 1.

Links

Crossrefs

Cf. A003095, A247981, A248218.

Programs

  • Mathematica
    nmax=10000; periods=Table[m=Rest[NestList[Mod[#^2+1,n]&,0,nmax]]; period=0; j=1; While[j<=Length[m]&&period==0,If[m[[Length[m]-j]]==m[[Length[m]]],period=j]; j++]; period,{n,1,nmax}]; Select[Range[nmax],periods[[#]]==1&]

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

Views

Author

M. F. Hasler, Mar 25 2015

Keywords

Comments

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

Examples

			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.

Links

Crossrefs

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

Programs

  • Maple
    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
  • Mathematica
    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 *)
  • PARI
    for(i=1,200,A248218(i)==2&&print1(i","))

A256349 Moduli n for which A248218(n) = 9.

Original entry on oeis.org

81, 101, 271, 303, 361, 405, 505, 509, 567, 653, 707, 743, 813, 839, 909, 1033, 1083, 1187, 1355, 1447, 1515, 1527, 1539, 1753, 1805, 1897, 1919, 1959, 2025, 2121, 2229, 2381, 2439, 2511, 2517, 2525, 2527, 2545, 2579, 2687, 2727, 2749, 2753, 2777, 2803, 2835
Offset: 1

Views

Author

M. F. Hasler, Mar 25 2015

Keywords

Comments

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

Examples

			In Z/81Z, the iteration of x -> x^2+1 starting at x = 0 yields (0, 1, 2, 5, 26, 29, 32, 53, 56, 59, 80, 2, ...), and m = 81 is the least positive number for which there is such a cycle of length 9, here [2, 5, 26, 29, 32, 53, 56, 59, 80], therefore a(1) = 81.

Links

Crossrefs

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

Programs

  • Maple
    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] = 9)
    else R[x]:= k
    fi
  od;
end proc:
select(filter, [$1..10000]); # Robert Israel, Mar 09 2021
  • Mathematica
    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] == 9], R[x] = k]]];
Select[Range[10000], filterQ] (* Jean-François Alcover, Feb 01 2023, after Robert Israel *)
  • PARI
    for(i=1,3000,A248218(i)==9&&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

Views

Author

M. F. Hasler, Mar 25 2015

Keywords

Comments

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

Links

Crossrefs

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

Programs

  • Maple
    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
  • Mathematica
    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 *)
  • PARI
    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

Views

Author

M. F. Hasler, Mar 25 2015

Keywords

Comments

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

Links

Crossrefs

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

Programs

  • Maple
    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
  • Mathematica
    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 *)
  • PARI
    for(i=1,3000,A248218(i)==8&&print1(i","))

A328700 Numbers k dividing nonzero terms in A003095.

Original entry on oeis.org

1, 2, 5, 10, 13, 26, 41, 65, 82, 130, 137, 149, 205, 229, 274, 293, 298, 397, 410, 458, 509, 533, 586, 661, 677, 685, 709, 745, 761, 794, 809, 877, 881, 1018, 1066, 1145, 1217, 1249, 1277, 1322, 1354, 1370, 1418, 1465, 1490, 1522, 1601, 1618, 1754, 1762, 1781, 1937, 1985, 2053, 2290
Offset: 1

Views

Author

Jianing Song, Oct 26 2019

Keywords

Comments

k is a term if and only if A328699(k) = 0, in which case all the indices m such that k divides A003095(m) are m = t*A248218(k), t = 0, 1, 2, 3, ...

Examples

			41 divides A003095(7) = 210066388901, so 41 is in this sequence. In addition, 41 divides A003095(m) if and only if 7 divides m.
29 is not a term: {A003095(n) mod 29} = {0, 1, 2, 5, 26, 10, 14, 23, 8, 7, 21, 7, 21, 7, 21, ...}, so 29 does not divides A003095(m) for any m > 0.

Links

Crossrefs

Cf. A003095, A328699, A248218.
The primes in this sequence are given by A247981.

Programs

  • PARI
    v(n) = my(v=[0],k,flag=1); for(i=2, n+1, k=(v[#v]^2+1)%n; v=concat(v, k); for(j=1, i-1, if(v[j]==k, flag=0)); if(flag==0, break())); v;
is(n) = !(v(n)[#v(n)]);

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

Views

Author

M. F. Hasler, Mar 25 2015

Keywords

Comments

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

Examples

			See A256342 or A256349.

Links

Crossrefs

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

Programs

  • Maple
    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
  • PARI
    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

Views

Author

M. F. Hasler, Mar 25 2015

Keywords

Comments

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

Examples

			See A256342 or A256349.

Links

Crossrefs

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

Programs

  • Maple
    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
  • PARI
    for(i=1,2900,A248218(i)==5&&print1(i","))
Showing 1-10 of 12 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.