|
%I #37 Nov 04 2021 09:40:00
%S 1,3,9,12,18,21,27,30,36,39,45,48,54,57,63,66,72,75,81,84,90,93,99,
%T 102,108,111,117,120,126,129,135,138,144,147,153,156,162,165,171,174,
%U 180,183,189,192,198,201,207,210,216,219,225,228,234,237,243,246,252
%N Start with a single equilateral triangle for n=0; for the odd n-th generation add a triangle at each expandable side of the triangles of the (n-1)-th generation (this is the "side to side" version); for the even n-th generation use the "vertex to vertex" version; a(n) is the number of triangles added in the n-th generation.
%C See a comment on V-V and V-S at A249246.
%C There are a total of 16 combinations as shown in the table below:
%C +-------------------------------------------------------+
%C | Even n-th version V-V S-V V-S S-S |
%C +-------------------------------------------------------+
%C | Odd n-th version |
%C | V-V A008486 A248969 A261951 A261952 |
%C | S-V A261950 A008486 A008486 A261956 |
%C | V-S A249246 A008486 A008486 A261957 |
%C | S-S a(n) A261954 A261955 A008486 |
%C +-------------------------------------------------------+
%C Note: V-V = vertex to vertex, S-V = side to vertex,
%C V-S = vertex to side, S-S = side to side.
%C From _Manfred Boergens_, Sep 21 2021: (Start)
%C For finite sets of random points in the real plane with exactly n nearest neighbors, a(n) for n >= 2 is a lower bound for the maximal number of points. Conjecturally, a(n) equals this number.
%C The randomness provides for pairwise different distances with probability = 1.
%C A point A is called a nearest neighbor if there is a point B with smaller distance to A than to any other point C.
%C In graph theory terms: Let G be a finite simple digraph; the vertices of G are arbitrary placed points in R^2 with pairwise different distances; the edges of G are arrows joining each point (tail end) to its nearest neighbor (head end). If G contains exactly n nearest neighbors and b(n) is the maximal number of points in any such graph then a(n) is the best lower bound known as yet for b(n).
%C a(n) for n >= 2 can be seen as an "inverse" to A347941.
%C a(n) is built by constructing G with m points and n nearest neighbors, m chosen as maximal as possible, then defining a(n)=m. The start is a(2)=9 and a(3)=12. We call the pairs (m,n)=(9,2) and (m,n)=(12,3) "anchor pairs" and proceed to bigger n by combining graphs with these anchor pairs to bigger graphs. So the next anchor pairs are (18,4), (21,5) and (27,6).
%C We conjecture that a(n) is optimal. This claim is true if the following assumptions hold:
%C - The anchor pairs (9,2) and (12,3) are optimal.
%C - All bigger anchor pairs (m,n) are constructed by combining copies of (9,2) if n is even and adding one (12,3) if n is odd.
%C (End)
%H Kival Ngaokrajang, <a href="/A261953/a261953.pdf">Illustration of initial terms</a>
%H Manfred Boergens, <a href="https://github.com/maboerg/Next-neighbours">Next-neighbours</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1).
%F a(0)=1, a(1)=3; for n >= 2, a(n) = a(n-1) + 6, if mod(n,2) = 0, otherwise a(n) = a(n-1) + 3.
%F From _Colin Barker_, Sep 10 2015: (Start)
%F a(n) = (3*(-1+(-1)^n+6*n))/4.
%F a(n) = a(n-1)+a(n-2)-a(n-3) for n>3.
%F G.f.: (x^3+5*x^2+2*x+1) / ((x-1)^2*(x+1)).
%F (End)
%F a(n) = 3 * A032766(n) for n>=1. - _Michel Marcus_, Sep 13 2015
%F a(0)=1; for n >= 1, a(n) = 9n/2 for even n, a(n) = (9n-3)/2 for odd n. - _Manfred Boergens_, Sep 21 2021
%e If the graph G in the comment by Manfred Boergens has 5 nearest neighbors there are at most 21 vertices in G (conjectured; it is proved that there are G with 5 nearest neighbors and 21 vertices but it is not yet proved that 21 is the maximum). - _Manfred Boergens_, Sep 21 2021
%t Join[{1}, Table[If[OddQ[n], (9 n - 3)/2, 9 n/2], {n, 1, 100}]] - _Manfred Boergens_, Sep 21 2021
%o (PARI) {a=3; print1("1, ", a, ", "); for(n=2, 100, if (Mod(n,2)==0, a=a+6, a=a+3); print1(a, ", "))}
%Y Cf. A032766, A008486, A248969, A249246, A347941.
%K nonn,easy
%O 0,2
%A _Kival Ngaokrajang_, Sep 06 2015
|
