//
// Using FutureBasic 7.0.34, July 2025 R.W.
//
// Sum to 100 solutions
//
// Using 123456789 digits so the resulting
// mathematical expression adds up to a 100
// using "-" and "+" operators only
//

Int maxPerm, allDigits

maxPerm = 13122    //2 * 3 ^ 8  max permutation
allDigits = 123456789

Int sum(13121)
CFStringRef equation

// Get sum of one of the permutation
// on entry:    n = permutation number
// on exit:    ret = sum
//            modifies global var equation

local fn doEval( n as UInt32) as Int

  CFStringRef evalstr
  boolean doAdd = _False
  Int ret, cPtr, x, sw

  evalstr = @"9"
  ret = 0: cPtr = 9
  doAdd = (n => (maxPerm / 2))

  for x = 8 to 1 step -1 //do 87654321
    sw = n % 3
    if sw == 0 then cPtr += x * 10^(1 + fix(log(cPtr + 0.5) / log(10)))
    if sw == 1
      ret += cPtr
      cPtr = x
      evalstr = concat (@" + ",evalstr)
    end if
    if sw == 2
      ret -= cPtr
      cPtr = x
      evalstr = concat (@" - ",evalstr)
    end if
    evalstr = concat(mid(str(x),1),evalstr)
    n = fix(n/3)
  next x

  if doAdd == 0
    evalstr = concat(@" - ", evalstr)
    ret -= cPtr
  else
    ret += cPtr
  end if

  evalstr = concat(str(ret),@" = ",evalstr)
  equation = evalstr
end fn = ret

window 1,@"Sum to 100"


Int x, y, curr

// calculate all solutions 2 * 3 ^ 8
//
for x = maxPerm-1 to 0 step -1
  equation = @""
  curr = fn DoEval(x)
  sum(x) = curr
  if curr = 100 then print equation
next x
print

// sum with most solution

Int i,j,sav,most,tot

for x = 0 to maxPerm-1
  sav = 0
  for y = 0 to maxPerm-1
    if sum(y) == sum(x) then sav++
  next y
  if sav > tot then tot = sav: most = sum(x)
next x
print most;" has most solutions occurring ";tot;" times."

// lowest non negative with no solution

boolean sk = _False
for x = 0 to allDigits-1
  for y = 0 to maxPerm-1
    if sum(y) == x then sk = _True: y = maxPerm
  next y
  if !sk
    print "The first non negative number that has no solution is ";x
    exit for
  else
    sk = _False
  end if
next x

// ten highest with solution

print
print "The ten highest numbers that can be expressed:"

most = 0
for x = 1 to 10
  for y = 0 to maxPerm-1
    if sum(y) > sum(most) then most = y
  next y
  fn doEval(most)
  print equation
  sum(most) = 0
next x

HandleEvents