A003095 -id:A003095 - cp's OEIS frontend

A072191 a(n) = a(n-1)^2 + 2.

0, 2, 6, 38, 1446, 2090918, 4371938082726, 19113842599189892819591078, 365338978906606237729724396156395693696687137202086, 133472569508521677503139972517335009022889462418844369330479463819154657319297609174034202576402751398

Offset: 0

Miklos Kristof, Jul 02 2002

This shows that in the Mandelbrot set (with z^2 + c), the point c = 2 escapes to infinity. - Alonso del Arte, Apr 08 2016

			0^2 + 2 = 2, 2^2 + 2 = 6, 6^2 + 2 = 38 ...

Mordechai Ben-Ari, Mathematical Logic for Computer Science, Third edition, 173-203

Samuel R. Buss, Herbrand's Theorem, University of California, San Diego La Jolla, California 92093-0112, U.S.A.
Neil J. Calkin, Eunice Y. S. Chan, and Robert M. Corless, Some Facts and Conjectures about Mandelbrot Polynomials, Maple Trans., Vol. 1, No. 1, Article 1 (July 2021).
Alessandro Farinelli, Herbrand Universe
Eric Weisstein's World of Mathematics, Weakly Binary Tree
Wikipedia, Herbrand Structure
Damiano Zanardini, Computational Logic, UPM European Master in Computational Logic (EMCL) School of Computer Science Technical University of Madrid, 2009-2010.
Index entries for sequences of form a(n+1)=a(n)^2 + ...

Cf. A001566 (a(n-1)^2-2), A003095 (a(n-1)^2+1).

[n le 1 select 0 else Self(n-1)^2+2: n in [1..10]]; // Vincenzo Librandi, Oct 05 2015

NestList[#^2 + 2 &, 0, 10]  (* Harvey P. Dale, Jan 23 2011 *)

a(n)=if(n<1, 0, 2+a(n-1)^2) /* Michael Somos, Mar 25 2006 */

a(n) ~ c^(2^n), where c = 1.57583423499194129500626808486999436507... - Vaclav Kotesovec, Sep 20 2013

a(n) mod 2 = 0. - Altug Alkan, Oct 04 2015

Edited by Robert G. Wilson v, Jul 03 2002

A088674 Coefficients of the eigenfunction of a sequence transformation.

Original entry on oeis.org

1, 3, 6, 45, 126, 750, 2796, 19389, 75894, 449562, 2027796, 12211794, 57895596, 332787324, 1677545304, 9766642077, 50378641830, 286825948194, 1529968671492, 8729259097158, 47374697101572, 269062276076868, 1484430536591592

Offset: 0

Michael Somos, Oct 04 2003

nonn

G.f. A(x) satisfies A(x^2) = (A(x/2)-1)/x - A(x/2)^2/2.
B(x) := 1/(2*x) - x*A(x^2) satisfies B(x)^2 + 1 = B(2*x^2).
Define f(n, c) := x - Sum_{k>=0} a(k)/(2*x)^(2*k+1) where x = c^(2^n). Then A003095(n+1) = A004019(n) + 1 = f(n, 1.502836801...). Also, A062013(n) = f(n, 1.78050350...).  - Michael Somos, Jun 07 2021

			G.f. = A(x) = 1 + 3*x + 6*x^2 + 45*x^3 + 126*x^4 + 750*x^5 + 2796*x^6 + ...
B(x) = 1/(2*x) - x - 3*x^3 - 6*x^5 - 45*x^7 - 126*x^9 - 750*x^11 - ... - _Michael Somos_, Jul 11 2019

Cf. A003095, A004019, A062013.

a[ n_] := If[n < 0, 0, Module[{A = 1 + O[x], m = 2}, While[m < n + 2, m *= 2; A = (Normal[ 1/x - Sqrt[ 1/x^2 - 2/x - 2*(Normal[A] /. x -> x^2) + O[x]^(m - 2)]] /. x -> 2*x) + O[x]^(m - 1) //PowerExpand]; SeriesCoefficient[A, n]]]; (* Michael Somos, Jun 07 2021 *)

{a(n) = my(A, m); if( n < 0, 0, m=2; A = 1 + O(x); while( m < n+2, m*=2; A = subst(1/x - sqrt(2*(subst((1/2)/x - A, x, x^2) - 1/x)), x, 2*x)); polcoeff(A, n))};

A168542 Number of trees that have a maximum 'n'.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 5, 10, 10, 20, 25, 50, 52, 104, 130, 260, 260, 520, 650, 1300, 1352, 2704, 3380, 6760, 6770, 13540, 16925, 33850, 35204, 70408, 88010, 176020, 176020, 352040, 440050, 880100, 915304, 1830608, 2288260, 4576520, 4583290, 9166580, 11458225

Offset: 0

Endi Begeja (andy.bege(AT)libero.it), Nov 29 2009

nonn

a(2^n) = Product_{k=1..n} A003095(k). - Michael Somos, Dec 20 2018

Alois P. Heinz, Table of n, a(n) for n = 0..5654

Cf. A003095, A070939, A309049.

Partial differences of A091980. - Alois P. Heinz, Jul 12 2019

b:= proc(n) option remember; `if`(n=0, 1, (g-> (f->
      1+b(f)*b(n-1-f))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
a:= n-> b(n)-`if`(n=0, 0, b(n-1)):
seq(a(n), n=0..45);  # Alois P. Heinz, Jul 12 2019

a[ n_] := If[ n < 3, Boole[n > 0], With[{m = BitLength[Quotient[n, 3]] - 1}, Nest[#^2 + 1 &, 2, m] a[n - 2 2^m]]]; (* Michael Somos, Dec 20 2018 *)

{a(n) = if( n<3, n>0, my(m = #binary(n\3)-1, t = 2); for(i=1, m, t = t^2+1); t*a(n - 2*2^m))}; /* Michael Somos, Dec 20 2018 */

a(1) = a(2) = 1, a(3*2^m + k) = A003095(m+2) * a(n - 2*2^m) where 0 <= k < 3*2^m. - Michael Somos, Dec 20 2018

a(n) = Sum_{k=0..n} (A309049(n,k)-A309049(n-1,k)) for n > 0, a(0) = 1. - Alois P. Heinz, Jul 12 2019

a(0)=1 prepended by Alois P. Heinz, Jul 12 2019

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","))

A024358 Sum of the sizes of binary subtrees of the perfect binary tree of height n.

Original entry on oeis.org

0, 1, 8, 105, 6136, 8766473, 8245941529080, 3508518207951157937469961, 311594265746788494170062926869662848646207622648, 1217308491239906829392988008143949647398943617188660186130545502913055217344025410733271773705

Offset: 0

Cyril Banderier, Jun 09 2000

Size of binary tree = number of internal nodes.

Alois P. Heinz, Table of n, a(n) for n = 0..12
Cyril Banderier, On the sum of the sizes of binary subtrees of a perfect binary tree, personal note, 2000.

Cf. A003095, A309049, A309052.

B:= proc(n) B(n):= `if`(n<0, 0, expand(1+x*B(n-1)^2)) end:
a:= n-> subs(x=1, diff(B(n), x)):
seq(a(n), n=0..9);  # Alois P. Heinz, Jul 12 2019

B[n_] := If[n<0, 0, Expand[1+x*B[n-1]^2]];
a[n_] := D[B[n], x] /. x -> 1;
Table[a[n], {n, 0, 9}] (* Jean-François Alcover, Oct 13 2022, after Alois P. Heinz *)

a(n) = B'n(1) where B{n+1}(x) = 1 + x*B_n(x)^2.
From Alois P. Heinz, Jul 12 2019: (Start)
a(n) = Sum_{k=0..2^n-1} (2^n-1-k) * A309049(2^n-1,k).
a(n) = A309052(2^n-1). (End)

a(0) changed to 0 by Alois P. Heinz, Jul 12 2019

A119687 f-Pascal's triangle where f(n) = n^2 = A000290(n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 5, 5, 1, 1, 26, 50, 26, 1, 1, 677, 3176, 3176, 677, 1, 1, 458330, 10545305, 20173952, 10545305, 458330, 1, 1, 210066388901, 111413523931925, 518191796841329, 518191796841329, 111413523931925, 210066388901, 1

Offset: 0

Philippe Deléham, Jun 09 2006

The second diagonal, T(n,n-1) = A003095(n). - Cortney Reagle, Sep 17 2019

			Triangle T(n,k) (with rows n >= 0 and columns 0 <= k <= n) begins as follows:
  1;
  1,      1;
  1,      2,        1;
  1,      5,        5,        1;
  1,     26,       50,       26,        1;
  1,    677,     3176,     3176,      677,      1;
  1, 458330, 10545305, 20173952, 10545305, 458330, 1;
  ...

Cortney Reagle, Table of n, a(n) for n = 0..104 (Rows n = 0..12 of the triangle, flattened)

Row sums are A327563.

Cf. A007318, A003095.

T(n)={my(M=matrix(n,n)); M[1,1]=1; for(n=2, n, M[n,1]=1; for(k=2, n, M[n,k]=M[n-1,k-1]^2 + M[n-1,k]^2)); M}
{ my(A=T(7)); for(i=1, #A, print(A[i,1..i])) } \\ Andrew Howroyd, Sep 17 2019

T(n, k) = T(n-1, k-1)^2 + T(n-1, k)^2; T(0,0) = 1; T(n,-1) = 0; T(n, k) = 0, n < k.

a(12) = 50 inserted and more terms added by Cortney Reagle, Sep 17 2019

A202019 Triangle by rows, related to the numbers of binary trees of height less than n, derived from the Mandelbrot set.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 4, 6, 6, 5, 2, 1, 1, 1, 8, 28, 60, 94, 116, 114, 94, 69, 44, 26, 14, 5, 2, 1, 1, 1, 16, 120, 568, 1932, 5096, 10948, 19788, 30782, 41944, 50788, 55308, 54746, 49700, 41658, 32398, 23461, 15864, 10068, 6036, 3434, 1860, 958, 470, 221, 100, 42, 14, 5, 2, 1, 1

Offset: 1

Gary W. Adamson, Dec 08 2011

As shown on p. 74 [Diaconis & Graham], n-th row polynomials are cyclic with period n, given real roots, if the polynomials are divided through by n. For example, taking x^3 + 2x^2 + x + 1 = 0, the real root = -1.75487766... = c. Then using x^2 + c, we obtain the period three trajectory: -1.75487... -> 1.32471...-> 0.
The shuffling connection [p.75], resulting in a permutation that is the Gilbreath shuffle: "To make the connection with shuffling cards, write down a periodic sequence starting at zero. Write a one above the smallest point, a two above the next smallest point and so on. For example, if c = -1.75486...(a period three point), we have:
2.............1.............3......
0........-1.75487........1.32471... For a fixed value of c, the numbers written on top code up a permutation that is a Gilbreath shuffle".
Row sums = A003095: (1, 2, 5, 26, 677,...) relating to the number of binary trees of height less than n.
Let f(z) = z^2 + c, then row k lists the expansion of the n-fold composition f(f(...f(0)...)) in falling powers of c (with the coefficients for c^0 omitted). The n initial terms of the reversed n-th row are the Catalan numbers (cf. A137560). - Joerg Arndt, Jun 04 2016

			Row 4 = (1, 4, 6, 6, 5, 2, 1, 1) since (x^4 + 2x^3 + x^2 + x)^2 + x = x^8 + 4x^7 + 6x^6 + 6x^5 + 5x^4 + 2x^3 + x^2 + x.
Triangle begins:
  1;
  1, 1;
  1, 2,  1,  1;
  1, 4,  6,  6,  5,   2,   1,  1;
  1, 8, 28, 60, 94, 116, 114, 94, 69, 44, 26, 14, 5, 2, 1, 1;
  ...

Persi Diaconis & R. L. Graham, "Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks", Princeton University Press, 2012; pp. 73-83.

Alois P. Heinz, Rows n = 1..13, flattened
Juan Carlos Nuño and Francisco J. Muñoz, Entropy-Variance curves of binary sequences generated by random substitutions of constant length, arXiv:2112.15563 [math.PR], 2021.

Row sums are A003095.
Cf. A137560 (reversed rows).
Cf. A309049.

b:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> expand(
      x^n+b(f)*b(n-1-f)))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(2^(n-1)-1)):
seq(T(n), n=1..7);  # Alois P. Heinz, Jul 11 2019

b[n_] := b[n] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f]*
     b[n-1-f]]][Min[g-1, n-g/2]]][2^(Length[IntegerDigits[n, 2]]-1)]];
T[n_] := CoefficientList[b[2^(n-1)-1], x];
Array[T, 7] // Flatten (* Jean-François Alcover, Feb 19 2021, after Alois P. Heinz *)

Coefficients of x by rows such that given n-th row p(x), the next row is (p(x))^2 + x; starting x -> (x^2 + x) -> (x^4 + 2*x^3 + x^2 + x)...

T(n,k) = A309049(2^(n-1)-1,k-1). - Alois P. Heinz, Jul 11 2019

A285934 Number of connected induced (non-null) subgraphs of the perfect binary tree of height n.

Original entry on oeis.org

1, 6, 37, 750, 459829, 210067308558, 44127887746326310604917, 1947270476915296449559791701269341583074001038

Offset: 0

Giovanni Resta, May 05 2017

A perfect (sometimes called complete) binary tree of height k has 2^(k+1)-1 nodes.

a(8) has 91 digits and thus it is not reported.

Alois P. Heinz, Table of n, a(n) for n = 0..11
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Wikipedia, Types of binary trees

Cf. A003095, A020873 (wheel), A059020 (ladder), A059525 (grid), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286186 (friendship), A286187 (web), A286188 (gear), A286189 (rook), A285765 (queen).

a[1]=b[1]=1; b[n_] := b[n] = 1 + b[n - 1]^2; a[n_] := a[n] = b[n]^2 + 2 a[n - 1]; Array[a, 8]

Let b(0)=1 and b(n) = 1+b(n-1)^2. Then, a(0)=1 and a(n) = b(n)^2 + 2*a(n-1). Note that b(n) = A003095(n+1).

A350130 Integers m such that iterating the map f(x) = x^2 + 1 on m generates a number ending with m.

Original entry on oeis.org

0, 1, 2, 5, 6, 7, 26, 30, 77, 205, 330, 677, 802, 901, 1205, 2026, 4330, 4677, 7802, 8901, 48901, 52026, 71205, 74330, 107802, 152026, 271205, 474330, 904677, 948901, 2152026, 5904677, 7271205, 8948901, 9107802, 10474330, 22152026, 55904677, 77271205, 88948901

Offset: 1

Ya-Ping Lu, Dec 15 2021

It takes 6 iterations for a term in the sequence to generate a number ending with the term itself. The numbers in the table below, except for those that begin with 0, are the terms with the numbers of digits (d) up to 10 in which the endings in the six iterations are: m1 -> m2 -> m3 -> m4 -> m5 -> m6 -> m1.
   d          m1          m2          m3          m4          m5          m6
  --  ----------  ----------  ----------  ----------  ----------  ----------
         0           1           2           5           6           7
        30          01          02          05          26          77
       330         901         802         205         026         677
      4330        8901        7802        1205        2026        4677
     74330       48901       07802       71205       52026       04677
    474330      948901      107802      271205      152026      904677
   0474330     8948901     9107802     7271205     2152026     5904677
  10474330    88948901    89107802    77271205    22152026    55904677
 510474330   588948901   989107802   977271205   122152026   455904677
6510474330  1588948901  9989107802  9977271205  8122152026  3455904677

Cf. A002522, A003095, A033627.

isok(m) = {my(mm=m); for (i=1, 6, mm = mm^2+1;); !((mm-m) % 10^(#Str(m)));} \\ Michel Marcus, Feb 16 2022

for n in range(0, 10**11):
    s = len(str(n)); t = n; L = set()
    while t not in L:
        L.add(t); t = (t*t+1) % 10**s
        if t == n: print(n, end = ', ')

A355108 Maximal number of root ancestral configurations among matching gene trees and species trees with n leaves.

Original entry on oeis.org

0, 1, 2, 4, 6, 10, 15, 25, 35, 55, 80, 130, 182, 286, 416, 676, 936, 1456, 2106, 3406, 4758, 7462, 10842, 17602, 24372, 37912, 54837, 88687, 123891, 194299, 282309, 458329, 634349, 986389, 1426439, 2306539, 3221843, 5052451, 7340711, 11917231, 16500521

Offset: 1

Noah A Rosenberg, Jun 19 2022

nonn

An ancestral configuration is a set of gene lineages present immediately before a node of a species tree is reached, looking backward in time, and a root ancestral configuration is an ancestral configuration at the root node. The term a(n) gives the largest number of root ancestral configurations among pairs (G,S) where G is a labeled gene tree topology, S is a bijectively labeled species tree topology, G and S have n leaves, and G=S.

F. Disanto and N. A. Rosenberg, Enumeration of ancestral configurations for matching gene trees and species trees, J. Comput. Biol. 24 (2017), 831-850.

Cf. A003095, A004019, A091980, A306390.

a:= proc(n) option remember; `if`(n=1, 0, (g-> (f->
     (1+a(f))*(1+a(n-f)))(min(g, n-g/2)))(2^ilog2(n)))
    end:
seq(a(n), n=1..42);  # Alois P. Heinz, Jun 19 2022

b[n_] := b[n] = If[n == 1, 1, 1+Max[Table[b[i] b[n-i], {i, n-1}]]];
a[n_] := b[n]-1;
Array[a, 42] (* Jean-François Alcover, Jun 25 2022 *)

a(n) = max_{i=1..floor(n/2)} (a(i)+1)*(a(n-i)+1), with a(1)=0.
a(n) = A091980(n) - 1.
a(2^n) = A004019(n) = A003095(n)^2.

cp's OEIS Frontend

A072191 a(n) = a(n-1)^2 + 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A088674 Coefficients of the eigenfunction of a sequence transformation.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A168542 Number of trees that have a maximum 'n'.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

A024358 Sum of the sizes of binary subtrees of the perfect binary tree of height n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A119687 f-Pascal's triangle where f(n) = n^2 = A000290(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A202019 Triangle by rows, related to the numbers of binary trees of height less than n, derived from the Mandelbrot set.

Views

Author

Keywords

Comments

Examples