cp's OEIS Frontend

A140358 Smallest nonnegative integer k such that n = +-1+-2+-...+-k for some choice of +'s and -'s.

%I A140358 #62 Mar 18 2021 08:34:47
%S A140358 0,1,3,2,3,5,3,5,4,5,4,5,7,5,7,5,7,6,7,6,7,6,7,9,7,9,7,9,7,9,8,9,8,9,
%T A140358 8,9,8,9,11,9,11,9,11,9,11,9,11,10,11,10,11,10,11,10,11,10,11,13,11,
%U A140358 13,11,13,11,13,11,13,11,13,12,13,12,13,12,13,12,13,12,13,12,13,15,13,15,13
%N A140358 Smallest nonnegative integer k such that n = +-1+-2+-...+-k for some choice of +'s and -'s.
%H A140358 Alois P. Heinz, <a href="/A140358/b140358.txt">Table of n, a(n) for n = 0..20000</a>
%H A140358 Rishi Advani, <a href="https://math.stackexchange.com/a/3998466/134481">Formula for sequence on Mathematics Stack Exchange</a>
%F A140358 Conjecture when n is greater than 0. Choose k so that t(k)<=n<t(k+1) where t(n) is the n-th triangular number t(n)=n(n+1)/2. If n=t(k), a(n)=k, otherwise if k is odd then a(n)=k+2 if n-t(k) is odd, a(n)=k+1 if n-t(k) is even, else if k is even than a(n)=k+1 if n-t(k) is odd, a(n)=k+3 if n-t(k) is even. (This has been verified for n up to 100.)
%F A140358 a(n) = a(-n) for all n in Z. - _Seiichi Manyama_, Aug 18 2020
%F A140358 Let k be the least integer such that t(k) >= n. If t(k) and n have the same parity then a(n) = k. Otherwise a(n) is equal to the least odd integer greater than k. - _Rishi Advani_, Jan 24 2021
%e A140358 From _Seiichi Manyama_, Aug 18 2020: (Start)
%e A140358 Illustration of initial terms:
%e A140358    0 =  0 (empty sum).
%e A140358    1 =  1.
%e A140358    2 =  1 - 2 + 3.
%e A140358    3 =  1 + 2.
%e A140358    4 = -1 + 2 + 3.
%e A140358    5 =  1 + 2 + 3 + 4 - 5.
%e A140358    6 =  1 + 2 + 3.
%e A140358    7 =  1 + 2 + 3 - 4 + 5.
%e A140358    8 = -1 + 2 + 3 + 4.
%e A140358    9 =  1 + 2 - 3 + 4 + 5.
%e A140358   10 =  1 + 2 + 3 + 4.
%e A140358 ... (End)
%p A140358 b:= proc(n,i) option remember;
%p A140358       (n=0 and i=0) or n<=i*(i+1)/2 and (b(abs(n-i), i-1) or b(n+i, i-1))
%p A140358     end:
%p A140358 a:= proc(n) local k;
%p A140358       for k from 0 while not b(n,k) do od; k
%p A140358     end:
%p A140358 seq(a(n), n=0..100);  # _Alois P. Heinz_, Oct 19 2011
%t A140358 b[n_, i_] := b[n, i] = (n==0 && i==0) || Abs[n] <= i(i+1)/2 && (b[n-i, i-1] || b[n+i, i-1]);
%t A140358 a[n_] := Module[{k}, For[k = 0, !b[n, k], k++]; k];
%t A140358 a /@ Range[0, 100] (* _Jean-François Alcover_, Nov 15 2020, after _Alois P. Heinz_ *)
%Y A140358 Cf. A000217, A197702, A231015, A327467.
%K A140358 nonn,look
%O A140358 0,3
%A A140358 _John W. Layman_, Jun 23 2008
%E A140358 a(0)=3 prepended by _Seiichi Manyama_, Aug 17 2020
%E A140358 Edited and a(0)=0 from _Alois P. Heinz_, Aug 18 2020