Granville numbers

This article needs more work.

Please help by expanding it!

The Granville numbers or

S

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

Definitions

Granville set S

In 1996, Andrew Granville proposed the following construction of the set

S

, involving the sum of proper divisors of natural numbers.

Let

${\mathcal {S}}_{0}=\{\},\,$

and for

n ∈ ℕ, n   ≥   1

, if

$\left\{\sum _{\stackrel {\ d\,\in \,{\mathcal {S}}_{n-1}}{d\,|\,n}}{d}\right\}\leq n\,$

then

${\mathcal {S}}_{n}={\mathcal {S}}_{n-1}\cup \{n\},\,$

otherwise

${\mathcal {S}}_{n}={\mathcal {S}}_{n-1},\,$

and the Granville set

S

is defined as

${\mathcal {S}}:=\lim _{n\to \infty }{\mathcal {S}}_{n}.\,$

A?????? Granville set

S

involved in the definition of

S

-perfect numbers.

{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, ...}

A181487 Complement

S

of the Granville set

S

(contains the S -abundant numbers).

{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, ...}

A?????? Characteristic function

χS

of the Granville set

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, ...}

It is necessary to understand the membership of

S

first. A number is in that set if the sum of its proper divisors (including 1 but excluding the number itself) which are in

S

is less than or equal to the number. To get past the confusing clutter of notation usually used to describe

S

, the crystal clear explanation 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

  S

  . (With

  n

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

  S

  , their sum is still less than 

  n

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

  S

  . (Whether or not any divisors of

  n

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

  S

  is less than or equal rather than just less than.)
• Some abundant numbers are in

  S

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

  S

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

  S

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

  S

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

  S

  , the sum of its divisors in

  S

  is 25 rather than 55, and thus 36 is in

  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

is the intersection of the set of proper divisors of

n

and the Granville set

S

.

Sum of S -divisors of n

The sum

sS (n)

of

S

-divisors of

n, n   ≥   1,

is given by

$s_{\mathcal {S}}(n)=\sum _{\ d\,\in \,{\mathcal {S}}_{n-1},\ d\,|\,n}{d},\,$

or equivalently

$s_{\mathcal {S}}(n)=\sum _{d\,|\,n,\ d\,<\,n}{{\chi _{s}}(d)\cdot d},\,$

where

χS (n)

is the characteristic function of the Granville set S.

S -perfect numbers (Granville numbers)

A Granville number or

S

-perfect number is a positive integer

n

such that the sum of its S -divisors (proper divisors in the set

S

) is equal to

n

(Cf. A??????, A181487 for the complement of

S

)

$s_{\mathcal {S}}(n)=n,\ n\geq 1.\,$

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.

Theorem.

Any even number

n

that is a 2-perfect number is also

S

-perfect.

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

(2 p  −  1)  ⋅  2 p  − 1

, with

p

prime and

q = 2 p  −  1

a Mersenne prime, it follows that:

a) the prime divisor

q

of

n

is deficient (being quasi-1-perfect, since

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

) is in

S

;

b) the powers of two,

2 m, 0   ≤   m   ≤   p  −  1

, that divide

n

are also deficient (being almost-2-perfect, since

σ (2 m) = 2 m +1  −  1, s (2 m) = σ (2 m)  −  2 m = (2 m +1  −  1)  −  2 m = 2 m  −  1

); and

c) those proper divisors

d = 2 m q, 0 < m < p  −  1,

that are the product of a positive power of two and the Mersenne prime

q = 2 p  −  1

are also deficient (since

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

, since

1 < m + 1 < p

)

Therefore, all of

n

’s proper divisors are in

S

, and since they add up to

n

itself,

n

is therefore

S

-perfect. □

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 in

S

); the powers of 2 (namely 1, 2, 4, 8, 16) are almost-2-perfect and are thus also in

S

; as well as 31 times each positive power of two below 16 (62, 124, 248) with their sums of proper divisors being 34, 100, 232. We have already established that 496 is a 2-perfect number, and now that we have established that all of its proper divisors are in

S

, it follows that 496 is

S

-perfect. More interesting perhaps are those abundant numbers that turn out to be

S

-perfect since the excluded divisors turn out to add up to the number’s abundance. Some such numbers are 24, 96, 126, 224, 384, 1536, 1792, 6144. See A118372 for the Granville numbers, including those that are also in A000396. Whereas no odd 2-perfect numbers are known, there are odd Granville numbers, such as the 28th: 22528935. After 36, the sequence of abundant but

S

-deficient numbers continues 40, 54, 60, 100, 112, 132, 140, 144, 156, 160, 168, 176, 198, ...

S -deficient numbers

By definition of the Granville set

S

, an element of

S

which is not a

S

-perfect number is a

S

-deficient number, since the

S

-abundant numbers are the elements of the complement

S

of the Granville set.

S

-deficient numbers are numbers

n

such that

${\begin{array}{l}\displaystyle {S_{s}(n)<n,\ n\geq 1.}\end{array}}$

A??????

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, 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, ...}

The deficient numbers (A005100) are a subset of the

S

-deficient numbers. Among the

S

-deficient numbers, the deficient numbers (A005100) (shown in black below) constitute a subset, and the abundant

S

-deficient numbers (A??????) (shown in red) constituting a sparse subset

{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 complement

S

of the Granville set

S

.

S -multiperfect numbers

Among the S -abundant numbers, as a generalization of

S

-perfect number is that of

S

-multiperfect number

$s_{s}(n)=kn,\ k\geq 2,\ n\geq 1.\,$

Sequences

Perfect S -perfect numbers

The even perfect numbers (A000396) being

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

the even perfect numbers constitute a sparse subset (shown in red below) of the

S

-perfect 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, ...}

If odd perfect numbers happen to exist, then depending on their forms, these could be either

S

-deficient numbers or

S

-perfect numbers...

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 the

S

-deficient numbers). A?????? Abundant

S

-perfect numbers.

{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

A005100 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 are

S

-deficient numbers (the even perfect numbers being a subset of the

S

-perfect numbers). If odd perfect numbers happen to exist, then depending on their forms, these could be either

S

-deficient numbers or

S

-perfect numbers...

Abundant S -deficient numbers

A?????? Abundant

S

-deficient numbers.

{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}]) == # &
           ]

References

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