nx_theorems4_test.nx source
↩ module page · 153 lines · 7305 B
1// nx_theorems4_test.nx -- batch 4 verification.
2
3import "syscalls.nx"
4import "nx_qed_freek.nx"
5
6func main() -> i64 {
7 // #51 CRT: x ≡ 2 (mod 3), x ≡ 3 (mod 5). Unique soln mod 15 is x = 8.
8 if nx_th_crt_2(2, 3, 3, 5) != 8 { return 51 }
9 // x ≡ 1 (mod 4), x ≡ 2 (mod 9) -> x = 29 mod 36.
10 if nx_th_crt_2(1, 4, 2, 9) != 29 { return 52 }
11
12 // #52 Lucas: C(10, 3) mod 5. C(10,3)=120. 120 mod 5 = 0.
13 if nx_th_lucas_binomial_mod_p(10, 3, 5) != 0 { return 53 }
14 // C(7, 3) mod 5 = 35 mod 5 = 0.
15 if nx_th_lucas_binomial_mod_p(7, 3, 5) != 0 { return 54 }
16 // C(6, 3) mod 5 = 20 mod 5 = 0.
17 if nx_th_lucas_binomial_mod_p(6, 3, 5) != 0 { return 55 }
18 // C(7, 2) mod 5 = 21 mod 5 = 1.
19 if nx_th_lucas_binomial_mod_p(7, 2, 5) != 1 { return 56 }
20
21 // #53 Carmichael: 561 = 3*11*17 is the first Carmichael number.
22 if nx_th_carmichael_check(561) != 1 { return 57 }
23 // 1105 = 5*13*17 second Carmichael.
24 if nx_th_carmichael_check(1105) != 1 { return 58 }
25 // 15 isn't (a=2: 2^14 mod 15 = 16384 mod 15 = 4 != 1).
26 if nx_th_carmichael_check(15) != 0 { return 59 }
27
28 // #54 Mersenne primes: M_2=3 prime, M_3=7 prime, M_5=31 prime, M_11=2047=23*89 not.
29 if nx_th_mersenne_prime_check(2) != 1 { return 61 }
30 if nx_th_mersenne_prime_check(3) != 1 { return 62 }
31 if nx_th_mersenne_prime_check(5) != 1 { return 63 }
32 if nx_th_mersenne_prime_check(7) != 1 { return 64 }
33 if nx_th_mersenne_prime_check(11) != 0 { return 65 }
34 if nx_th_mersenne_prime_check(13) != 1 { return 66 }
35
36 // #55 Sophie Germain: 2, 3, 5, 11, 23, 29 are S.G. primes.
37 if nx_th_sophie_germain_check(2) != 1 { return 67 }
38 if nx_th_sophie_germain_check(3) != 1 { return 68 }
39 if nx_th_sophie_germain_check(5) != 1 { return 69 }
40 if nx_th_sophie_germain_check(11) != 1 { return 70 }
41 if nx_th_sophie_germain_check(7) != 0 { return 71 } // 15 not prime
42
43 // #56 Bertrand: for n=10, there's a prime in (10, 20). Should find 11.
44 if nx_th_bertrand_witness(10) != 11 { return 72 }
45 if nx_th_bertrand_witness(20) != 23 { return 73 }
46
47 // #57 QM-AM check.
48 if nx_th_qm_am_check(3, 5) != 1 { return 74 }
49 if nx_th_qm_am_check(0, 10) != 1 { return 75 }
50
51 // #58 Holder p2 q2 on (1,2,3) and (4,5,6).
52 let xv: *i64 = (sys_mmap(24)) as *i64
53 let yv: *i64 = (sys_mmap(24)) as *i64
54 xv[0]=1; xv[1]=2; xv[2]=3
55 yv[0]=4; yv[1]=5; yv[2]=6
56 if nx_th_holder_p2_q2_check(xv, yv, 3) != 1 { return 76 }
57
58 // #59 Minkowski p=2.
59 if nx_th_minkowski_p2_check(xv, yv, 3) != 1 { return 77 }
60
61 // #60 Vandermonde: C(3+4, 2) = C(7,2)=21 == sum_{k=0..2} C(3,k)C(4,2-k).
62 if nx_th_vandermonde_check(3, 4, 2) != 1 { return 78 }
63 if nx_th_vandermonde_check(5, 3, 4) != 1 { return 79 }
64
65 // #61 Hockey stick: sum_{i=2..6} C(i, 2) = C(7, 3) = 35.
66 // (1+3+6+10+15 = 35).
67 if nx_th_hockey_stick_check(6, 2) != 1 { return 80 }
68
69 // #62 Ptolemy: 3-4-5 right + 3-4-5 right glued at hypotenuse.
70 // Square 1x1: a=b=c=d=1, p=q=sqrt(2) so pq=2; ac+bd=1+1=2.
71 if nx_th_ptolemy_check(1, 1, 1, 1, 14142, 14142) != 0 { return 81 }
72 // Use scale: 10x10x10x10 with diagonals 14, 14: pq=196; ac+bd=100+100=200. Not perfect.
73 // Choose a triple that's exact. 5-5-5-5 square with diag sqrt(50)~7. We need
74 // integers. Use a=3, b=5, c=3, d=5, diagonals computed for cyclic quadrilateral.
75 // Actually, simple integer Ptolemy: rectangle 3x4: a=3, b=4, c=3, d=4, diagonal=5.
76 // pq=25; ac+bd=9+16=25. Verified.
77 if nx_th_ptolemy_check(3, 4, 3, 4, 5, 5) != 1 { return 82 }
78
79 // #63 Ceva (concurrent cevians): if BD/DC * CE/EA * AF/FB = 1.
80 // Try medians: BD=DC=1, CE=EA=1, AF=FB=1 -> product 1.
81 if nx_th_ceva_check(1, 1, 1, 1, 1, 1) != 1 { return 83 }
82 // Non-concurrent: BD=2, DC=1, CE=1, EA=2, AF=2, FB=1 -> 4 != 2.
83 if nx_th_ceva_check(2, 1, 1, 2, 2, 1) != 0 { return 84 }
84
85 // #64 Menelaus: same shape as Ceva but different geometry.
86 if nx_th_menelaus_check(1, 1, 1, 1, 1, 1) != 1 { return 85 }
87
88 // #65 Stewart: 3-4-5 with median to hypotenuse: a=5, b=4, c=3, d=2.5 (median len).
89 // 2d = sqrt(2b^2 + 2c^2 - a^2) = sqrt(50) approx 7.07; d^2 = 12.5 (integer ratio).
90 // Use scaled: a=10, b=8, c=6, d^2 from formula. m=n=5.
91 // b^2*m + c^2*n - a*d^2 = 64*5 + 36*5 - 10*d^2 = 320+180 - 10d^2 = 500 - 10d^2.
92 // = a*m*n = 10*25 = 250.
93 // So 10d^2 = 250, d^2 = 25, d = 5.
94 if nx_th_stewart_check(10, 8, 6, 5, 5, 5) != 1 { return 86 }
95
96 // #66 Singleton: (n=7, k=4, d=3) -> 4 <= 7-3+1=5. PASS.
97 if nx_th_singleton_bound_check(7, 4, 3) != 1 { return 87 }
98 if nx_th_singleton_bound_check(7, 5, 3) != 0 { return 88 }
99
100 // #67 Hamming: (n=7, k=4, d=3): 2^4 * (C(7,0)+C(7,1)) = 16*8=128 <= 128.
101 if nx_th_hamming_bound_check(7, 4, 3) != 1 { return 89 }
102
103 // #68 Plotkin: (n=4, k=2, d=3) -> 2d=6 > n=4; M=4; limit = 6/(6-4)=3.
104 // 4 > 3 -> bound violated -> return 0.
105 if nx_th_plotkin_bound_check(4, 2, 3) != 0 { return 90 }
106 // (n=4, k=1, d=3): M=2 <= 3 PASS.
107 if nx_th_plotkin_bound_check(4, 1, 3) != 1 { return 91 }
108
109 // #69 Squeeze: a=[1,2,3], b=[1,2,3], c=[1,2,3]: trivially squeezed.
110 let av: *i64 = (sys_mmap(24)) as *i64
111 let bv: *i64 = (sys_mmap(24)) as *i64
112 let cv: *i64 = (sys_mmap(24)) as *i64
113 av[0]=1; av[1]=2; av[2]=3
114 bv[0]=1; bv[1]=2; bv[2]=3
115 cv[0]=1; cv[1]=2; cv[2]=3
116 if nx_th_squeeze_check(av, bv, cv, 3) != 1 { return 92 }
117 // Violation: b[1] = 4 > c[1] = 3.
118 bv[1] = 4
119 if nx_th_squeeze_check(av, bv, cv, 3) != 0 { return 93 }
120
121 // #70 Lipschitz: f(x) = 2x. L=2 should hold; L=1 should fail.
122 let xx: *i64 = (sys_mmap(40)) as *i64
123 let yy: *i64 = (sys_mmap(40)) as *i64
124 xx[0]=0; xx[1]=1; xx[2]=3; xx[3]=7; xx[4]=10
125 yy[0]=0; yy[1]=2; yy[2]=6; yy[3]=14; yy[4]=20
126 if nx_th_lipschitz_check(xx, yy, 5, 2) != 1 { return 94 }
127 if nx_th_lipschitz_check(xx, yy, 5, 1) != 0 { return 95 }
128
129 // #71 Wolstenholme: C(14, 7) mod 7^3 = 343. C(14,7)=3432. 3432 mod 343 = 2.
130 if nx_th_wolstenholme_check(7) != 1 { return 96 }
131 if nx_th_wolstenholme_check(11) != 1 { return 97 }
132
133 // #72 Carmichael lambda: lambda(1)=1, lambda(2)=1, lambda(8)=2, lambda(15)=4.
134 if nx_th_carmichael_lambda(1) != 1 { return 98 }
135 if nx_th_carmichael_lambda(15) != 4 { return 99 }
136 // lambda(12) = lcm(lambda(4), lambda(3)) = lcm(2, 2) = 2.
137 if nx_th_carmichael_lambda(12) != 2 { return 100 }
138
139 // #74 RSA: n=33=3*11, phi=20, e=3 (gcd(3,20)=1), d=7 (3*7=21≡1 mod 20).
140 // Sign m=4: s = 4^7 mod 33 = 16384 mod 33 = 16384 - 496*33 = 16384 - 16368 = 16.
141 // Verify: 16^3 mod 33 = 4096 mod 33 = 4096 - 124*33 = 4096 - 4092 = 4 = m. PASS.
142 if nx_th_rsa_verify(4, 16, 3, 33) != 1 { return 110 }
143
144 // #75 Fermat two squares: 5 = 1+4, 13 = 4+9, 17 = 1+16, 29 = 4+25.
145 if nx_th_fermat_two_squares(5) != 1 { return 120 }
146 if nx_th_fermat_two_squares(13) != 1 { return 121 }
147 if nx_th_fermat_two_squares(17) != 1 { return 122 }
148 if nx_th_fermat_two_squares(29) != 1 { return 123 }
149 // 7 ≡ 3 mod 4, not expressible.
150 if nx_th_fermat_two_squares(7) != 0 { return 124 }
151
152 return 0
153}