Post Reply 
HHC 2018 Programming Contests
10-01-2018, 06:40 AM (This post was last modified: 10-01-2018 09:14 PM by Thomas Klemm.)
Post: #46
RE: HHC 2018 Programming Contests
For each period \(p \in {23, 28, 33}\) we're looking for values such that

\(\sin(2 \pi \tfrac{k}{p})\approx \pm 1\)

This leads to the following result:

\(
\begin{matrix}
p=23 :& k \in \{6, 17\} \\
p=28 :& k \in \{7, 21\} \\
p=33 :& k \in \{8, 25\}
\end{matrix}
\)

For each pair \((23, 28)\), \((23, 33)\) and \((28, 33)\) the "extrema dates" are calculated separately with the help of the Chinese remainder theorem which states that for numbers \(p\) and \(q\) that are coprime there's a ring isomorphism:

\(\mathbb{Z}_{p}\times\mathbb{Z}_{q}\cong\mathbb{Z}_{p\cdot q}\).

In the end the minimum of these three values is chosen.

\(\mathbb{Z}_{23}\times\mathbb{Z}_{28}\cong\mathbb{Z}_{644}\)

We're looking for a number \(n\) such that \((n \bmod 23, n \bmod 28) = (1, 0)\).
Clearly \(n\) must be a multiple of \(28\): \(n = 28 \cdot k\).
But then \(n \bmod 23 \equiv 5\cdot k\) and we can guess \(k=14\) since \(5 \cdot 14 = 70 = 1 + 3 \cdot 23 \equiv 1\ (\bmod 23)\).
Thus we end up with: \(n = 28 \cdot 14 = 392 \equiv 1\ (\bmod 23)\).

Similarly we can find a number \(m\) such that \((m \bmod 23, m \bmod 28) = (0, 1)\):
\(m = 23 \cdot 11 = 253 = 1 + 9 \cdot 28 \equiv 1\ (\mod 28)\)

Thus \((1, 0) \simeq 392\) and \((0, 1) \simeq 253\) form a basis in \(\mathbb{Z}_{23} \times \mathbb{Z}_{28}\).
For \(a, b \in \mathbb{N}\) we find that: \((a, b) \simeq a \cdot 392 + b \cdot 253\ (\bmod 644)\)

This leads to the following table:
\(
\begin{matrix}
(6, 7) &\simeq& 6 \cdot 392 &+& 7 \cdot 253 &=& 4123 &\equiv& 259\ (\bmod\ 644) \\
(6, 21) &\simeq& 6 \cdot 392 &+& 21 \cdot 253 &=& 7665 &\equiv& 581\ (\bmod\ 644) \\
(17, 7) &\simeq& 17 \cdot 392 &+& 7 \cdot 253 &=& 8435 &\equiv& 63\ (\bmod\ 644) \\
(17, 21) &\simeq& 17 \cdot 392 &+& 21 \cdot 253 &=& 11977 &\equiv& 385\ (\bmod\ 644)
\end{matrix}
\)

This explains the magic numbers in these lines of the program:
Code:
07 63               ; (17, 7)
11 259              ; (6, 7)
15 385              ; (17, 21)
19 581              ; (6, 21)

\(\mathbb{Z}_{23}\times\mathbb{Z}_{33}\cong\mathbb{Z}_{759}\)

As above we can find a basis using \((1, 0) \simeq 231\) and \((0, 1) \simeq 529\).

We end up with this table:
\(
\begin{matrix}
(6, 8) &\simeq& 6 \cdot 231 &+& 8 \cdot 529 &=& 5618 &\equiv& 305\ (\bmod\ 759) \\
(6, 25) &\simeq& 6 \cdot 231 &+& 25 \cdot 529 &=& 14611 &\equiv& 190\ (\bmod\ 759) \\
(17, 8) &\simeq& 17 \cdot 231 &+& 8 \cdot 529 &=& 8159 &\equiv& 569\ (\bmod\ 759) \\
(17, 25) &\simeq& 17 \cdot 231 &+& 25 \cdot 529 &=& 17152 &\equiv& 454\ (\bmod\ 759)
\end{matrix}
\)

These are magic numbers of the program:
Code:
29 190              ; (6, 25)
33 305              ; (6, 8)
37 454              ; (17, 25)
41 569              ; (17, 8)

\(\mathbb{Z}_{28}\times\mathbb{Z}_{33}\cong\mathbb{Z}_{924}\)

As above we can find a basis using \((1, 0) \simeq 561\) and \((0, 1) \simeq 364\).

We end up with this table:
\(
\begin{matrix}
(7, 8) &\simeq& 7 \cdot 561 &+& 8 \cdot 364 &=& 6839 &\equiv& 371\ (\bmod\ 924) \\
(7, 25) &\simeq& 7 \cdot 561 &+& 25 \cdot 364 &=& 13027 &\equiv& 91\ (\bmod\ 924) \\
(21, 8) &\simeq& 21 \cdot 561 &+& 8 \cdot 364 &=& 14693 &\equiv& 833\ (\bmod\ 924) \\
(21, 25) &\simeq& 21 \cdot 561 &+& 25 \cdot 364 &=& 20881 &\equiv& 553\ (\bmod\ 924)
\end{matrix}
\)

These are the magic numbers of the program:
Code:
55 91               ; (7, 25)
59 371              ; (7, 8)
63 553              ; (21, 25)
67 833              ; (21, 8)

Here's the program for the HP-41CX:
Code:
01▸LBL "NED"        ; birthday
02 DATE             ; today
03 DDAYS            ; n days difference
04 RCL X            ; n         n
05 644              ; = 23 × 28
06 MOD              ; u=n%644   n
07 63               ; (17, 7)
08 X>Y?             ; 63 > u ?
09 GTO 00           ; found next U
10 RDN              ; u         n
11 259              ; (6, 7)
12 X>Y?             ; 259 > u ?
13 GTO 00           ; found next U
14 RDN              ; u         n
15 385              ; (17, 21)
16 X>Y?             ; 385 > u ?
17 GTO 00           ; found next U
18 RDN              ; u         n
19 581              ; (6, 21)
20 X>Y?             ; 581 > u ?
21 GTO 00           ; found next U
22 RDN              ; u         n
23 707              ; = 644 + 63
24▸LBL 00           ; U         u       n
25 X<>Y             ; u         U       n
26 -                ; ∆u        n
27 RCL Y            ; n         ∆u      n
28 759              ; = 23 × 33
29 MOD              ; v=n%759   ∆u      n
30 190              ; (6, 25)
31 X>Y?             ; 190 > v ?
32 GTO 00           ; found next V
33 RDN              ; v         ∆u      n
34 305              ; (6, 8)
35 X>Y?             ; 305 > v ?
36 GTO 00           ; found next V
37 RDN              ; v         ∆u      n
38 454              ; (17, 25)
39 X>Y?             ; 454 > v ?
40 GTO 00           ; found next V
41 RDN              ; v         ∆u      n
42 569              ; (17, 8)
43 X>Y?             ; 569 > v ?
44 GTO 00           ; found next V
45 RDN              ; v         ∆u      n
46 949              ; = 759 + 190
47▸LBL 00           ; V         v       ∆u      n
48 X<>Y             ; v         V       ∆u      n
49 -                ; ∆v        ∆u      n       n
50 X<Y?             ; ∆v < ∆u ?
51 X<>Y             ; max       min     n       n
52 RDN              ; min       n       n
53 X<>Y             ; n         min     n
54 924              ; = 28 × 33
55 MOD              ; w=n%924   min     n
56 91               ; (7, 25)
57 X>Y?             ; 91 > w ?
58 GTO 00           ; found next W
59 RDN              ; w         min     n
60 371              ; (7, 8)
61 X>Y?             ; 371 > w ?
62 GTO 00           ; found next W
63 RDN              ; w         min     n
64 553              ; (21, 25)
65 X>Y?             ; 553 > w ?
66 GTO 00           ; found next W
67 RDN              ; w         min     n
68 833              ; (21, 8)
69 X>Y?             ; 833 > w ?
70 GTO 00           ; found next W
71 RDN              ; w         min     n
72 1015             ; = 924 + 91
73▸LBL 00           ; W         w       min     n
74 X<>Y             ; w         W       min     n
75 -                ; ∆w        min     n       n
76 X<Y?             ; ∆w < min ?
77 X<>Y             ; max       min
78 RDN              ; min       n       n
79 +                ; m = n + min
80 DATE             ; today     m       n       n
81 LASTX            ; min       today   m       n
82 DATE+            ; today+min m       n       n
83 "NED: "          ; show next extrema date
84 FIX 6            ;
85 ADATE            ;
86 AVIEW            ;
87 RDN              ; m         n
88 23               ; 23        m       n
89 XEQ 00           ; show 23
90 28               ; 28        m       n
91 XEQ 00           ; show 28
92 33               ; 33        m       n
93▸LBL 00           ; show p
94 FIX 0            ;
95 CLA              ; ""
96 ARCL X           ; "p"
97 ├": "            ; "p: "
98 RCL Y            ; m         p       m       n
99 X<>Y             ; p         m       m       n
100 /               ; m/p       m       n       n
101 360             ; 360       m/p     m       n
102 *               ; 360*m/p   m       n       n
103 SIN             ; value     m       n       n
104 100             ; 100       value   m       n
105 *               ; %value    m       n       n
106 ARCL X          ; "p: %value"
107 FIX 6           ;
108 AVIEW           ;
109 RDN             ; m         n       n
110 END             ;

Examples:

The date-format DMY is used.

27.021963
XEQ "NED"
NED: 14.11.2018
23: -100
28: -100
33: -76


01.011905
XEQ "NED"
NED: 10.10.2018
23: -100
28: 62
33: 100


28.092018
XEQ "NED"
NED: 30.11.2018
23: -100
28: 100
33: -54


Thanks for the challenge
Thomas
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
HHC 2018 Programming Contests - Joe Horn - 09-13-2018, 02:17 PM
RE: HHC 2018 Programming Contests - pier4r - 09-13-2018, 06:29 PM
RE: HHC 2018 Programming Contests - Zaphod - 09-13-2018, 10:10 PM
RE: HHC 2018 Programming Contests - Gene - 09-13-2018, 10:56 PM
RE: HHC 2018 Programming Contests - Gene - 09-14-2018, 12:06 AM
RE: HHC 2018 Programming Contests - Jlouis - 09-19-2018, 07:00 PM
RE: HHC 2018 Programming Contests - sasa - 09-19-2018, 11:17 AM
RE: HHC 2018 Programming Contests - pier4r - 09-29-2018, 07:41 PM
RE: HHC 2018 Programming Contests - 3298 - 09-30-2018, 05:32 PM
RE: HHC 2018 Programming Contests - 3298 - 09-30-2018, 08:47 PM
RE: HHC 2018 Programming Contests - Gene - 09-29-2018, 07:22 PM
RE: HHC 2018 Programming Contests - Gene - 10-01-2018, 02:55 AM
RE: HHC 2018 Programming Contests - sasa - 10-01-2018, 05:31 AM
RE: HHC 2018 Programming Contests - sasa - 10-01-2018, 09:54 AM
RE: HHC 2018 Programming Contests - 3298 - 10-01-2018, 06:37 AM
RE: HHC 2018 Programming Contests - Thomas Klemm - 10-01-2018 06:40 AM
RE: HHC 2018 Programming Contests - Werner - 10-01-2018, 01:42 PM
RE: HHC 2018 Programming Contests - Werner - 10-02-2018, 06:10 AM
RE: HHC 2018 Programming Contests - Namir - 10-04-2018, 06:09 PM
RE: HHC 2018 Programming Contests - Werner - 10-03-2018, 02:03 PM
RE: HHC 2018 Programming Contests - Werner - 10-04-2018, 05:55 AM
RE: HHC 2018 Programming Contests - 3298 - 10-04-2018, 02:48 PM
RE: HHC 2018 Programming Contests - 3298 - 10-05-2018, 08:26 PM
RE: HHC 2018 Programming Contests - 3298 - 10-06-2018, 12:07 PM
RE: HHC 2018 Programming Contests - 3298 - 10-06-2018, 04:21 PM



User(s) browsing this thread: 2 Guest(s)