cp's OEIS Frontend

A114146 Number of threshold functions on n X n grid.

%I A114146 #45 Aug 16 2021 14:45:57
%S A114146 1,2,14,58,174,402,838,1498,2566,4082,6214,8986,12790,17490,23646,
%T A114146 31114,40150,50914,64174,79450,97870,118914,143110,170506,202502,
%U A114146 238082,278702,323866,374510,430274,493382,561834,638694,722658,814606,914362,1023430,1140466
%N A114146 Number of threshold functions on n X n grid.
%C A114146 Also, number of intersections of a halfspace with an n X n grid. While A114043 counts cuts, this sequence counts sides of cuts. The only difference between this and twice A114043 is that this makes sense for the empty grid. This is the "labeled" version - rotations and reflections are not taken into account. - _David Applegate_, Feb 24 2006
%C A114146 In the terminology of Koplowitz et al., this is the number of linear dichotomies on a square grid. - _N. J. A. Sloane_, Mar 14 2020
%H A114146 Chai Wah Wu, <a href="/A114146/b114146.txt">Table of n, a(n) for n = 0..10000</a>
%H A114146 M. A. Alekseyev. <a href="https://arxiv.org/abs/math/0602511">On the number of two-dimensional threshold functions</a>, arXiv:math/0602511 [math.CO], 2006-2010; doi:<a href="http://dx.doi.org/10.1137/090750184">10.1137/090750184</a>, SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631.
%H A114146 M. A. Alekseyev, M. Basova, N. Yu. Zolotykh. <a href="http://dx.doi.org/10.1137/140978090">On the minimal teaching sets of two-dimensional threshold functions</a>. SIAM J. Disc. Math. 29(1), 2015, pp. 157-165.
%H A114146 Jack Koplowitz, Michael Lindenbaum and A. Bruckstein, <a href="https://doi.org/10.1109/18.50392">The number of digital straight lines on an N*N grid</a>, IEEE Transactions on Information Theory 36.1 (1990): 192-197. See D(n).
%H A114146 N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)
%F A114146 For n>0, a(n) = 2*A114043(n).
%F A114146 For n>0, a(n) = 8*n^2 - 12*n + 6 + 4*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - _Chai Wah Wu_, Aug 15 2021
%t A114146 a[0] = 1; a[n_] := 4 Sum[(n-i)(n-j) Boole[CoprimeQ[i, j]], {i, 1, n-1}, {j, 1, n-1}] + 4 n^2 - 4 n + 2;
%t A114146 Array[a, 38, 0] (* _Jean-François Alcover_, Sep 04 2018, after _Max Alekseyev_ in A114043 *)
%o A114146 (Python)
%o A114146 from sympy import totient
%o A114146 def A114146(n): return 1 if n == 0 else 8*n**2-12*n+6 + 4*sum(totient(i)*(n-i)*(2*n-i) for i in range(2,n)) # _Chai Wah Wu_, Aug 15 2021
%Y A114146 Cf. A114043, A114531.
%Y A114146 The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - _N. J. A. Sloane_, Feb 04 2020
%K A114146 nonn
%O A114146 0,2
%A A114146 _N. J. A. Sloane_, Feb 22 2006
%E A114146 Definition corrected by _Max Alekseyev_, Oct 23 2008
%E A114146 a(0)=1 prepended by _Max Alekseyev_, Jan 23 2015