The Fundamental theorem of arithmetic – SQL version

Every positive integer (except the number 1) can be represented in exactly one way apart from rearrangement as a product of one or more primes, see for example Wolfram MathWorld or Wikipedia.

Here is the SQL-Version, we compute this for all integers up to 100

with bound as
(
select 100 as bound from dual
),
n_until_bound as (
select level+1 n
from dual
connect by level <= (select bound.bound from bound)
),
primes_under_bound as
(
select n_until_bound.n as prime
from n_until_bound
minus
select n1.n * n2.n
from n_until_bound n1, n_until_bound n2
where n1.n <= n2.n
and n1.n <= (select sqrt(bound.bound) from bound)
),
primepowers_until_bound as
(
select p.prime, l.exponent
from primes_under_bound p, lateral(select level as exponent from dual connect by level <= log(p.prime, (select bound.bound from bound))) l
),
factors as
(
select n.n, pb.prime, pb.exponent
from n_until_bound n, primepowers_until_bound pb
where mod(n.n, power(pb.prime, pb.exponent)) = 0
),
largestfactors as
(
select
 f.n, f.prime, min(f.exponent) keep(dense_rank first order by f.exponent desc) as exponent
from factors f
group by f.n, f.prime
)
select /*+pallel */ lf.n || ' = ' || listagg(lf.prime || case when lf.exponent > 1 then ' ^ ' || lf.exponent end, ' * ') within group(order by lf.prime asc) as factorization
from largestfactors lf
group by lf.n
order by lf.n
FACTORIZATION
----------------------------------------------------------------------------------------------------
2 = 2
3 = 3
4 = 2 ^ 2
5 = 5
6 = 2 * 3
7 = 7
8 = 2 ^ 3
9 = 3 ^ 2
10 = 2 * 5
11 = 11
12 = 2 ^ 2 * 3
13 = 13
14 = 2 * 7
15 = 3 * 5
16 = 2 ^ 4
17 = 17
18 = 2 * 3 ^ 2
19 = 19
20 = 2 ^ 2 * 5
21 = 3 * 7
22 = 2 * 11
23 = 23
24 = 2 ^ 3 * 3
25 = 5 ^ 2
26 = 2 * 13
27 = 3 ^ 3
28 = 2 ^ 2 * 7
29 = 29
30 = 2 * 3 * 5
31 = 31
32 = 2 ^ 5
33 = 3 * 11
34 = 2 * 17
35 = 5 * 7
36 = 2 ^ 2 * 3 ^ 2
37 = 37
38 = 2 * 19
39 = 3 * 13
40 = 2 ^ 3 * 5
41 = 41
42 = 2 * 3 * 7
43 = 43
44 = 2 ^ 2 * 11
45 = 3 ^ 2 * 5
46 = 2 * 23
47 = 47
48 = 2 ^ 4 * 3
49 = 7 ^ 2
50 = 2 * 5 ^ 2
51 = 3 * 17
52 = 2 ^ 2 * 13
53 = 53
54 = 2 * 3 ^ 3
55 = 5 * 11
56 = 2 ^ 3 * 7
57 = 3 * 19
58 = 2 * 29
59 = 59
60 = 2 ^ 2 * 3 * 5
61 = 61
62 = 2 * 31
63 = 3 ^ 2 * 7
64 = 2 ^ 6
65 = 5 * 13
66 = 2 * 3 * 11
67 = 67
68 = 2 ^ 2 * 17
69 = 3 * 23
70 = 2 * 5 * 7
71 = 71
72 = 2 ^ 3 * 3 ^ 2
73 = 73
74 = 2 * 37
75 = 3 * 5 ^ 2
76 = 2 ^ 2 * 19
77 = 7 * 11
78 = 2 * 3 * 13
79 = 79
80 = 2 ^ 4 * 5
81 = 3 ^ 4
82 = 2 * 41
83 = 83
84 = 2 ^ 2 * 3 * 7
85 = 5 * 17
86 = 2 * 43
87 = 3 * 29
88 = 2 ^ 3 * 11
89 = 89
90 = 2 * 3 ^ 2 * 5
91 = 7 * 13
92 = 2 ^ 2 * 23
93 = 3 * 31
94 = 2 * 47
95 = 5 * 19
96 = 2 ^ 5 * 3
97 = 97
98 = 2 * 7 ^ 2
99 = 3 ^ 2 * 11
100 = 2 ^ 2 * 5 ^ 2

A Greedy Algorithm using Recursive subquery factoring ( or better – read the comments – using pattern matching)

Today is friday and I like the twitter-hashtag #FibonacciFriday,
so I tweeted

Zeckendorfs theorem every positive integer is uniquely the sum of distinct nonconsecutive Fibonaccis http://en.wikipedia.org/wiki/Zeckendorf%27s_theorem#FibonacciFriday

— Matthias Rogel (@MatthiasRogel) 22. Mai 2015

 

Don’t be afraid of having a look at the wikipedia-site, the math is not complicated at all ( you don’t need more than adding natural numbers smaller than hundred ), nevertheless the theorem is nice from a mathematical point of view.

And there is also mentioned

… For any given positive integer, a representation that satisfies the conditions of Zeckendorf’s theorem can be found by using a greedy algorithm, choosing the largest possible Fibonacci number at each stage. …

After thinking a bit about it, I came to the idea to implement it solely in SQL which might show the strength of this language.

Here we go, we compute the Zeckendorf representations of the first 200 natural numbers in SQL.

If you are not familiar with the xmlquery-part of it, see what Tom Kyte learned from me

with
n as
(
 /* the first 200 natural numbers */
 select level as n
 from dual
 connect by level <= 200
),
f(n, a, b) as
(
 /* construct fibonaccis, 30 are surely enough ... */
 select 1 as n, 1 as a, 1 as b
 from dual
 union all
 select n+1, b, a+b
 from f
 where n<=30
)
,
fibonaccis as
(
 select
 f.a as f
 from f
),
decomp(n, s) as
(
 /* here is the magic recursive subquery factoring */
 select
 n.n,
 (select cast(max(fibonaccis.f) as varchar2(100)) from fibonaccis where fibonaccis.f <= n.n)
 from n
 union all
 select
 d.n,
 rtrim
 (
 d.s || ' + ' ||
 (
 select cast(max(fibonaccis.f) as varchar2(10))
 from fibonaccis
 where fibonaccis.f <= d.n - xmlquery(d.s returning content).getNumberVal()
 ),
 ' + '
 )
 from decomp d
 where
 d.s !=
 rtrim
 (
 d.s || ' + ' ||
 (
 select cast(max(fibonaccis.f) as varchar2(10))
 from fibonaccis
 where fibonaccis.f <= d.n - xmlquery(d.s returning content).getNumberVal()
 ),
 ' + '
 )
)
/* we only want "the last" decomp, the one with maximal length */
select
 decomp.n ||
 ' = ' ||
 min(decomp.s) keep(dense_rank first order by length(decomp.s) desc)
 as zeckendorf_representation
from decomp
group by decomp.n
order by decomp.n
/

ZECKENDORF_REPRESENTATION
------------------------------------------------------------------------------------------------------------------------------------------------------------
1 = 1
2 = 2
3 = 3
4 = 3 + 1
5 = 5
6 = 5 + 1
7 = 5 + 2
8 = 8
9 = 8 + 1
10 = 8 + 2
11 = 8 + 3
12 = 8 + 3 + 1
13 = 13
14 = 13 + 1
15 = 13 + 2
16 = 13 + 3
17 = 13 + 3 + 1
18 = 13 + 5
19 = 13 + 5 + 1
20 = 13 + 5 + 2
21 = 21
22 = 21 + 1
23 = 21 + 2
24 = 21 + 3
25 = 21 + 3 + 1
26 = 21 + 5
27 = 21 + 5 + 1
28 = 21 + 5 + 2
29 = 21 + 8
30 = 21 + 8 + 1
31 = 21 + 8 + 2
32 = 21 + 8 + 3
33 = 21 + 8 + 3 + 1
34 = 34
35 = 34 + 1
36 = 34 + 2
37 = 34 + 3
38 = 34 + 3 + 1
39 = 34 + 5
40 = 34 + 5 + 1
41 = 34 + 5 + 2
42 = 34 + 8
43 = 34 + 8 + 1
44 = 34 + 8 + 2
45 = 34 + 8 + 3
46 = 34 + 8 + 3 + 1
47 = 34 + 13
48 = 34 + 13 + 1
49 = 34 + 13 + 2
50 = 34 + 13 + 3
51 = 34 + 13 + 3 + 1
52 = 34 + 13 + 5
53 = 34 + 13 + 5 + 1
54 = 34 + 13 + 5 + 2
55 = 55
56 = 55 + 1
57 = 55 + 2
58 = 55 + 3
59 = 55 + 3 + 1
60 = 55 + 5
61 = 55 + 5 + 1
62 = 55 + 5 + 2
63 = 55 + 8
64 = 55 + 8 + 1
65 = 55 + 8 + 2
66 = 55 + 8 + 3
67 = 55 + 8 + 3 + 1
68 = 55 + 13
69 = 55 + 13 + 1
70 = 55 + 13 + 2
71 = 55 + 13 + 3
72 = 55 + 13 + 3 + 1
73 = 55 + 13 + 5
74 = 55 + 13 + 5 + 1
75 = 55 + 13 + 5 + 2
76 = 55 + 21
77 = 55 + 21 + 1
78 = 55 + 21 + 2
79 = 55 + 21 + 3
80 = 55 + 21 + 3 + 1
81 = 55 + 21 + 5
82 = 55 + 21 + 5 + 1
83 = 55 + 21 + 5 + 2
84 = 55 + 21 + 8
85 = 55 + 21 + 8 + 1
86 = 55 + 21 + 8 + 2
87 = 55 + 21 + 8 + 3
88 = 55 + 21 + 8 + 3 + 1
89 = 89
90 = 89 + 1
91 = 89 + 2
92 = 89 + 3
93 = 89 + 3 + 1
94 = 89 + 5
95 = 89 + 5 + 1
96 = 89 + 5 + 2
97 = 89 + 8
98 = 89 + 8 + 1
99 = 89 + 8 + 2
100 = 89 + 8 + 3
101 = 89 + 8 + 3 + 1
102 = 89 + 13
103 = 89 + 13 + 1
104 = 89 + 13 + 2
105 = 89 + 13 + 3
106 = 89 + 13 + 3 + 1
107 = 89 + 13 + 5
108 = 89 + 13 + 5 + 1
109 = 89 + 13 + 5 + 2
110 = 89 + 21
111 = 89 + 21 + 1
112 = 89 + 21 + 2
113 = 89 + 21 + 3
114 = 89 + 21 + 3 + 1
115 = 89 + 21 + 5
116 = 89 + 21 + 5 + 1
117 = 89 + 21 + 5 + 2
118 = 89 + 21 + 8
119 = 89 + 21 + 8 + 1
120 = 89 + 21 + 8 + 2
121 = 89 + 21 + 8 + 3
122 = 89 + 21 + 8 + 3 + 1
123 = 89 + 34
124 = 89 + 34 + 1
125 = 89 + 34 + 2
126 = 89 + 34 + 3
127 = 89 + 34 + 3 + 1
128 = 89 + 34 + 5
129 = 89 + 34 + 5 + 1
130 = 89 + 34 + 5 + 2
131 = 89 + 34 + 8
132 = 89 + 34 + 8 + 1
133 = 89 + 34 + 8 + 2
134 = 89 + 34 + 8 + 3
135 = 89 + 34 + 8 + 3 + 1
136 = 89 + 34 + 13
137 = 89 + 34 + 13 + 1
138 = 89 + 34 + 13 + 2
139 = 89 + 34 + 13 + 3
140 = 89 + 34 + 13 + 3 + 1
141 = 89 + 34 + 13 + 5
142 = 89 + 34 + 13 + 5 + 1
143 = 89 + 34 + 13 + 5 + 2
144 = 144
145 = 144 + 1
146 = 144 + 2
147 = 144 + 3
148 = 144 + 3 + 1
149 = 144 + 5
150 = 144 + 5 + 1
151 = 144 + 5 + 2
152 = 144 + 8
153 = 144 + 8 + 1
154 = 144 + 8 + 2
155 = 144 + 8 + 3
156 = 144 + 8 + 3 + 1
157 = 144 + 13
158 = 144 + 13 + 1
159 = 144 + 13 + 2
160 = 144 + 13 + 3
161 = 144 + 13 + 3 + 1
162 = 144 + 13 + 5
163 = 144 + 13 + 5 + 1
164 = 144 + 13 + 5 + 2
165 = 144 + 21
166 = 144 + 21 + 1
167 = 144 + 21 + 2
168 = 144 + 21 + 3
169 = 144 + 21 + 3 + 1
170 = 144 + 21 + 5
171 = 144 + 21 + 5 + 1
172 = 144 + 21 + 5 + 2
173 = 144 + 21 + 8
174 = 144 + 21 + 8 + 1
175 = 144 + 21 + 8 + 2
176 = 144 + 21 + 8 + 3
177 = 144 + 21 + 8 + 3 + 1
178 = 144 + 34
179 = 144 + 34 + 1
180 = 144 + 34 + 2
181 = 144 + 34 + 3
182 = 144 + 34 + 3 + 1
183 = 144 + 34 + 5
184 = 144 + 34 + 5 + 1
185 = 144 + 34 + 5 + 2
186 = 144 + 34 + 8
187 = 144 + 34 + 8 + 1
188 = 144 + 34 + 8 + 2
189 = 144 + 34 + 8 + 3
190 = 144 + 34 + 8 + 3 + 1
191 = 144 + 34 + 13
192 = 144 + 34 + 13 + 1
193 = 144 + 34 + 13 + 2
194 = 144 + 34 + 13 + 3
195 = 144 + 34 + 13 + 3 + 1
196 = 144 + 34 + 13 + 5
197 = 144 + 34 + 13 + 5 + 1
198 = 144 + 34 + 13 + 5 + 2
199 = 144 + 55
200 = 144 + 55 + 1

200 rows selected.

Elapsed: 00:01:28.71

Learning foreign languages with Oracle SQL

with y as
(
   select 
      add_months(date'2012-01-01', level-1) monn, 
      to_char(add_months(date'2012-01-01', level-1), 'MONTH') mon
   from dual
   connect by level<=12
)
select 
   value as language, 
   y.mon, 
   to_char(y.monn, 'MONTH', q'|nls_date_language='|' || value || q'|'|') month, 
   to_char(y.monn, 'MON', q'|nls_date_language='|' || value || q'|'|') month_s
from v$nls_valid_values n, y
where n.parameter='LANGUAGE'
order by language, y.monn

TRADITIONAL CHINESE looks easy