Inverse Doomsday

[Thomas Klemm]

Recently I came across an old concert poster that took place on Friday, September 4th and wondered what year this was.
After a few tries with the DOW (day of week) function I figured it out pretty quickly.
But then I wondered how to solve this problem without brute force.

In this specific case, the closest Doomsday is September 5th (i.e. 9/5) which is a Saturday and therefore the anchor day of this year which is coded as 6.

For the year's last two digits \(y\) in a certain century, its anchor day can be calculated using the following formula:

\(d=\left(k + y+\left\lfloor {\frac {y}{4}}\right\rfloor \right){\bmod {7}}\)

The constant \(k\) depends on the century:
\(1900–1999\): \(k = 3\)
\(2000–2099\): \(k = 2\)

We therefore essentially want to invert the following function:

\(m=\left(y+\left\lfloor {\frac {y}{4}}\right\rfloor \right){\bmod {7}}\)

This function is periodic with a period of \(28 = 4 \times 7\).
We will therefore limit ourselves to \(y \in \{0, 1, 2, \cdots, 27\}\) for the time being.

The following table can be viewed as a torus.
It indicates for each row which \(y\) are mapped to the same value \(m\):

\(
\begin{array}{|r:r|r|r|r|}
\hline
& 0 & 1 & 2 & 3 \\\hline
0 & 0 & 17 & 6 & 23 \\\hline
1 & 12 & 1 & 18 & 7 \\\hline
2 & 24 & 13 & 2 & 19 \\\hline
3 & 8 & 25 & 14 & 3 \\\hline
4 & 20 & 9 & 26 & 15 \\\hline
5 & 4 & 21 & 10 & 27 \\\hline
6 & 16 & 5 & 22 & 11 \\\hline
\end{array}
\)

A row is skipped if the year is a leap year, which means it is divisible by \(4\).

In my case (i.e. Friday, September 4th in the 20th century) we are looking for values \(y\) that map to \(3 = 6 - 3\).
This means that we consider the following line:

\(
\begin{array}{|r:r|r|r|r|}
\hline
3 & 8 & 25 & 14 & 3 \\\hline
\end{array}
\)

Or then in correct order: \(\{3, 8, 14, 25\}\).
Once the years are sorted in each row you may notice a common pattern:
The differences cycle through the following values: \(\{5, 6, 11, 6\}\)
However, they will start with different values.

This program is for the HP-42S:

Code:

00 { 59-Byte Prgm }
01▸LBL "DD↑-1"
02 GTO IND ST X
03▸LBL 00
04 GTO 09
05▸LBL 01
06 GTO 07
07▸LBL 02
08 GTO 10
09▸LBL 03
10 GTO 08
11▸LBL 04
12 9
13 GTO 07
14▸LBL 05
15 4
16 GTO 09
17▸LBL 06
18 5
19▸LBL 07
20 STOP
21 6
22 +
23▸LBL 08
24 STOP
25 5
26 +
27▸LBL 09
28 STOP
29 6
30 +
31▸LBL 10
32 STOP
33 11
34 +
35 GTO 07
36 END

Example

3 XEQ "DD↑-1"

3

R/S

8

R/S

14

R/S

25

R/S

31

\(\cdots\)

81

R/S

87

R/S

92

R/S

98


Can you come up with a simpler solution?

PS: Due to further constraints, I am convinced that the concert took place in 1992.

References

• Doomsday Rule
  

[Allen]

This is a very clever implementation of the rotation of the \( f = [5,6,11,6] \) shifts and initial states.

In looking for a recursion, it occurs to me that \( a_n = a_{n-1} + (7* f_{n-2} \mod 12 ) \) , but it is less clear if it could be useful in reducing the program size, already very readable and comprehensible using the IND and GTO to set \(a_0 \) accordingly. Very elegant.

[lrdheat]

Does the “k” work for the year 2000? No leap year that year.

[lrdheat]

Sorry about that…2000 was a 00 year that had a leap day!

[RPNerd]

(08-09-2024 03:28 AM)lrdheat Wrote:  Does the “k” work for the year 2000? No leap year that year.

2000 was a leap year.

Years that are multiples of 4 but not multiples of 100 unless they are multiples of 400 are leap years.

1904 -> leap year
1900 -> not a leap year
2000 -> leap year

[lrdheat]

…actually, most years ending with 00 are not leap years. Did this impact your calculations for this century, the year 2000 in particular?

[Thomas Klemm]

(08-09-2024 03:28 AM)lrdheat Wrote:  Does the “k” work for the year 2000?

For the anchor day \(k\) of a century consult the table in Finding a year's anchor day:

\(
\begin{array}{|l|l|l|}
\hline
\textbf{Century} & \textbf{Anchor day} & \textbf{Index (day of week)} \\\hline
1600–1699 & \text{Tuesday} & 2 \\\hline
1700–1799 & \text{Sunday} & 0 \\\hline
1800–1899 & \text{Friday} & 5 \\\hline
1900–1999 & \text{Wednesday} & 3 \\\hline
2000–2099 & \text{Tuesday} & 2 \\\hline
2100–2199 & \text{Sunday} & 0 \\\hline
2200–2299 & \text{Friday} & 5 \\\hline
\end{array}
\)

For the year \(2000\) use \(k=2\).

---

Just to make it clear: the inversion here is only related to the year's last two digits \(y\) within a certain century.

[Thomas Klemm]

Here's another example: Today is 2024-08-09 which is a Friday.
In which years of this century was September 9th also a Friday?

The anchor day for the year's last two digits \(y=24\) is \(2=\left(24 + 6\right) \mod 7\).

2 XEQ "DD↑-1"

2
13
19
24

Therefore in:

• 2002
• 2013
• 2019
• 2024
  

[Albert Chan]

(08-09-2024 02:01 PM)Thomas Klemm Wrote:  Here's another example: Today is 2024-08-09 which is a Friday.
In which years of this century was September 9th also a Friday?

365 MOD 7 ≡ 1. We just need to account for leap year.

Code:

Weekday  August 9, 20??
5        24  19  13      02
4            18  12  07  01
3        23  17      06  00
2        22  16  11  05   
1        21      10  04  
0        20  15  09      
6            14  08  03

Brute force is not that hard. (blanks are due to leap year)
From first row, we have Years with August 9 = Friday

[Thomas Klemm]

(08-09-2024 03:34 PM)Albert Chan Wrote:  Brute force is not that hard.

(08-06-2024 05:00 PM)Thomas Klemm Wrote:  But then I wondered how to solve this problem without brute force.

You may have missed it, but this is the whole point of this post.

Otherwise we could have just used the following program for the HP-42S to calculate \(\left(y+\left\lfloor {\frac {y}{4}}\right\rfloor \right){\bmod {7}}\):

Code:

00 { 25-Byte Prgm }
01 0
02▸LBL 00
03 STO ST Z
04 4
05 ÷
06 IP
07 RCL+ ST Z
08 7
09 MOD
10 X=Y?
11 VIEW ST Z
12 X<> ST Z
13 1
14 +
15 GTO 00
16 END

Make sure to use PROFF and SF 21.

Example

2 R/S

ST Z=2

R/S

ST Z=13

R/S

ST Z=19

R/S

ST Z=24

[Albert Chan]

Hi, Thomas Klemm

Sorry I missed that. Here is non brute force way

2024-08-09 is Friday:

y + floor(y/4) ≡ 24 + 6 ≡ 30 ≡ 2 (mod 7)

For other Fridays, we search other 2 digits y that satisfied above.
Let y = 4k+z, where z = 0 to 3, and all modulo calculations are (mod 7)

y + floor(y/4) ≡ (4k+z) + k ≡ 5k+z ≡ z-2k ≡ 2      --> z ≡ 2*(k+1)

k ≡ 0 --> z ≡ 2
k ≡ 1 --> z ≡ 4, no solution
k ≡ 2 --> z ≡ 6, no solution
k ≡ 3 --> z ≡ 8 ≡ 1
k ≡ 4 --> z ≡ 3
k ≡ 5 --> z ≡ 5, no solution
k ≡ 6 --> z ≡ 7 ≡ 0

y = 4k + z, we have 2 digits y full solutions:

02, 13, 19, 24
30, 41, 47, 52
58, 69, 75, 80
86, 97

[Albert Chan]

We can also do smarter brute-force.
7 / (1 + 1/4) = 5.6. Instead of trying 1 year at a time, we can jump ahead

lua> f = fn'y: (y+floor(y/4)) % 7'
lua> f(24)
2
lua> f(24-5)
2
lua> f(19-5)
3
lua> f(19-6)
2
lua> f(13-5)
3
lua> f(13-6)
1
lua> f(7-5)
2

f(y) has period of 4*7 = 28 --> f(y)=value has 1/7 = 4/28 solutions

f(y)=2 --> y ≡ {24, 24-5, 19-6, 13-11} ≡ {24, 19, 13, 02} (mod 28)

[Thomas Klemm]

(08-10-2024 12:51 PM)Albert Chan Wrote:  f(y)=2 --> y ≡ {24, 24-5, 19-6, 13-11} ≡ {24, 19, 13, 02} (mod 28)

Compare this to the table in my initial post:

(08-06-2024 05:00 PM)Thomas Klemm Wrote:  \(
\begin{array}{|r:r|r|r|r|}
\hline
2 & 24 & 13 & 2 & 19 \\\hline
\end{array}
\)

And then a bit later:

(08-06-2024 05:00 PM)Thomas Klemm Wrote:  Once the years are sorted in each row you may notice a common pattern:
The differences cycle through the following values: \(\{5, 6, 11, 6\}\)
However, they will start with different values.

(08-10-2024 02:21 AM)Albert Chan Wrote:  Sorry I missed that.

Do you even read the posts before responding?

[Albert Chan]

Hi, Thomas Klemm

Yes, your post and mine are equivalent, thus same answer.
But, intermediate calculations are very different.
Your quote of mine, f(y)=2, is based on "smart" trial and error, not a lookup table.

Yes, I read your posts. I just missed you really don't want brute force answer.
To compensate for the error, I did provide non brute-force solution too (post #11)

But, y with period of 28, brute force is probably simpler than the smart way.
All we need is make a table with a jump for leap year, very little math involved.

Start with 2024-09-04 is Wednesday (only 1 DOW calculation needed), we have:

Code:

Weekday          September 4th, ????

3       2024    2019    2013            2002    ...
2               2018    2012    2007    2001    
1       2023    2017            2006    2000
0       2022    2016    2011    2005         
6       2021            2010    2004    1999
5       2020    2015    2009            1998
4               2014    2008    2003    1997

If we continued on, pattern of "leap" blanks repeat itself --> y has period of 28

OP, Friday, September 4th, Year = 2020 - 28 = 1992 (based on your other constraints)

[Martin Hepperle]

(08-09-2024 02:01 PM)Thomas Klemm Wrote:  Here's another example: Today is 2024-08-09 which is a Friday.
In which years of this century was September 9th also a Friday?

[...]

Therefore in:

• 2002
• 2013
• 2019
• 2024
  

The given month confused me: September --> August :-)

(In my life, September 9th, 2019 was a Monday.)

Martin