Let's say I am one of the two men, and see 4. I know he either sees 6 or 9.
If he saw 9, he would know I see either 1 or 4.
If I saw 1, he knows I would know he saw either 9 or 12.
If he saw 12, we'd be out on the 1st day.
We're not, so he knows I know he doesn't see 12.
If I saw 1, I would now know he sees 9 and the towns are 10. We'd be out on the 2nd day.
We're not, so he knows I don't see 1.
If he saw 9, we would be out, because he would now know I see 4, and the towns would be 13. We would be out on the 3rd day.
We are still not out, so I know he doesn't see 9.
Therefore he must see 6. I tell the gaoler it's 10 towns and we're free on the 4th day.
I tried this thought process with me seeing 5 and 3, but I'm still out on the 4th day, not the 5th.
If they get out on the 4th day, it's always 10 towns.