This is another one in the Date/Time extension series. Bugs #63391 and #61599 both deal with PHP getting the Day of Week wrong in years before 1600. Technically I did not write the patch for this contribution, but I did add tests, verified it and merged it to all the four branches (PHP 5.4, 5.5, 5.6 and master).
However, it does seem that I introduced the bug in the first place. When writing the new date/time support about 7 years ago I was looking for an algorithm that would tell me the day of the week for any given (Gregorian calendar) date. Wikipedia has quite a good article on it. The article outlines the calculation of the century number. For the Gregorian calendar, that's quite straight forwards:
6 - (j % 4) * 2. For the Julian calendar it's not very difficult either. Although PHP uses the proleptic Gregorian calendar that I wrote about before, I mistakenly had used a formula that combined the Julian and Gregorian calendar calculations. This then resulted in wrong calculations before the year 1600. This is now corrected and ready for inclusion into PHP 5.4.24, 5.5.7, and later versions.