This site is supported by donations to The OEIS Foundation.

Divisors

From OeisWiki
(Redirected from Nontrivial divisors)
Jump to: navigation, search


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


The divisors (or factors) of a positive integer
n
are the positive integers that divide
n
without leaving a remainder. For example, 4 is a divisor of 12, since 12 divided by 4 is 3 with no remainder; 5 is not a divisor of 12 because there is a remainder of 2.
The positive divisors of
n
are the zeros of the smooth (everywhere except at
x = 0
) function[1]
dn(x) = sin 2  (π  x) + sin 2π 
n
x
 , 1 ≤ xn.

Divides predicate

The divides predicate
dn
is a Boolean function which evaluates to true if and only if
d
divides
n
, otherwise evaluates to false.

Divisors of n

In the number of divisors
d (n)
column of the following table, Ramanujan’s largely composite numbers (A067128), defined to be
n
such that
d (n)   ≥   d (k)
for all
1   ≤   k < n
, are shown in bold. In the sum of divisors
σ (n)
column of the following table, the highly abundant numbers (A002093), defined as
σ (n) > σ (m)
for all
1   ≤   m < n
, are shown in bold.

Divisors of
n, n   ≥   1
.

n
Divisors Count
σ0 (n) (d (n), τ (n))

A000005
Sum
σ1(n) (σ (n))

A000203
1 {1} 1 1
2 {1, 2} 2 3
3 {1, 3} 2 4
4 {1, 2, 4} 3 7
5 {1, 5} 2 6
6 {1, 2, 3, 6} 4 12
7 {1, 7} 2 8
8 {1, 2, 4, 8} 4 15
9 {1, 3, 9} 3 13
10 {1, 2, 5, 10} 4 18
11 {1, 11} 2 12
12 {1, 2, 3, 4, 6, 12} 6 28
13 {1, 13} 2 14
14 {1, 2, 7, 14} 4 24
15 {1, 3, 5, 15} 4 24
16 {1, 2, 4, 8, 16} 5 31
17 {1, 17} 2 18
18 {1, 2, 3, 6, 9, 18} 6 39
19 {1, 19} 2 20
20 {1, 2, 4, 5, 10, 20} 6 42
21 {1, 3, 7, 21} 4 32
22 {1, 2, 11, 22} 4 36
23 {1, 23} 2 24
24 {1, 2, 3, 4, 6, 8, 12, 24} 8 60
25 {1, 5, 25} 3 31
26 {1, 2, 13, 26} 4 42
27 {1, 3, 9, 27} 4 40
28 {1, 2, 4, 7, 14, 28} 6 56
29 {1, 29} 2 30
30 {1, 2, 3, 5, 6, 10, 15, 30} 8 72
31 {1, 31} 2 32
32 {1, 2, 4, 8, 16, 32} 6 63
33 {1, 3, 11, 33} 4 48
34 {1, 2, 17, 34} 4 54
35 {1, 5, 7, 35} 4 48
36 {1, 2, 3, 4, 6, 9, 12, 18, 36} 9 91
37 {1, 37} 2 38
38 {1, 2, 19, 38} 4 60
39 {1, 3, 13, 39} 4 56
40 {1, 2, 4, 5, 8, 10, 20, 40} 8 90
41 {1, 41} 2 42
42 {1, 2, 3, 6, 7, 14, 21, 42} 8 96
43 {1, 43} 2 44
44 {1, 2, 4, 11, 22, 44} 6 84
45 {1, 3, 5, 9, 15, 45} 6 78
46 {1, 2, 23, 46} 4 72
47 {1, 47} 2 48
48 {1, 2, 3, 4, 6, 8, 12, 16, 24, 48} 10 124
49 {1, 7, 49} 3 57
50 {1, 2, 5, 10, 25, 50} 6 93
51 {1, 3, 17, 51} 4 72
52 {1, 2, 4, 13, 26, 52} 6 98
53 {1, 53} 2 54
54 {1, 2, 3, 6, 9, 18, 27, 54} 8 120
55 {1, 5, 11, 55} 4 72
56 {1, 2, 4, 7, 8, 14, 28, 56} 8 120
57 {1, 3, 19, 57} 4 80
58 {1, 2, 29, 58} 4 90
59 {1, 59} 2 60
60 {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} 12 168
        
n
Divisors Count
σ0 (n) (d (n), τ (n))

A000005
Sum
σ1(n) (σ (n))

A000203
61 {1, 61} 2 62
62 {1, 2, 31, 62} 4 96
63 {1, 3, 7, 9, 21, 63} 6 104
64 {1, 2, 4, 8, 16, 32, 64} 7 127
65 {1, 5, 13, 65} 4 84
66 {1, 2, 3, 6, 11, 22, 33, 66} 8 144
67 {1, 67} 2 68
68 {1, 2, 4, 17, 34, 68} 6 126
69 {1, 3, 23, 69} 4 96
70 {1, 2, 5, 7, 10, 14, 35, 70} 8 144
71 {1, 71} 2 72
72 {1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72} 12 195
73 {1, 73} 2 74
74 {1, 2, 37, 74} 4 114
75 {1, 3, 5, 15, 25, 75} 6 124
76 {1, 2, 4, 19, 38, 76} 6 140
77 {1, 7, 11, 77} 4 96
78 {1, 2, 3, 6, 13, 26, 39, 78} 8 168
79 {1, 79} 2 80
80 {1, 2, 4, 5, 8, 10, 16, 20, 40, 80} 10 186
81 {1, 3, 9, 27, 81} 5 121
82 {1, 2, 41, 82} 4 126
83 {1, 83} 2 84
84 {1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84} 12 224
85 {1, 5, 17, 85} 4 108
86 {1, 2, 43, 86} 4 132
87 {1, 3, 29, 87} 4 120
88 {1, 2, 4, 8, 11, 22, 44, 88} 8 180
89 {1, 89} 2 90
90 {1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90} 12 234
91 {1, 7, 13, 91} 4 112
92 {1, 2, 4, 23, 46, 92} 6 168
93 {1, 3, 31, 93} 4 128
94 {1, 2, 47, 94} 4 144
95 {1, 5, 19, 95} 4 120
96 {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96} 12 252
97 {1, 97} 2 98
98 {1, 2, 7, 14, 49, 98} 6 171
99 {1, 3, 9, 11, 33, 99} 6 156
100 {1, 2, 4, 5, 10, 20, 25, 50, 100} 9 217
101 {1, 101} 2 102
102 {1, 2, 3, 6, 17, 34, 51, 102} 8 216
103 {1, 103} 2 104
104 {1, 2, 4, 8, 13, 26, 52, 104} 8 210
105 {1, 3, 5, 7, 15, 21, 35, 105} 8 192
106 {1, 2, 53, 106} 4 162
107 {1, 107} 2 108
108 {1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108} 12 280
109 {1, 109} 2 110
110 {1, 2, 5, 10, 11, 22, 55, 110} 8 216
111 {1, 3, 37, 111} 4 152
112 {1, 2, 4, 7, 8, 14, 16, 28, 56, 112} 10 248
113 {1, 113} 2 114
114 {1, 2, 3, 6, 19, 38, 57, 114} 8 240
115 {1, 5, 23, 115} 4 144
116 {1, 2, 4, 29, 58, 116} 6 210
117 {1, 3, 9, 13, 39, 117} 6 182
118 {1, 2, 59, 118} 4 180
119 {1, 7, 17, 119} 4 144
120 {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120} 16 360

The above table gives the infinite sequence of finite sequences

{{1}, {1, 2}, {1, 3}, {1, 2, 4}, {1, 5}, {1, 2, 3, 6}, {1, 7}, {1, 2, 4, 8}, {1, 3, 9}, {1, 2, 5, 10}, {1, 11}, {1, 2, 3, 4, 6, 12}, {1, 13}, {1, 2, 7, 14}, {1, 3, 5, 15}, {1, 2, 4, 8, 16}, {1, 17}, {1, 2, 3, 6, 9, 18}, {1, 19}, {1, 2, 4, 5, 10, 20}, {1, 3, 7, 21}, {1, 2, 11, 22}, {1, 23},
{1, 2, 3, 4, 6, 8, 12, 24}, {1, 5, 25}, {1, 2, 13, 26}, {1, 3, 9, 27}, {1, 2, 4, 7, 14, 28}, {1, 29}, {1, 2, 3, 5, 6, 10, 15, 30}, ...}
A027750 Triangle (sort of...) read by rows in which row
n
list the divisors of
n
.
{1, 1, 2, 1, 3, 1, 2, 4, 1, 5, 1, 2, 3, 6, 1, 7, 1, 2, 4, 8, 1, 3, 9, 1, 2, 5, 10, 1, 11, 1, 2, 3, 4, 6, 12, 1, 13, 1, 2, 7, 14, 1, 3, 5, 15, 1, 2, 4, 8, 16, 1, 17, 1, 2, 3, 6, 9, 18, 1, 19, 1, 2, 4, 5, 10, 20, 1, 3, 7, 21, 1, 2, 11, 22, 1, 23, 1, 2, 3, 4, 6, 8, 12, 24, 1, 5, 25, 1, 2, 13, 26, 1, 3, 9, 27,
1, 2, 4, 7, 14, 28, 1, 29, 1, 2, 3, 5, 6, 10, 15, 30, ...}

Liouville’s tau generalization of sum of cubes equals square of sum

If, for each divisor
di, i ∈ {1, ..., τ (n)},
of
n
, we consider the number of divisors
τ (di )
of each
di
, we have Liouville’s tau generalization,[2][3] named after Joseph Liouville,
τ (n)
i   = 1
  
τ (di  ) 3  =    
τ (n)
i   = 1
  
τ (di  )
 2.
In particular, if
n
is a prime power
pn  − 1
, we have the well known
n
i   = 1
  
i 3  =    
n
i   = 1
  
i
 2.
From the prime power decomposition of
n
, we can obtain the former relation from the latter.

Aliquot divisors of n

The aliquot divisors (or aliquot parts, and unfortunately often referred to as proper divisors or proper parts) of
n
are the divisors of
n
less than
n
.

Strong divisors of n

The strong divisors (or strong parts) of
n
are the divisors of
n
greater than 1 (1 being a “weak divisor,” so to speak).

Nontrivial divisors of n

The nontrivial divisors (or nontrivial parts, which are referred to as proper divisors or proper parts in some texts) of
n
are the divisors of 
n
other than 1 or
n
. Every integer is divisible by 1, hence 1 is a trivial divisor; and every integer (except 
0
) is divisible by itself. Prime numbers have only trivial divisors.

For example, the nontrivial divisors of 12 are {2, 3, 4, 6}. The number 13 does not have any nontrivial divisors.

Even divisors of n

(...)

Odd divisors of n

(...)

Unitary divisors of n

A divisor
d
of
n
is a unitary divisor of
n
if
d
divides
n
exactly once (i.e.
d 2
does not divide
n
). For example, 3 is a unitary divisor of 12, since 9 does not divide 12. But 2 is not a unitary divisor of 12 because 4 also divides 12 evenly.

Even unitary divisors of n

(...)

Odd unitary divisors of n

(...)

Divisors of n!

(...) (Elaborate: Divisors of n!.)[4]

Sequences

A000005
d (n)
(also called
τ (n)
or
σ0 (n)
), the number of divisors of
n
.
{1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, ...}
A067128 Ramanujan’s largely composite numbers, defined to be
n
such that
d (n)   ≥   d (k)
for
k = 1
to
n  −  1
.
{1, 2, 3, 4, 6, 8, 10, 12, 18, 20, 24, 30, 36, 48, 60, 72, 84, 90, 96, 108, 120, 168, 180, 240, 336, 360, 420, 480, 504, 540, 600, 630, 660, 672, 720, 840, 1080, 1260, 1440, ...}
A002182 Highly composite numbers, definition (1): where
d (n)
, the number of divisors of
n
(A000005), increases to a record.
{1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160, 25200, 27720, 45360, 50400, 55440, 83160, 110880, 166320, ...}
A002183 Record values of
τ (n)
: number of divisors of
n
th highly composite number.
{1, 2, 3, 4, 6, 8, 9, 10, 12, 16, 18, 20, 24, 30, 32, 36, 40, 48, 60, 64, 72, 80, 84, 90, 96, 100, 108, 120, 128, 144, 160, 168, 180, 192, 200, 216, 224, 240, 256, 288, 320, 336, ...}
A000203
σ (n) =
sum of divisors of
n
. Also called
σ1(n)
.
{1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, 42, 32, 36, 24, 60, 31, 42, 40, 56, 30, 72, 32, 63, 48, 54, 48, 91, 38, 60, 56, 90, 42, 96, 44, 84, 78, ...}
A005100 Deficient numbers: numbers
n
such that
σ (n) < 2 n
.
{1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 21, 22, 23, 25, 26, 27, 29, 31, 32, 33, 34, 35, 37, 38, 39, 41, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 55, 57, 58, 59, ...}
A005101 Abundant numbers (sum of divisors of
n
exceeds
2 n
).
{12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100, 102, 104, 108, 112, 114, 120, 126, 132, 138, 140, 144, 150, 156, 160, 162, 168, 174, ...}
A?????? Largely abundant numbers:
σ (n)   ≥   σ (m)
for all
m < n
.
{Is this the same sequence as A002093 Highly abundant numbers or is the strong law of small numbers at play here? — Daniel Forgues 04:30, 23 May 2012 (UTC)}
A002093 Highly abundant numbers:
σ (n) > σ (m)
for all
m < n
.
{1, 2, 3, 4, 6, 8, 10, 12, 16, 18, 20, 24, 30, 36, 42, 48, 60, 72, 84, 90, 96, 108, 120, 144, 168, 180, 210, 216, 240, 288, 300, 336, 360, 420, 480, 504, 540, 600, 630, ...}
A034885 Record values of
σ (n)
.
{1, 3, 4, 7, 12, 15, 18, 28, 31, 39, 42, 60, 72, 91, 96, 124, 168, 195, 224, 234, 252, 280, 360, 403, 480, 546, 576, 600, 744, 819, 868, 992, 1170, 1344, 1512, 1560, 1680, ...}
A004394 Superabundant [or super-abundant] numbers:
n
such that
σ (n)
n
>
σ (m)
m
for all
m < n, σ (n)
being the sum of the divisors of
n
.
{1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 10080, 15120, 25200, 27720, 55440, 110880, 166320, 277200, 332640, 554400, 665280, ...}
A001065 Sum of proper divisors (or aliquot parts) of
n
: sum of divisors of
n
that are less than
n
.
{0, 1, 1, 3, 1, 6, 1, 7, 4, 8, 1, 16, 1, 10, 9, 15, 1, 21, 1, 22, 11, 14, 1, 36, 6, 16, 13, 28, 1, 42, 1, 31, 15, 20, 13, 55, 1, 22, 17, 50, 1, 54, 1, 40, 33, 26, 1, 76, 8, 43, ...}
A000396 Perfect numbers
n
:
n
is equal to the sum of the proper divisors of
n
.
{6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, 2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216, ...}
A034090 Numbers
n
such that sum of proper divisors of
n
exceeds that of all smaller numbers.
{1, 2, 4, 6, 8, 10, 12, 18, 20, 24, 30, 36, 48, 60, 72, 84, 90, 96, 108, 120, 144, 168, 180, 216, 240, 288, 300, 336, 360, 420, 480, 504, 540, 600, 660, 720, 840, 960, 1008, ...}

A034091 Records for sum of proper divisors function.

{0, 1, 3, 6, 7, 8, 16, 21, 22, 36, 42, 55, 76, 108, 123, 140, 144, 156, 172, 240, 259, 312, 366, 384, 504, 531, 568, 656, 810, 924, 1032, 1056, 1140, 1260, 1356, 1698, 2040, ...}
A007955 Product of divisors of
n
.
{1, 2, 3, 8, 5, 36, 7, 64, 27, 100, 11, 1728, 13, 196, 225, 1024, 17, 5832, 19, 8000, 441, 484, 23, 331776, 125, 676, 729, 21952, 29, 810000, 31, 32768, 1089, 1156, 1225, ...}
A034287 Numbers
n
such that product of divisors of
n
is larger than for any number less than
n
. (Equals A067128 for the 105834 terms less than 10 150.)
{1, 2, 3, 4, 6, 8, 10, 12, 18, 20, 24, 30, 36, 48, 60, 72, 84, 90, 96, 108, 120, 168, 180, 240, 336, 360, 420, 480, 504, 540, 600, 630, 660, 672, 720, 840, 1080, 1260, 1440, ...}
A007956 Product of proper divisors of
n
.
{1, 1, 1, 2, 1, 6, 1, 8, 3, 10, 1, 144, 1, 14, 15, 64, 1, 324, 1, 400, 21, 22, 1, 13824, 5, 26, 27, 784, 1, 27000, 1, 1024, 33, 34, 35, 279936, 1, 38, 39, 64000, 1, 74088, 1, ...}

A034288 Product of proper divisors is larger than for any smaller number.

{1, 4, 6, 8, 10, 12, 18, 20, 24, 30, 36, 48, 60, 72, 84, 90, 96, 108, 120, 168, 180, 240, 336, 360, 420, 480, 504, 540, 600, 630, 660, 672, 720, 840, 1080, 1260, 1440, 1680, ...}

Divisor functions in computer algebra systems

The functionality is available in PARI/GP as divisors(n) and Divisors[n] in Mathematica.

Generalization to other integral domains

Much of the foregoing has focused on
ℤ +
, the domain of positive integers, but the concept can readily be extended to other integral domains. Let’s say
D
is some domain of algebraic integers, and
n
and
d
are in that domain. If
n
d
D
also, then
d
is a divisor of
n
. For example, in
ℤ [
2  3
]
, we see that
1 +
2  3
is a divisor of 2 since
2
1 +
2  3
=  − 1 +
2  3
. But it is not a divisor of 7 since
7
1 +
2  3
=  −  
7
2
+
7
2  3
2
∉ ℤ [
2  3
]
.

See also

Notes

  1. Online plot of (sin(pi*x))^2 + (sin(pi*72/x))^2.
  2. Peter D. Taylor, Sum of Cubes.
  3. Edward Barbeau and Samer Seraj, “Sum of Cubes is Square of Sum,” arXiv:1306.5257 [math.NT], 2013.
  4. Needs elaboration (Divisors of n!).