| 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 |
|