A273724 - OEIS

%I #35 Jan 11 2019 00:56:17

%S 0,0,0,2,1,4,4,6,3,8,8,10,9,12,12,14,11,16,16,18,17,20,20,22,19,24,24,

%T 26,25,28,28,30,27,32,32,34,33,36,36,38,35,40,40,42,41,44,44,46,43,48,

%U 48,50,49,52,52,54,51,56,56,58,57,60,60,62,59,64,64,66,65,68,68,70,67,72,72,74,73,76,76,78,75,80,80

%N Place n equally-spaced points around a circle, labeled 0,1,2,...,n-1. For each i = 0..n-1 such that 3i != i mod n, draw an (undirected) chord from i to (3i mod n). Then a(n) is the total number of distinct chords.

%H Brooke Logan and N. J. A. Sloane, <a href="/A273724/b273724.txt">Table of n, a(n) for n = 0..10000</a>

%H Kival Ngaokrajang, <a href="/A273724/a273724.pdf">Illustration of initial terms</a>

%H Burkard Polster, <a href="https://www.youtube.com/watch?v=qhbuKbxJsk8">Times Tables, Mandelbrot and the Heart of Mathematics</a>, Mathologer video (2015).

%F a(n) = n-1 if n>0 is odd, n-2 if n == +-2 (mod 8), n-3 if n == 4 (mod 8), and n-5 if n == 0 (mod 8). These formulas are easily established by observing that the chord at i is missing if 2i == 0 mod n, and the chords starting at i and at 3i coincide if 8i == 0 mod n. The formulas then imply that the g.f. is 4+x^2/(1-x)^2-(4+x^2+2*x^4+x^6)/(1-x^8), which can be rewritten as (5*x^63*x^5+2*x^4+3*x^2-x+2)*x^3/((1-x)*(1-x^8)). (This g.f. was conjectured by _Colin Barker_.) - _Brooke Logan_ and _N. J. A. Sloane_, Jun 23 2016

%F a(n) = a(n-1)+a(n-8)-a(n-9) for n>9. - _Colin Barker_, May 29 2016 (This follows from the above g.f. - _Brooke Logan_ and _N. J. A. Sloane_)

%o (Small Basic)

%o For n=0 to 200

%o For i = 0 To n-1

%o   x[i]=0

%o   a=i*3

%o   b=a-n

%o   c=a-2*n

%o   If b<0 And c<0 Then

%o     x[i]=a

%o   EndIf

%o   If b>0 And c<0 Then

%o     x[i]=b

%o   EndIf

%o   If b>0 And c>0 Then

%o     x[i]=c

%o   EndIf

%o EndFor

%o c=0

%o For j = 0 To n-1

%o   For k=0 To j

%o     If x[j]=k And x[k]=j Then

%o       c=c+1

%o     EndIf

%o   EndFor

%o EndFor

%o aa=n-c

%o TextWindow.Write(aa+", ")

%o Endfor

%Y Cf. A117571 (if 3i is changed to 2i), A274462 (if 3i is changed to 4i).

%K nonn

%O 0,4

%A _Kival Ngaokrajang_, May 28 2016

%E Definition edited by _N. J. A. Sloane_, Jun 23 2016