*Post by James Waldby**Post by Nick**Post by James Waldby*...

*Post by Peter Percival*Consider the digits 123456789 in that order. Distribute addition and

subtraction signs among them so that the sum 100 results.

12 + 3 - 4 + 5 + 67 + 8 + 9

is one solution, there are others.

This problem is in Knuth's taocp vol 4A [...] He asks [...]

[...] for the least +ve integer *not* representable

in this way. See Ex 111 on page 319. The soln is on page

702 where the problem is attributed to Dudeney in 1899.

*Post by Peter Percival*Suppose it's m. And I ask -

What is the algorithm that works generally for sums

m, m+1, m+2, ..., 123456789? I.e., a partition is

Omit m.

I don't know of an efficient general algorithm for this, but maybe

a divide-and-conquer method could reduce the asymptotic run time

somewhat compared to the exponential time that enumerating all

combinations requires. A time savings comes from being able to

process parts in linear order or via tree search or via a heap.

Dividing up the problem is easy for combinations that have a plus

or minus operator at the divide point, but is clumsy when numbers

cross that point. One approach is to store each segment value in

two parts, eg for a left half store the instance's value up to the

last operator in it, and store the last (not-necessarily-complete)

number value as well.

I don't understand this comment. For me it seems we have the set of

digits plus a choice of three operators (+,-,string concatenation). A

prefix operator only has 2 choices. So total choices are in python

2*(3**8). So we would essentially have a ternary search tree. You seem

to have recognised this in the python program.

Yes, one approach is to use a ternary search tree. My Python program

didn't generate the tree per se, but instead decoded numbers into

ternary digits, representing subtraction, concatenation, and addition.

Generating a tree more explicitly might allow use of higher-power

search techniques, like alpha-beta pruning.

Suppose the digit string is a little larger, eg 50 instead of 9.

Generating and/or searching a tree may become impractical. A

divide-and-conquer method should develop lists of possible values

for sections of the digit string and allow combining those values

efficiently. For an oversimplified example, if there are n = m+m

digits and if our target is t and if left and right lists have

sorted values, we process the left list in order and the right list

in reverse order at the same time, advancing the left list pointer

when left+right < t, and reducing the right list pointer when

t < left+right, thus taking time O(m) + O(G) where O(G) is time to

generate a list over m characters. But along with individual values

in the list, we presumably need number-part values, and in general

don't have useful limits on their lengths.

I'm still not sure I'm getting you but it is easy to see how this type

of idea could develop a recursive program. Basically build a set of all

solutions for n digits and the add digit n+1. There is the added

complexity you need to remember all potential last terms in the n case

so you can append another digit. Possibly it has slightly lower

complexity that ternary exponential. I was going to test it then it

occurred to me that there are only 9 possibly ten digits.

Anyway FWIW please excuse my Python. I'm more C#, Java, VBA orientated

#main function to solve the problem

def find_lowest_sum_not_ok():

digits=9

set_of_sums = find_all_sums_from_digits(digits)

print( "Potential Complexity guess (ordinality({(sums,last_term)})="

+ str( len(set_of_sums)))

res = get_first(set_of_sums)

print( "Lowest Solution " + str(res ))

return res

#finds the firrst gap in the set of posible sum tuples

# {(sum,last term)}

def get_first(nums):

last = 0

# unpack tuples (sum,last item) to give a sorted list of sums > 0

sorted_sums_only = sorted({ x[0] for x in nums if x[0] > 0 })

for key in sorted_sums_only:

if key - last != 1:

return (last + 1)

last = key

#returns a set of tuples containing potential sums and the

# last term in the sum.

#max_digit == number of digits

def find_all_sums_from_digits(digits) :

res = set()

#base case

if digits==1:

res.add((-1,-1))

res.add((1,1))

return res

#recursive step

for (t,l) in find_all_sums_from_digits(digits-1):

# +

res.add((t + digits, digits))

# -

res.add((t - digits, -digits))

# concatenate digits

if l>0:

e = l * 10 + digits

else:

e = l * 10 - digits

res.add((t - l + e, e))

return res

*Post by James Waldby*[snip: interesting comments on Martin Fowler re Knuth]

*Post by Nick*If you too love Knuth I would recommend

<https://www.amazon.co.uk/Artificial-Intelligence-Approach-Stuart-Russell/dp/1292024208>

Very much in the spirit of Knuth and it describes practical ways to

solve this sort of problem. This type of problem would normally involve

applying a few rules to identify potential solution areas and then

applying search trees. A simple type of rule might be that a solution

cannot more that 5 digits in a number.

When the target has lots of digits, a rule like that may be

difficult to prove correct.

Not really it is easy to see it must be less than half the digits.