login
Number of nontriangular numbers <= n.
14

%I #56 Feb 04 2024 09:30:31

%S 0,0,1,1,2,3,3,4,5,6,6,7,8,9,10,10,11,12,13,14,15,15,16,17,18,19,20,

%T 21,21,22,23,24,25,26,27,28,28,29,30,31,32,33,34,35,36,36,37,38,39,40,

%U 41,42,43,44,45,45,46,47,48,49,50,51,52,53,54,55,55,56,57,58,59,60,61,62

%N Number of nontriangular numbers <= n.

%C An alternative description: the sequence of nonnegative integers with the triangular numbers repeated.

%C a(t(n)) = t(n+1), where t(n)=A000217(n)=n(n+1)/2, the n-th triangular number. For n>=1, a(n)=a(n-1) if and only if n is a triangular number; otherwise, a(n)=1+a(n-1).

%H Reinhard Zumkeller, <a href="/A083920/b083920.txt">Table of n, a(n) for n = 0..10000</a>

%H R. K. Guy, <a href="http://dx.doi.org/10.1016/S0304-0208(08)73500-X">Sets of integers whose subsets have distinct sums</a>, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982. See Table 1, column (4).

%F a(n) = n-floor((x-1)/2) = n-A003056(n), where x = sqrt(8*n+1).

%F A005318(n+1) = 2*A005318(n)-A205744(n), A205744(n) = A005318(a(n)), a(n) = n - A002024(n). - _N. J. A. Sloane_, Feb 11 2012

%F G.f.: 1/(1 - x)^2 - (1/(1 - x))*Product_{k>=1} (1 - x^(2*k))/(1 - x^(2*k-1)). - _Ilya Gutkovskiy_, May 30 2017

%F a(n) = n - floor(sqrt(2*n + 1) - 1/2). - _Ridouane Oudra_, Jun 19 2019

%e a(7)=4 counts the nontriangular numbers, 2,4,5,7, that are <=7.

%t f[n_] := n - Floor[(Sqrt[8n + 1] - 1)/2]; Table[ f[n], {n, 0, 73}] (* _Robert G. Wilson v_, Oct 22 2005 *)

%t Accumulate[Table[If[OddQ[Sqrt[8n+1]],0,1],{n,0,120}]] (* _Harvey P. Dale_, Oct 14 2014 *)

%o (Haskell)

%o a083920 n = a083920_list !! n

%o a083920_list = scanl1 (+) $ map (1 -) a010054_list

%o -- _Reinhard Zumkeller_, Feb 12 2012

%o (PARI) a(n)=n-(sqrtint(8*n+1)-1)\2 \\ _Charles R Greathouse IV_, Sep 02 2015

%o (Magma) [n-Floor((Sqrt(8*n+1)-1)/2):n in [1..75]]; // _Marius A. Burtea_, Jun 19 2019

%Y Cf. A000217, A002024, A003056, A005318, A205744.

%Y Essentially partial sums of A023532.

%Y Number of nonzero terms in row n+1 of A342557.

%K nonn

%O 0,5

%A _Clark Kimberling_, May 08 2003

%E Added alternative definition and Guy reference. - _N. J. A. Sloane_, Feb 09 2012