If I have to do it with logic gates, I would use a pll (4046) with a 4x divider and run the signal from the pll through a 1:5 divider.
So a 5khz signal into the pll will generate a 20khz output signal. Dividing that by 5 gives you a 4khz signal.
Overly complicated in my view.