A lower bound for a constant in Shallit's conjecture