There are no approved revisions of this page, so it may
not have been
reviewed.
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
minimizes
and
.
It corresponds to the squarest (least oblong) integral rectangle with area
. This has minimal semi-perimeter (
A063655), since
is minimal when
.
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
is
| nodes(n) = 1 + sum(nodes(i), nodes(j)). |
The number of levels of the binary tree of recursive squarest factorizations of
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??????
|
