## 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