Sokrates on Oracle

The Fundamental theorem of arithmetic – SQL version

Posted by Matthias Rogel on 26. May 2015

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

Advertisements

One Response to “The Fundamental theorem of arithmetic – SQL version”

  1. we also can verify the decomposition we found:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: