Task[edit]
Solve the "Impossible Puzzle":


X and Y are two different whole numbers greater than 1. Their sum is no greater than 100, and Y is greater than X. S and P are two mathematicians (and consequently perfect logicians); S knows the sum X+Y and P knows the product X*Y. Both S and P know all the information in this paragraph.
The following conversation occurs:

 S says "P does not know X and Y."
 P says "Now I know X and Y."
 S says "Now I also know X and Y!"
What are X and Y?


Guidance
It can be hard to wrap one's head around what the three lines of dialog between S (the "sum guy") and P (the "product guy") convey about the values of X and Y.

So for your convenience, here's a break-down:





 Quote

 Implied fact


 1)

 S says "P does not know X and Y."

 For every possible sum decomposition of the number X+Y, the product has in turn more than one product decomposition.


 2)

 P says "Now I know X and Y."

 The number X*Y has only one product decomposition for which fact 1 is true.


 3)

 S says "Now I also know X and Y."

 The number X+Y has only one sum decomposition for which fact 2 is true.

Terminology:

 "sum decomposition" of a number = Any pair of positive integers (A, B) so that A+B equals the number. Here, with the additional constraint 2 ≤ A < B.
 "product decomposition" of a number = Any pair of positive integers (A, B) so that A*B equals the number. Here, with the additional constraint 2 ≤ A < B.


Your program can solve the puzzle by considering all possible pairs (X, Y) in the range 2 ≤ X < Y ≤ 98, and then successively eliminating candidates based on the three facts. It turns out only one solution remains!

See the Python example for an implementation that uses this approach with a few optimizations.

See also
   Wikipedia:   Sum and Product Puzzle

function print_count(t)
    local cnt = 0
    for k,v in pairs(t) do
        cnt = cnt + 1
    end
    print(cnt .. ' candidates')
end
 
function make_pair(a,b)
    local t = {}
    table.insert(t, a) -- 1
    table.insert(t, b) -- 2
    return t
end
 
function setup()
    local candidates = {}
    for x = 2, 98 do
        for y = x + 1, 98 do
            if x + y <= 100 then
                local p = make_pair(x, y)
                table.insert(candidates, p)
            end
        end
    end
    return candidates
end
 
function remove_by_sum(candidates, sum)
    for k,v in pairs(candidates) do
        local s = v[1] + v[2]
        if s == sum then
            table.remove(candidates, k)
        end
    end
end
 
function remove_by_prod(candidates, prod)
    for k,v in pairs(candidates) do
        local p = v[1] * v[2]
        if p == prod then
            table.remove(candidates, k)
        end
    end
end
 
function statement1(candidates)
    local unique = {}
    for k,v in pairs(candidates) do
        local prod = v[1] * v[2]
        if unique[prod] ~= nil then
            unique[prod] = unique[prod] + 1
        else
            unique[prod] = 1
        end
    end
 
    local done
    repeat
        done = true
        for k,v in pairs(candidates) do
            local prod = v[1] * v[2]
            if unique[prod] == 1 then
                local sum = v[1] + v[2]
                remove_by_sum(candidates, sum)
                done = false
                break
            end
        end
    until done
end
 
function statement2(candidates)
    local unique = {}
    for k,v in pairs(candidates) do
        local prod = v[1] * v[2]
        if unique[prod] ~= nil then
            unique[prod] = unique[prod] + 1
        else
            unique[prod] = 1
        end
    end
 
    local done
    repeat
        done = true
        for k,v in pairs(candidates) do
            local prod = v[1] * v[2]
            if unique[prod] > 1 then
                remove_by_prod(candidates, prod)
                done = false
                break
            end
        end
    until done
end
 
function statement3(candidates)
    local unique = {}
    for k,v in pairs(candidates) do
        local sum = v[1] + v[2]
        if unique[sum] ~= nil then
            unique[sum] = unique[sum] + 1
        else
            unique[sum] = 1
        end
    end
 
    local done
    repeat
        done = true
        for k,v in pairs(candidates) do
            local sum = v[1] + v[2]
            if unique[sum] > 1 then
                remove_by_sum(candidates, sum)
                done = false
                break
            end
        end
    until done
end
 
function main()
    local candidates = setup()
    print_count(candidates)
 
    statement1(candidates)
    print_count(candidates)
 
    statement2(candidates)
    print_count(candidates)
 
    statement3(candidates)
    print_count(candidates)
 
    for k,v in pairs(candidates) do
        local sum = v[1] + v[2]
        local prod = v[1] * v[2]
        print("a=" .. v[1] .. ", b=" .. v[2] .. "; S=" .. sum .. ", P=" .. prod)
    end
end
 
main()