This site is supported by donations to The OEIS Foundation.

Factorization tree

From OeisWiki
Jump to: navigation, search


This article page is a stub, please help by expanding it.


Among the different integer factorization trees one might think of, the binary tree of recursive squarest factorizations down to primes (binary tree of recursive factorizations into central factors down to primes) seems the most interesting.

Binary tree of recursive squarest factorizations down to primes

The squarest factorization, i.e. into central factors, of 
n = i · j, 2   ≤   i   ≤   j,
minimizes 
j  −  i
and 
j  ⁄  i
. It corresponds to the squarest (least oblong) integral rectangle with area 
n
. This has minimal semi-perimeter (A063655), since 
s = i + j = i +
n
i
is minimal when 
ds
di
= 1  − 
n
i 2
= 0, i.e. n = i 2
.
          48
       /       \
      6         8
     / \       / \
    2   3     2   4
                 / \
                2   2

The binary tree of recursive squarest factorizations, i.e. into central factors, down to primes has

  • primes as leaf nodes;
  • an odd number of nodes (except for the root node, all nodes come in pairs of central factors);
  • an even number of edges (obviously, all edges come in pairs).
The number of nodes of the binary tree of recursive squarest factorizations of 
n = i · j, 2   ≤   i   ≤   j,
is
nodes(n) = 1 + sum(nodes(i), nodes(j)).
The number of levels of the binary tree of recursive squarest factorizations of 
n = i · j, 2   ≤   i   ≤   j,
is
levels(n) = 1 + max(levels(i), levels(j)).

A162348 Pairs (i,j) of central factors of n, such that i*j = n, where i is the largest divisor of n <= sqrt(n) and j is the smallest divisor of n >= sqrt(n).

{1, 1, 1, 2, 1, 3, 2, 2, 1, 5, 2, 3, 1, 7, 2, 4, 3, 3, 2, 5, 1, 11, 3, 4, 1, 13, 2, 7, 3, 5, 4, 4, 1, 17, 3, 6, 1, 19, 4, 5, 3, 7, 2, 11, 1, 23, 4, 6, 5, 5, 2, 13, 3, 9, 4, 7, 1, 29, 5, 6, 1, 31, 4, ...}

A033676 Largest divisor of n <= sqrt(n).

{1, 1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 3, 1, 2, 3, 4, 1, 3, 1, 4, 3, 2, 1, 4, 5, 2, 3, 4, 1, 5, 1, 4, 3, 2, 5, 6, 1, 2, 3, 5, 1, 6, 1, 4, 5, 2, 1, 6, 7, 5, 3, 4, 1, 6, 5, 7, 3, 2, ...}

A033677 Smallest divisor of n >= sqrt(n).

{1, 2, 3, 2, 5, 3, 7, 4, 3, 5, 11, 4, 13, 7, 5, 4, 17, 6, 19, 5, 7, 11, 23, 6, 5, 13, 9, 7, 29, 6, 31, 8, 11, 17, 7, 6, 37, 19, 13, 8, 41, 7, 43, 11, 9, 23, 47, 8, 7, 10, 17, ...}
Binary tree of recursive squarest factorizations
Nodes Edges
(Nodes − 1)
Levels Height
(Levels − 1)
1 Empty product 0 0
2 2 1 0 1 0
3 3 1 0 1 0
4 4 → 2 * 2 3 2 2 1
5 5 1 0 1 0
6 6 → 2 * 3 3 2 2 1
7 7 1 0 1 0
8 8 → 2 * 4 → 2 * (2 * 2) 5 4 3 2
9 9 → 3 * 3 3 2 2 1
10 10 → 2 * 5 3 2 2 1
11 11 1 0 1 0
12 12 → 3 * 4 → 3 * (2 * 2) 5 4 3 2
13 13 1 0 1 0
14 14 → 2 * 7 3 2 2 1
15 15 → 3 * 5 3 2 2 1
16 16 → 4 * 4 → (2 * 2) * (2 * 2) 7 6 3 2
17 17 1 0 1 0
18 18 → 3 * 6 → 3 * (2 * 3) 5 4 3 2
19 19 1 0 1 0
20 20 → 4 * 5 → (2 * 2) * 5 5 4 3 2
21 21 → 3 * 7 3 2 2 1
22 22 → 2 * 11 3 2 2 1
23 23 1 0 1 0
24 24 → 4 * 6 → (2 * 2) * (2 * 3) 7 6 3 2
25 25 → 5 * 5 3 2 2 1
26 26 → 2 * 13 3 2 2 1
27 27 → 3 * 9 → 3 * (3 * 3) 5 4 3 2
28 28 → 4 * 7 → (2 * 2) * 7 5 4 3 2
29 29 1 0 1 0
30 30 → 5 * 6 → 5 * (2 * 3) 5 4 3 2
Nodes Edges
(Nodes − 1)
Levels Height
(Levels − 1)
31 31 1 0 1 0
32 32 → 4 * 8 → (2 * 2) * (2 * 4) → (2 * 2) * (2 * (2 * 2)) 9 8 4 3
33 33 → 3 * 11 3 2 2 1
34 34 → 2 * 17 3 2 2 1
35 35 → 5 * 7 3 2 2 1
36 36 → 6 * 6 → (2 * 3) * (2 * 3) 7 6 3 2
37 37 1 0 1 0
38 38 → 2 * 19 3 2 2 1
39 39 → 3 * 13 3 2 2 1
40 40 → 5 * 8 → 5 * (2 * 4) → 5 * (2 * (2 * 2)) 7 6 4 3
41 41 1 0 1 0
42 42 → 6 * 7 → (2 * 3) * 7 5 4 3 2
43 43 1 0 1 0
44 44 → 4 * 11 → (2 * 2) * 11 5 4 3 2
45 45 → 5 * 9 → 5 * (3 * 3) 5 4 3 2
46 46 → 2 * 23 3 2 2 1
47 47 1 0 1 0
48 48 → 6 * 8 → (2 * 3) * (2 * 4) → (2 * 3) * (2 * (2 * 2)) 9 8 4 3
49 49 → 7 * 7 3 2 2 1
50 50 → 5 * 10 → 5 * (2 * 5) 5 4 3 2
51 51 → 3 * 17 3 2 2 1
52 52 → 4 * 13 → (2 * 2) * 13 5 4 3 2
53 53 1 0 1 0
54 54 → 6 * 9 → (2 * 3) * (3 * 3) 7 6 3 2
55 55 → 5 * 11 3 2 2 1
56 56 → 7 * 8 → 7 * (2 * 4) → 7 * (2 * (2 * 2)) 7 6 4 3
57 57 → 3 * 19 3 2 2 1
58 58 → 2 * 29 3 2 2 1
59 59 1 0 1 0
60 60 → 6 * 10 → (2 * 3) * (2 * 5) 7 6 3 2

Numbers whose binary tree of recursive squarest factorizations has k edge pairs
Sequence A-number
0 Primes: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, ...} A000040
1 Biprimes: {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, ...} A001358
2 {8, 12, 18, 20, 27, 28, 30, 42, 44, 45, 50, 52, ...} A??????
3 {16, 24, 36, 40, 54, 60, ...} A??????
4 {32, 48, ...} A??????
5 {?, ...} A??????
6 {?, ...} A??????
7 {?, ...} A??????
8 {?, ...} A??????
9 {?, ...} A??????
10 {?, ...} A??????
11 {?, ...} A??????
12 {?, ...} A??????
13 {?, ...} A??????
14 {?, ...} A??????
15 {?, ...} A??????
16 {?, ...} A??????
17 {?, ...} A??????
18 {?, ...} A??????
19 {?, ...} A??????
20 {?, ...} A??????
21 {?, ...} A??????
22 {?, ...} A??????
23 {?, ...} A??????
24 {?, ...} A??????
25 {?, ...} A??????
26 {?, ...} A??????
27 {?, ...} A??????
28 {?, ...} A??????
29 {?, ...} A??????
30 {?, ...} A??????

Numbers whose binary tree of recursive squarest factorizations has k levels (thus height k − 1)
Sequence A-number
0 {1}  
1 Primes: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, ...} A000040
2 Biprimes: {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, ...} A001358
3 {8, 12, 16, 18, 20, 24, 27, 28, 30, 36, 42, 44, 45, 50, 52, 54, 56, 60, ...} A??????
4 {32, 40, 48, 56, ...} A??????
5 {?, ...} A??????
6 {?, ...} A??????
7 {?, ...} A??????
8 {?, ...} A??????
9 {?, ...} A??????
10 {?, ...} A??????
11 {?, ...} A??????
12 {?, ...} A??????
13 {?, ...} A??????
14 {?, ...} A??????
15 {?, ...} A??????
16 {?, ...} A??????
17 {?, ...} A??????
18 {?, ...} A??????
19 {?, ...} A??????
20 {?, ...} A??????
21 {?, ...} A??????
22 {?, ...} A??????
23 {?, ...} A??????
24 {?, ...} A??????
25 {?, ...} A??????
26 {?, ...} A??????
27 {?, ...} A??????
28 {?, ...} A??????
29 {?, ...} A??????
30 {?, ...} A??????