While playing around with 150 relays, I built a full adder.
I managed to get it down to 9 relays (closing type) and some diodes.
Here is the schematic:
Please note that relay 6 is just a drawing error, due to the diode near the closer of relay 8 it's unnecessary.
The Resistors are all 1k, which seems to be an appropriate value for my 24V/2.7kOhms relays, but maybe you need to change it depending on your relays.
The diode near the sum output might be useless, but I need more time to test it.
This all is not tested yet, it's just an idea I wanted to share.