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

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, 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, 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

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..20000

Rishi Advani, Formula for sequence on Mathematics Stack Exchange

Formula

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.)

a(n) = a(-n) for all n in Z. - Seiichi Manyama, Aug 18 2020

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

Example

From Seiichi Manyama, Aug 18 2020: (Start)
Illustration of initial terms:
   0 =  0 (empty sum).
   1 =  1.
   2 =  1 - 2 + 3.
   3 =  1 + 2.
   4 = -1 + 2 + 3.
   5 =  1 + 2 + 3 + 4 - 5.
   6 =  1 + 2 + 3.
   7 =  1 + 2 + 3 - 4 + 5.
   8 = -1 + 2 + 3 + 4.
   9 =  1 + 2 - 3 + 4 + 5.
  10 =  1 + 2 + 3 + 4.
... (End)

Maple

b:= proc(n, i) option remember;
      (n=0 and i=0) or n<=i*(i+1)/2 and (b(abs(n-i), i-1) or b(n+i, i-1))
    end:
a:= proc(n) local k;
      for k from 0 while not b(n, k) do od; k
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Oct 19 2011

Mathematica

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]);
a[n_] := Module[{k}, For[k = 0, !b[n, k], k++]; k];
a /@ Range[0, 100] (* Jean-François Alcover, Nov 15 2020, after Alois P. Heinz *)

Crossrefs

Cf. A000217, A197702, A231015, A327467.

Sequence in context: A346388 A128151 A071166 * A130727 A155515 A023605

Adjacent sequences: A140355 A140356 A140357 * A140359 A140360 A140361

Keyword

nonn,look

Author

John W. Layman, Jun 23 2008

Extensions

a(0)=3 prepended by Seiichi Manyama, Aug 17 2020

Edited and a(0)=0 from Alois P. Heinz, Aug 18 2020

Status

approved