cp's OEIS Frontend

A077591 Maximum number of regions into which the plane can be divided using n (concave) quadrilaterals.

%I A077591 #95 Jul 13 2025 17:48:15
%S A077591 1,2,18,50,98,162,242,338,450,578,722,882,1058,1250,1458,1682,1922,
%T A077591 2178,2450,2738,3042,3362,3698,4050,4418,4802,5202,5618,6050,6498,
%U A077591 6962,7442,7938,8450,8978,9522,10082,10658,11250,11858,12482,13122,13778
%N A077591 Maximum number of regions into which the plane can be divided using n (concave) quadrilaterals.
%C A077591 Sequence found by reading the segment (1, 2) together with the line from 2, in the direction 2, 18, ..., in the square spiral whose vertices are the triangular numbers A000217. - _Omar E. Pol_, Sep 05 2011
%C A077591 For a(n) > 1, a(n) are the numbers such that phi(sum of the odd divisors of a(n)) = phi(sum of even divisors of a(n)). - _Michel Lagneau_, Sep 14 2011
%C A077591 Apart from first term, subsequence of A195605. - _Bruno Berselli_, Sep 21 2011
%C A077591 Engel expansion of 1F2(1; 1/2, 1/2; 1/8). - _Benedict W. J. Irwin_, Jun 21 2018
%C A077591 Let f(n) = 4*n^2 - 5, then (x, y, z) = (a(n+1), -f(n), -f(n + 1)) are solutions of the Diophantine equation x^3 + 4*y^3 + 4*z^3 = 512. - _XU Pingya_, Apr 25 2022
%H A077591 Vincenzo Librandi, <a href="/A077591/b077591.txt">Table of n, a(n) for n = 0..10000</a>
%H A077591 Keyang Li, <a href="/A077591/a077591_1.svg">when n=1, number of regions is 2; when n=2, maximum number of regions is 18</a>
%H A077591 Keyang Li, <a href="/A077591/a077591.svg">when n=3, maximum number of regions is 50</a>
%H A077591 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3, -3, 1).
%F A077591 a(n) = 8*n^2 - 8*n + 2 = 2*(2*n-1)^2, n > 0, a(0)=1.
%F A077591 Proof from _Keyang Li_, Jun 18 2022: (Start)
%F A077591 Represent the configuration of n concave quadrilaterals by a planar graph with a node for each vertex of the quadrilaterals and for each intersection point. Let there be v_n nodes and e_n edges. By Euler's formula for planar graphs, a(n) = e_n - v_n + 2. When we go from n to n+1 quadrilaterals, each side of the new quadrilateral can meet each side of the existing quadrilaterals at most 4 times, so Dv_n := v_{n+1} - v_n <= 4*4n = 16n.
%F A077591 Each of these intersection points increases the number of edges in the graph by 2, so De_n := e_{n+1} - e_n = 4 + 2*Dv_n, Da_n := a(n+1) - a(n) = 4 + Dv_n <= 4+16*n.
%F A077591 These upper bounds can be achieved by taking n interwoven concave quadrilaterals (for n=1,2,3 see the attached Keyang Li links), and we achieve a(n) = 8n^2 - 8n + 2 (and v_n = 8n^2 - 4n, e_n = 4n*(4n-3)) for n > 0. QED (End)
%F A077591 For n > 0: A071974(a(n)) = 2*n+1, A071975(a(n)) = 2. - _Reinhard Zumkeller_, Jul 10 2011
%F A077591 a(n) = 1 + A069129(n), if n >= 1. - _Omar E. Pol_, Sep 05 2011
%F A077591 a(n) = 2*A016754(n-1), if n >= 1. - _Omar E. Pol_, Sep 05 2011
%F A077591 G.f.: (1 - x + 15*x^2 + x^3)/(1-x)^3. - _Colin Barker_, Feb 23 2012
%F A077591 E.g.f.: (8*x^2 + 2)*exp(x) - 1. - _G. C. Greubel_, Jul 15 2017
%F A077591 From _Amiram Eldar_, Jan 29 2021: (Start)
%F A077591 Sum_{n>=1} 1/a(n) = Pi^2/16.
%F A077591 Sum_{n>=1} (-1)^(n+1)/a(n) = G/2, where G is Catalan constant (A006752).
%F A077591 Product_{n>=1} (1 + 1/a(n)) = cosh(Pi/sqrt(8)).
%F A077591 Product_{n>=1} (1 - 1/a(n)) = cos(Pi/sqrt(8)). (End)
%e A077591 a(2) = 18 if you draw two concave quadrilaterals such that all four sides of one cross all four sides of the other.
%p A077591 A077591:=n->`if`(n=0, 1, 8*n^2 - 8*n + 2); seq(A077591(n), n=0..50); # _Wesley Ivan Hurt_, Mar 12 2014
%t A077591 Table[2*(4*n^2 - 4*n + 1), {n,0,50}] (* _G. C. Greubel_, Jul 15 2017 *)
%o A077591 (PARI) isok(n) = (sod = sumdiv(n, d, (d%2)*d)) && (sed = sumdiv(n, d, (1 - d%2)*d)) && (eulerphi(sod) == eulerphi(sed)); \\ from _Michel Lagneau_ comment; _Michel Marcus_, Mar 15 2014
%o A077591 (GAP) Concatenation([1], List([1..2000], n->8*n^2 - 8*n + 2)); # _Muniru A Asiru_, Jan 29 2018
%Y A077591 Cf. A006752, A077588, A239186.
%Y A077591 Cf. A071974, A071975.
%Y A077591 Cf. A016754, A069129.
%K A077591 nonn,easy
%O A077591 0,2
%A A077591 _Joshua Zucker_ and the Castilleja School MathCounts club, Nov 07 2002