The day of the week (i.e. Tuesday, ... etc) will always be correct, so it is irrelevant to your problem.
Assuming non leap year, you can build a table of 12 rows (1 per month) containing the number of days in this month minus 31.
- Jan 0
- Feb -3
- Mar 0
- Apr -1
- May 0
- Jun -1
- Jul 0
- Aug 0
- Sep -1
- Oct 0
- Nov -1
- Dec 0
You can build a table of the displayed date for every 1st of the month, by adding to the day of the previous month the related number in this list. If the number is negative or equal to zero, add 31 to the figure.
i.e. from the 1st Dec 09 (date at which the clock is displaying 23), you can go to the 1st Jan 10.
You look at this table and find the figure next to Dec, it is 0.
Add 0 to 23 and you know that on the 1st Jan 10, the clock will be displaying 23.
From the 1st Jan 09, you know that the date which will be displayed on the 1st Feb 10 is 23.
From the 1st Feb 10, you can compute the value for the 01 Mar 10, it is 23 + (-3) = 20.
... etc
So, now, at every start of month where you get a value of 1 in this table, you know that the dates in this month will be correct.
If you have to include leap year, you need a second table with the values for a leap year or make an exception for February.
If you want to use this computation for previous dates, substract the figure from the table and when the number you obtain is over 31, just substract 31 to get the day number.
Using these tables and taking in account leap years.
The last past date at which the clock was correct was the 30 September 08 (it was correct between the 01-Jul-08 and the 30-Sep-08)
The next date at which it will be correct will be the: 01-Oct-17 and it will still be correct on the 30-Nov-17.