Coprime Partitions

Let F(N,k) denote the number of distinct partitions of N into exactly
k mutually coprime parts.  Obviously F(N,1)=1 for all N.  Also, we have
F(N,2) = phi(N)/2 for all N, where phi() is the Euler totient function.

The sequence of values F(N-1+j,j) with j=1,2,... for every N eventually
reaches saturation.  For example, taking N=36 we have

                       F(36,1) =  1
                       F(37,2) = 18  =  phi(37)/2
                       F(38,3) = 49
                       F(39,4) = 77
                       F(40,5) = 88
                       F(41,6) = 89
                       F(42,7) = 89
                       F(43,8) = 89
                           etc

All subsequent values in this sequence are 89, which is the saturation
value reached at j=6.  For j>6 there are no essentially new partitions
in the sequence F(36-1+j,j).  We simply augment each partition in the
previous set with an isolated part equal to 1.

For any N let s(N) denote the saturation index of N, and let q(N)
denote the saturation value.  Thus in the above example we have s(36)=6 
and q(36)=89.  Here is a tabulation of s(N) and q(N) for N=1 to 50:

  N   s  q      N   s  q      N   s  q      N   s   q      N   s   q
  -   -  -     --   -  -     --   -  -     --   -   -     --   -   -
  1   1  1     11   2  2     21   3  7     31   4  19     41   5  31
  2   1  1     12   3  8     22   4 31     32   5  68     42   6 139
  3   1  1     13   3  4     23   4  8     33   4  18     43   5  43
  4   2  2     14   4  9     24   5 30     34   5  89     44   6 184
  5   1  1     15   2  4     25   4 12     35   5  21     45   5  37
  6   2  3     16   4 16     26   5 40     36   6  89     46   6 221
  7   2  2     17   3  4     27   3 10     37   4  29     47   5  47
  8   3  4     18   4 17     28   5 58     38   6 119     48   6 220
  9   2  2     19   3  7     29   4 12     39   5  24     49   5  59
 10   3  7     20   4 20     30   5 53     40   6 147     50   6 284

The values of q(N) can be regarded as a sort of "ultimate" totient 
function, because they represent the number of coprime partitions of
N-1+j into exactly j parts for all j > s(N).

Notice that if N is the smallest integer such that s(N)=k then N-1+s(N) 
is the sum of the first k primes.  For example, the first occurrence of
s(N)=5 in the above table is for N=24, so we have 

         (24-1+5)  =  28  =  2 + 3 + 5 + 7 + 11

This just expresses the fact that the smallest saturated partition into 
k coprime parts is just the smallest partition into k distinct primes.

The Euler totient function 2F(N,2) occurs in certain number-theoretic
applications such as the generalized version of Fermat's little theorem
a^2F(N,2) = a (mod N).  Does anyone know of analagous theorems involving
the higer order totients F(N,k), k>2?  Or involving q(N)?

 Et i'efpere que nos neueux me fcauront gre', non feulement des
 chofes que iay icy expliquees; mais auffy de celles que iay omifes
 volontairerement, affin de leur laiffer le plaifir de les inuenter.

Return to MathPages Main Menu