Debian Codegraph @

reasoning/fundamental-theorem-of-arithmetic/fundamental-theorem-of-arithmetic.n3

raw
1 @prefix : <http://example.org/fta#> .
2 @prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
3 @prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
4 @prefix math: <http://www.w3.org/2000/10/swap/math#> .
5 @prefix log: <http://www.w3.org/2000/10/swap/log#> .
6 @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
7
8 ############################################################
9 # P3: Prompt → Program → Proof (Answer, Reason, Check)
10 # Fundamental Theorem of Arithmetic (existence + uniqueness)
11 # Strategy: trial division by the *smallest* prime divisor.
12 ############################################################
13
14 # --- Vocabulary ---
15 :Integer a rdfs:Class . # numbers to factor
16 :Prime a rdfs:Class . # catalog of candidate primes
17 :PrimeFactor a rdfs:Class . # one prime factor occurrence
18 :Work a rdfs:Class . # work items during factoring
19 :Step a rdfs:Class . # a single division step
20 :Check a rdfs:Class .
21
22 :value a rdf:Property . # numeric value of an :Integer
23 :val a rdf:Property . # numeric value carried by a :Prime
24 :answer a rdf:Property . # links :Integer → factor nodes
25 :why a rdf:Property . # links :Integer → step records
26 :check a rdf:Property . # links :Integer → check results
27 :status a rdf:Property . # e.g., "factored"
28
29 # Work/Step details
30 :num a rdf:Property . # which integer this Work/Step belongs to
31 :m a rdf:Property . # current working remainder (number)
32 :from a rdf:Property . # pre-division value for a step
33 :to a rdf:Property . # post-division value for a step
34 :prime a rdf:Property . # prime used at a step or on a factor
35
36 :kind a rdf:Property .
37 :ok a rdf:Property .
38 :residual a rdf:Property .
39
40 ############################################################
41 # Prime catalog (enough for the harness below; extend as needed)
42 ############################################################
43 :P2 a :Prime; :val 2 .
44 :P3 a :Prime; :val 3 .
45 :P5 a :Prime; :val 5 .
46 :P7 a :Prime; :val 7 .
47 :P11 a :Prime; :val 11 .
48 :P13 a :Prime; :val 13 .
49 :P17 a :Prime; :val 17 .
50 :P19 a :Prime; :val 19 .
51 :P23 a :Prime; :val 23 .
52 :P29 a :Prime; :val 29 .
53 :P31 a :Prime; :val 31 .
54 :P37 a :Prime; :val 37 .
55 :P41 a :Prime; :val 41 .
56 :P43 a :Prime; :val 43 .
57 :P47 a :Prime; :val 47 .
58 :P53 a :Prime; :val 53 .
59 :P59 a :Prime; :val 59 .
60 :P61 a :Prime; :val 61 .
61 :P67 a :Prime; :val 67 .
62 :P71 a :Prime; :val 71 .
63 :P73 a :Prime; :val 73 .
64 :P79 a :Prime; :val 79 .
65 :P83 a :Prime; :val 83 .
66 :P89 a :Prime; :val 89 .
67 :P97 a :Prime; :val 97 .
68
69 ############################################################
70 # Initialization: seed a Work item for each integer n > 1
71 ############################################################
72 {
73 ?N a :Integer; :value ?n .
74 ?n math:greaterThan 1 .
75 }
76 =>
77 {
78 _:w a :Work; :num ?N; :m ?n .
79 } .
80
81 ############################################################
82 # Factoring step:
83 # Take the *smallest* catalog prime p that divides the current m,
84 # emit one prime factor p, record the step, and continue with m/p.
85 ############################################################
86 {
87 ?w a :Work; :num ?N; :m ?m .
88 ?P a :Prime; :val ?p .
89
90 (?m ?p) math:remainder ?r .
91 ?r math:equalTo 0 . # p divides m
92
93 # Minimality guard: no smaller catalog prime divides m
94 ?SCOPE log:notIncludes {
95 ?Q a :Prime; :val ?q .
96 ?q math:lessThan ?p .
97 (?m ?q) math:remainder ?rq .
98 ?rq math:equalTo 0 .
99 } .
100
101 (?m ?p) math:integerQuotient ?q .
102 }
103 =>
104 {
105 # Record a factor occurrence
106 ?N :answer [ a :PrimeFactor; :prime ?p ] .
107
108 # Record the step as part of the "Reason"
109 _:s a :Step; :num ?N; :from ?m; :prime ?p; :to ?q .
110 ?N :why _:s .
111
112 # Continue factoring
113 _:w2 a :Work; :num ?N; :m ?q .
114 } .
115
116 ############################################################
117 # Termination: when we reach 1, mark the integer as factored
118 ############################################################
119 {
120 ?w a :Work; :num ?N; :m 1 .
121 }
122 =>
123 {
124 ?N :status "factored" .
125 } .
126
127 ############################################################
128 # ----------------------- CHECKS --------------------------
129 # C1 (per-step divisibility): remainder(from, p) = 0
130 ############################################################
131 {
132 ?s a :Step; :from ?m; :prime ?p; :to ?q .
133 (?m ?p) math:remainder ?r .
134 ?r math:equalTo 0 .
135 }
136 =>
137 {
138 _:c a :Check; :kind "step-divisible"; :ok true .
139 } .
140
141 ############################################################
142 # C2 (per-step reconstruction): (to * p) = from
143 ############################################################
144 {
145 ?s a :Step; :from ?m; :prime ?p; :to ?q .
146 (?q ?p) math:product ?recon .
147 ?recon math:equalTo ?m .
148 }
149 =>
150 {
151 _:c a :Check; :kind "step-reconstruct"; :ok true .
152 } .
153
154 ############################################################
155 # C3 (per-step minimality): no smaller catalog prime divides 'from'
156 ############################################################
157 {
158 ?s a :Step; :from ?m; :prime ?p .
159 ?SCOPE log:notIncludes {
160 ?Q a :Prime; :val ?q .
161 ?q math:lessThan ?p .
162 (?m ?q) math:remainder ?rq .
163 ?rq math:equalTo 0 .
164 } .
165 }
166 =>
167 {
168 _:c a :Check; :kind "step-minimal-prime"; :ok true .
169 } .
170
171 ############################################################
172 # C4 (factor is prime w.r.t. catalog): p has no smaller divisor
173 ############################################################
174 {
175 ?N :answer ?f .
176 ?f a :PrimeFactor; :prime ?p .
177 ?p math:greaterThan 1 .
178 ?SCOPE log:notIncludes {
179 ?Q a :Prime; :val ?q .
180 ?q math:lessThan ?p .
181 (?p ?q) math:remainder ?rp .
182 ?rp math:equalTo 0 .
183 } .
184 }
185 =>
186 {
187 _:c a :Check; :kind "factor-is-prime"; :ok true .
188 } .
189
190 ############################################################
191 # C5 (done): we eventually reached 1 for this integer
192 ############################################################
193 {
194 ?N a :Integer; :status "factored" .
195 }
196 =>
197 {
198 ?N :check [ a :Check; :kind "terminated-at-1"; :ok true ] .
199 } .
200
201 ############################################################
202 # ----------------------- HARNESS -------------------------
203 # Six integers > 1 to exercise composite & prime cases
204 ############################################################
205
206 # 60 = 2 * 2 * 3 * 5
207 :N60 a :Integer; :value 60 .
208
209 # 84 = 2 * 2 * 3 * 7
210 :N84 a :Integer; :value 84 .
211
212 # 97 is prime
213 :N97 a :Integer; :value 97 .
214
215 # 360 = 2 * 2 * 2 * 3 * 3 * 5
216 :N360 a :Integer; :value 360 .
217
218 # 1001 = 7 * 11 * 13
219 :N1001 a :Integer; :value 1001 .
220
221 # 32 = 2^5
222 :N32 a :Integer; :value 32 .
223