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
 Thomas Klemm Senior Member Posts: 2,071 Joined: Dec 2013
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
 « Next Oldest | Next Newest »

 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 - Valentin Albillo - 09-13-2018, 10:05 PM RE: HHC 2018 Programming Contests - Zaphod - 09-13-2018, 10:10 PM RE: HHC 2018 Programming Contests - Joe Horn - 09-14-2018, 04:42 AM RE: HHC 2018 Programming Contests - Valentin Albillo - 09-14-2018, 10:28 PM RE: HHC 2018 Programming Contests - toml_12953 - 09-19-2018, 09:57 AM RE: HHC 2018 Programming Contests - Gene - 09-13-2018, 10:56 PM RE: HHC 2018 Programming Contests - rprosperi - 09-13-2018, 11:34 PM RE: HHC 2018 Programming Contests - Gene - 09-14-2018, 12:06 AM RE: HHC 2018 Programming Contests - cyrille de brébisson - 09-14-2018, 05:28 AM RE: HHC 2018 Programming Contests - Joe Horn - 09-14-2018, 06:18 PM RE: HHC 2018 Programming Contests - RMollov - 09-19-2018, 09:42 AM RE: HHC 2018 Programming Contests - Jlouis - 09-19-2018, 07:00 PM RE: HHC 2018 Programming Contests - Thomas Klemm - 09-19-2018, 10:25 AM RE: HHC 2018 Programming Contests - sasa - 09-19-2018, 11:17 AM RE: HHC 2018 Programming Contests - Joe Horn - 09-19-2018, 12:12 PM RE: HHC 2018 Programming Contests - Eddie W. Shore - 09-19-2018, 12:15 PM RE: HHC 2018 Programming Contests - Eddie W. Shore - 09-21-2018, 12:25 PM RE: HHC 2018 Programming Contests - rprosperi - 09-21-2018, 12:53 PM RE: HHC 2018 Programming Contests - Joe Horn - 09-22-2018, 06:59 PM RE: HHC 2018 Programming Contests - Joe Horn - 09-29-2018, 07:03 PM RE: HHC 2018 Programming Contests - pier4r - 09-29-2018, 07:41 PM RE: HHC 2018 Programming Contests - Csaba Tizedes - 09-30-2018, 11:38 AM RE: HHC 2018 Programming Contests - 3298 - 09-30-2018, 05:32 PM RE: HHC 2018 Programming Contests - Csaba Tizedes - 09-30-2018, 07:16 PM RE: HHC 2018 Programming Contests - Gerson W. Barbosa - 09-30-2018, 08:32 PM RE: HHC 2018 Programming Contests - 3298 - 09-30-2018, 08:47 PM RE: HHC 2018 Programming Contests - Gerson W. Barbosa - 09-30-2018, 09:40 PM RE: HHC 2018 Programming Contests - Didier Lachieze - 09-30-2018, 09:54 PM RE: HHC 2018 Programming Contests - Gerson W. Barbosa - 09-30-2018, 10:22 PM RE: HHC 2018 Programming Contests - Gene - 09-29-2018, 07:22 PM RE: HHC 2018 Programming Contests - Joe Horn - 09-30-2018, 04:42 AM RE: HHC 2018 Programming Contests - grsbanks - 09-30-2018, 04:58 AM RE: HHC 2018 Programming Contests - Didier Lachieze - 09-30-2018, 08:49 PM RE: HHC 2018 Programming Contests - Joe Horn - 09-30-2018, 11:24 PM RE: HHC 2018 Programming Contests - Gene - 10-01-2018, 02:55 AM RE: HHC 2018 Programming Contests - Gerson W. Barbosa - 10-01-2018, 05:15 AM RE: HHC 2018 Programming Contests - sasa - 10-01-2018, 05:31 AM RE: HHC 2018 Programming Contests - Joe Horn - 10-01-2018, 06:09 AM RE: HHC 2018 Programming Contests - sasa - 10-01-2018, 09:54 AM RE: HHC 2018 Programming Contests - Gerson W. Barbosa - 10-01-2018, 04:57 AM RE: HHC 2018 Programming Contests - Didier Lachieze - 10-01-2018, 04:59 AM RE: HHC 2018 Programming Contests - Gerson W. Barbosa - 10-01-2018, 06:21 AM RE: HHC 2018 Programming Contests - 3298 - 10-01-2018, 06:37 AM RE: HHC 2018 Programming Contests - Gerson W. Barbosa - 10-03-2018, 04:20 AM RE: HHC 2018 Programming Contests - Joe Horn - 10-01-2018, 06:38 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 - jjohnson873 - 10-01-2018, 08:38 PM RE: HHC 2018 Programming Contests - Thomas Klemm - 10-01-2018, 09:47 PM RE: HHC 2018 Programming Contests - Didier Lachieze - 10-01-2018, 10:46 AM RE: HHC 2018 Programming Contests - Thomas Klemm - 10-01-2018, 09:33 PM RE: HHC 2018 Programming Contests - Werner - 10-02-2018, 06:10 AM RE: HHC 2018 Programming Contests - Fred Lusk - 10-02-2018, 04:15 AM RE: HHC 2018 Programming Contests - Thomas Klemm - 10-02-2018, 08:11 AM RE: HHC 2018 Programming Contests - Joe Horn - 10-02-2018, 04:33 PM RE: HHC 2018 Programming Contests - Eddie W. Shore - 10-03-2018, 12:39 PM RE: HHC 2018 Programming Contests - Namir - 10-04-2018, 06:09 PM RE: HHC 2018 Programming Contests - Joe Horn - 10-02-2018, 08:47 PM RE: HHC 2018 Programming Contests - Werner - 10-03-2018, 02:03 PM RE: HHC 2018 Programming Contests - Didier Lachieze - 10-03-2018, 03:46 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 - Gerson W. Barbosa - 10-04-2018, 03:47 PM RE: HHC 2018 Programming Contests - Joe Horn - 10-05-2018, 12:00 AM RE: HHC 2018 Programming Contests - Didier Lachieze - 10-05-2018, 05:07 AM RE: HHC 2018 Programming Contests - Joe Horn - 10-05-2018, 06:22 AM RE: HHC 2018 Programming Contests - Craig Bladow - 06-25-2019, 01:27 AM RE: HHC 2018 Programming Contests - Joe Horn - 10-05-2018, 12:11 AM RE: HHC 2018 Programming Contests - Joe Horn - 10-05-2018, 12:36 AM RE: HHC 2018 Programming Contests - Didier Lachieze - 10-05-2018, 07:45 AM RE: HHC 2018 Programming Contests - Joe Horn - 10-05-2018, 12:26 PM RE: HHC 2018 Programming Contests - David Hayden - 10-05-2018, 02:25 PM RE: HHC 2018 Programming Contests - Gerson W. Barbosa - 10-05-2018, 07:23 PM RE: HHC 2018 Programming Contests - 3298 - 10-05-2018, 08:26 PM RE: HHC 2018 Programming Contests - Gerson W. Barbosa - 10-05-2018, 09:51 PM RE: HHC 2018 Programming Contests - 3298 - 10-06-2018, 12:07 PM RE: HHC 2018 Programming Contests - Joe Horn - 10-05-2018, 09:32 PM RE: HHC 2018 Programming Contests - Eddie W. Shore - 10-06-2018, 03:15 PM RE: HHC 2018 Programming Contests - Thomas Klemm - 10-06-2018, 10:14 AM RE: HHC 2018 Programming Contests - Gerson W. Barbosa - 10-06-2018, 11:42 AM RE: HHC 2018 Programming Contests - Thomas Klemm - 10-06-2018, 12:48 PM RE: HHC 2018 Programming Contests - Gerson W. Barbosa - 10-06-2018, 03:57 PM RE: HHC 2018 Programming Contests - 3298 - 10-06-2018, 04:21 PM RE: HHC 2018 Programming Contests - Thomas Klemm - 10-06-2018, 06:38 PM RE: HHC 2018 Programming Contests - David Hayden - 10-07-2018, 01:46 PM RE: HHC 2018 Programming Contests - Thomas Klemm - 10-09-2018, 04:48 AM

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