A276647 Number of squares after the n-th generation in a symmetric (with 45-degree angles) non-overlapping Pythagoras tree.

1, 3, 7, 15, 31, 59, 107, 183, 303, 483, 755, 1151, 1735, 2571, 3787, 5511, 7999, 11507, 16547, 23631, 33783, 48027, 68411, 96983, 137839, 195075, 276883, 391455, 555175, 784427, 1111979, 1570599, 2225823, 3143187, 4453763, 6288623, 8909911, 12579771

Offset: 0

Author

Ernst van de Kerkhof, Sep 13 2016

Keywords

• nonn
• easy

Comments

Non-overlapping is to be understood as: any two different squares in the tree can never share more than one side, disallowing area overlap. In branches where an area overlap is about to occur, growth is terminated.

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Ernst van de Kerkhof, Illustration of a(6)
• "QuantumKiwi", A Year in the Life of a Pythagoras Tree, YouTube, (2008).
• Wikipedia, Pythagoras tree (fractal)
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-5,6,-2).

Crossrefs

Partial sums of A276677.

Programs

Mathematica

TableForm[Table[{n, 20 * 2^Floor[n/2] + 28*2^Floor[(n-1)/2] - (2n^2 + 10n + 33)}, {n, 0, 100, 1}], TableSpacing -> {1, 5}]
LinearRecurrence[{3,-1,-5,6,-2},{1,3,7,15,31},50] (* Harvey P. Dale, May 07 2019 *)

PARI

Vec((1+x)^2*(1-2*x+2*x^2)/((1-x)^3*(1-2*x^2)) + O(x^50)) \\ Colin Barker, Sep 20 2016

Formula

Theorem: a(n) = 20*2^floor(n/2) + 28*2^floor((n-1)/2) - (2*n^2+10*n+33).

From Colin Barker, Sep 20 2016: (Start)

G.f.: (1+x)^2*(1-2*x+2*x^2) / ((1-x)^3*(1-2*x^2)).

a(n) = 3*a(n-1)-a(n-2)-5*a(n-3)+6*a(n-4)-2*a(n-5) for n>4.

a(n) = (-25+2^((n-1)/2)*(24-24*(-1)^n+17*sqrt(2)+17*(-1)^n*sqrt(2))-4*(1+n)-2*(1+n)*(2+n)). Therefore:

a(n) = 17*2^(n/2+1)-2*n^2-10*n-33 for n even.

a(n) = 3*2^((n+7)/2)-2*n^2-10*n-33 for n odd. (End)