Notes on A141000
----------------
Date: Sat, 12 Jul 2008 14:36:23 -0400
From: David Applegate <david(AT)research.att.com>

Here's a proof of Hess & Fisher's result. 

Define the "bandwidth" m(x,i) be the smallest integer m
such that 1..i can add up to x using prefix sums <= m,
with m(x,i) = \infty if 1..i cannot add up to x.

In other words, m(x,i) is the smallest number m such that there exists
signs s_j for j=1..i with
    sum_{j=1}^i s_j j = x,
and
    0 <= sum_{j=1}^k s_j j  <= m  for all 1 <= k <= i.

Clearly, 
   if i == 0 or 3 (mod 4) and x == 1 (mod 2) then m(x,i) == \infty,
and
   if i == 1 or 2 (mod 4) and x == 0 (mod 2) then m(x,i) == \infty,
and
   if x > i(i+1)/2 then m(x,i) == \infty.

Also
    m(x,i) >= x,
and 
    if x < i, m(x,i) >= x+i 
since if x<i, s_i must be -1.

Lemma:  These bounds are nearly tight.  That is,
assuming 
    i >= 21,
    x <= i(i+1)/2 - 6
    x == i(i+1)/2 mod 2
then
    if x >= i, m(x,i) = x,
    if x < i,  m(x,i) = x+i.

Proof: By induction.  The base case for i == 21 is checked by
enumeration.  Suppose the lemma is true for i-1.  Then if x < i,
   m(x,i) <= max(m(x+i,i-1), x) <= x+i (since x+i >= i-1)
and if x >= i,
   m(x,i) <= max(m(x-i,i-1), x) <= x   (since m(x-i,i-1) <= x-i + i-1 = x-1)

Corollary: for i >= 22, i is in A141000 iff i == 0 or 1 (mod 4).
Proof:  From the Lemma, m(i,i) == i if i == 0 or 1 (mod 4), and
 m(i,i) == \infty if i == 2 or 3 (mod 4).

----------------------------------------------------------------

Here is some tcl code to compute m, etc.:

proc m {x i} {
  global mc
  set v [expr {$i * ($i+1) / 2}]
  if {$x % 2 != $v % 2} {return -1}
  if {$x > $v} {return -1}
  if {$x == 0 && $i == 0} {return 0}
  if {[info exists mc([list $x $i])]} {
    return $mc([list $x $i])
  }
  set v1 [m [expr {$x + $i}] [expr {$i - 1}] ]
  if {$x >= $i} {
    set v2 [m [expr {$x - $i}] [expr {$i - 1}] ]
    if {$v2 != -1} {
      if {$x > $v2} {set v2 $x}
      if {$v1 == -1 || $v2 < $v1} {
        set v1 $v2
      }
    }
  }
  set mv([list $x $i]) $v1
  return $v1
}
proc mg {x i} {
   global notgreedy
   set v $x
   while {$i > 0} {
      if {$x > $v} {set v $x}
      if {$x >= $i && ![info exists notgreedy([list $x $i])]} {
         incr x -$i    
      } else {
         incr x $i
      }
      incr i -1
  }
  if {$x == 0} {
    return $v
  } else { 
    return -1
  }
}
proc build_notgreedy {{ilim 21}} {
   global notgreedy
   for {set i 1} {$i <= $ilim} {incr i} {
      puts -nonewline "$i..."
      flush stdout
      set out []
      for {set x 0} {$x <= $i * ($i+1) / 2} {incr x} {
         set v [m $x $i]
         set vg [mg $x $i]
         if {$vg != $v} {
            set notgreedy([list $x $i]) 1
            lappend out $x
            set vg [mg $x $i]
            if {$vg != $v} {
               puts "setting notgreedy didn't help for $x $i ($v != $vg)"
            }
         }
      }
      puts "done ([join $out ,])"
   }
}