This site is supported by donations to The OEIS Foundation.

# Granville numbers

**Granville numbers**or

**are positive integers which meet certain criteria in regards to their divisors. The first 32 Granville numbers are listed in A118372.**

-perfect numbers

S |

## Definitions

### Granville set S

In 1996, Andrew Granville proposed the following construction of the setS |

^{[1]}involving the sum of proper divisors of natural numbers.

Let

n ∈ ℕ, n ≥ 1 |

then

otherwise

S |

S |

S |

- {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 67, 68, 69, 71, 73, 74, 75, 76, 77, 79, 81, 82, 83, ...}

S |

S |

- {12, 18, 20, 30, 42, 48, 56, 66, 70, 72, 78, 80, 84, 88, 90, 102, 104, 108, 114, 120, 138, 150, 162, 174, 180, 186, 192, 196, 200, 210, 220, 222, 246, 252, 258, 260, 264, 270, 272, 280, 282, 288, 294, 300, 304, 308, 312, 318, 320, 330, 336, 340, 354, 364, 366, ...}

χS |

S |

- {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, ...}

S |

S |

S |

^{[2]}from William Marshall, using familiar number theory terminology, is now paraphrased (with elaborations from others in parentheses):

- All deficient numbers (A005100) are forcibly S -deficient numbers and are thus in

. (WithS

deficient, if we can’t exclude any of its divisors for not being in*n*

, their sum is stillS *less than*

itself.)*n* - All 2-perfect numbers (A000396) are in

. (Whether or not any divisors ofS

can be excluded is irrelevant at this juncture, since the condition of membership in*n*

isS *less than or equal*rather than just*less than*.) - Some abundant numbers are in

if we can exclude enough of their divisors for not being inS

such that the sum of the remaining S -divisors isS *less than or equal*to the number itself. For example, with 12 or 18, their proper divisors are all in

, and thus they remain S -abundant numbers, so it means that 12 and 18 themselves are not inS

. (This has consequences for multiples of 12 or 18, like 36: since 12 and 18 are not inS

, the sum of its divisors inS

is 25 rather than 55, and thus 36 is inS

).S

It should be clear at this point that in the case of numbers that are not squarefree, i.e. squareful numbers, it is more efficient to examine the smaller divisors first, for if we look at the larger divisors first we must then look at those smaller divisors that divide the larger divisors.

### S -divisors of *n*

The set of S -divisors of n |

n |

S |

#### Sum of S -divisors of *n*

The sum sS (n) |

S |

n, n ≥ 1, |

or equivalently

χS (n) |

### S -perfect numbers (Granville numbers)

A**Granville number**or

**is a positive integer**

-perfect number

S |

n |

S |

n |

S |

A118372 S -perfect numbers (Granville numbers).

- {6, 24, 28, 96, 126, 224, 384, 496, 1536, 1792, 6144, 8128, 14336, 15872, 24576, 98304, 114688, 393216, 507904, 917504, 1040384, 1572864, 5540590, 6291456, 7340032, 9078520, 16252928, 22528935, 25165824, 33550336, 56918394, 58720256, ...}

The mathematicians Jean-Marie De Koninck and Aleksandar Ivić first pondered these numbers in December 1996 at the suggestion of Andrew Granville.

For example, with 496, an even 2-perfect number that is the product of 2 4 and 31, we see that its prime divisors, 2 and 31, are both clearly deficient, since they are quasi-1-perfect, (and thus inTheorem.

Any even numberthat is a 2-perfect number is also

n-perfect.

S Proof.From Euler’s proof of the proposition that even 2-perfect numbers must be of the form, with

(2 p− 1) ⋅ 2p− 1prime and

pa Mersenne prime, it follows that:

q= 2p− 1

- a) the prime divisor
of

qis deficient (being quasi-1-perfect, since

n) is in

σ(q) =q+ 1,s(q) =σ(q) −q= (q+ 1) −q= 1;

S

- b) the powers of two,
, that divide

2 m, 0 ≤m≤p− 1are also deficient (being almost-2-perfect, since

n); and

σ(2m) = 2m+1 − 1,s(2m) =σ(2m) − 2m= (2m+1 − 1) − 2m= 2m− 1Therefore, all of

- c) those proper divisors
that are the product of a positive power of two and the Mersenne prime

d= 2mq, 0 <m<p− 1,are also deficient (since

q= 2p− 1, since

σ(d) =σ(2mq) =σ(2m)σ(q) = (2m+1 − 1) (q+ 1) = (2m+1 − 1) 2p< (2p− 1) 2p= 2d)

1 < m+ 1 <p’s proper divisors are in

n, and since they add up to

S itself,

nis therefore

n-perfect. □

S

S |

S |

S |

S |

S |

S |

### S -deficient numbers

By definition of the Granville setS |

S |

S |

S |

S |

S |

S |

n |

S |

- {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, 36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 67, 68, 69, 71, 73, 74, 75, 76, 77, 79, 81, 82, 83, ...}

S |

S |

S |

- {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, 36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 67, 68, 69, 71, 73, 74, 75, 76, 77, 79, 81, 82, 83, ...}

### S -abundant numbers

The S-abundant numbers are the elements of the complementS |

S |

#### S -multiperfect numbers

Among the S -abundant numbers, as a generalization ofS |

S |

## Sequences

#### Perfect S -perfect numbers

The even perfect numbers (A000396) being

- {6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, 2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216, ...}

S |

- {6, 24, 28, 96, 126, 224, 384, 496, 1536, 1792, 6144, 8128, 14336, 15872, 24576, 98304, 114688, 393216, 507904, 917504, 1040384, 1572864, 5540590, 6291456, 7340032, 9078520, 16252928, 22528935, 25165824, 33550336, 56918394, 58720256, ...}

S |

S |

#### Abundant S -perfect numbers

S -perfect numbers which are not perfect numbers are a subset of the abundant numbers (since the deficient numbers constitute a subset of theS |

S |

- {24, 96, 126, 224, 384, 1536, 1792, 6144, 14336, 15872, 24576, 98304, 114688, 393216, 507904, 917504, 1040384, 1572864, 5540590, 6291456, 7340032, 9078520, 16252928, 22528935, 25165824, 56918394, 58720256, ...}

Among the abundant numbers (A005101), the S -perfect numbers (A??????) (shown in red below) are sparse

- {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, 176, 180, 186, 192, 196, 198, 200, 204, 208, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264, 270, ...}

#### Deficient S -deficient numbers

- {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, 61, 62, 63, 64, 65, 67, 68, 69, 71, 73, 74, 75, 76, 77, 79, 81, 82, 83, ...}

#### Perfect S -deficient numbers

There are no even perfect numbers which areS |

S |

S |

S |

#### Abundant S -deficient numbers

A?????? AbundantS |

- {36, 40, 54, 60, 100, 112, 132, 140, 144, 156, 160, 168, 176, 198, ...}

Among the abundant numbers (A005101), the S -deficient numbers (A??????) (shown in red below) are

- {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, 176, 180, 186, 192, 196, 198, ...}

## Programs

### Programs for S -perfect numbers

#### C program for S -perfect numbers

// Contribution from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Oct 28 2010. #include <stdlib.h> #include <stdio.h> #define MAX_SIZE_SSET 1000000 int main(int argc, char* argv[]) { int Sset[MAX_SIZE_SSET] ; int Ssetsize = 1; Sset[0] = 1 ; for(int n = 2; n < MAX_SIZE_SSET; n++) { int dsum = 0 ; for(int i = 0; i < Ssetsize; i++) { if( n % Sset[i] == 0 && Sset[i] < n) dsum += Sset[i] ; if (dsum > n || Sset[i] >= n) break ; } if(dsum <= n) { if(dsum == n) printf("%d\n", n) ; Sset[Ssetsize++ ] = n ; } } }

#### Haskell program for S -perfect numbers

-- Contribution from Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Oct 28 2010. sPerfect :: Int -> [Int] -> [Int] sPerfect n ss = case compare (sum $ filter ((== 0) . mod n) $ takeWhile (< n) ss) n of LT -> sPerfect (n+1) (n:ss) EQ -> n:sPerfect (n+1) (n:ss) GT -> sPerfect (n+1) ss a118372_list = sPerfect 1 [] -- eop.

#### Mathematica program for S -perfect numbers

With searchMax set to ten thousand, these computations should only take a few seconds.

(* Contribution from Alonso del Arte (alonso.delarte(AT)gmail.com, Nov 3 2010 *) searchMax = 10001; S = {1}; For[i = 2, i < searchMax, i++, If[(Plus @@ Table[Divisors[i][[n]] * Boole[MemberQ[S, Divisors[i][[n]]]], {n, 1, Length[Divisors[i]] - 1}]) <= i, S = Flatten[Append[S, i]] ] ]; Take[S, 100] SPerfect = Select[Range[searchMax - 1], (Plus @@ Table[Divisors[#][[n]] * Boole[MemberQ[S, Divisors[#][[n]]]], {n, 1, Length[Divisors[#]] - 1}]) == # & ]

## Notes

- ↑ Jean-Marie De Koninck and Aleksandar Ivić, “On a sum of divisors problem,”
*Publications de l’Institut Mathématique,*New Series, Vol. 64, (1998), pp. 9–20. - ↑ William Marshall, Who understands Granville numbers?, posting to SeqFan on Oct 28 2010

## References

- Jean-Marie De Koninck,
*Those Fascinating Numbers*, translated by the author. American Mathematical Society (2008) p. 40.