Strictly Chained (p,q)-ary Partitions

Laurent Imbert 1, 2
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A partition of an integer n is a non-increasing sequence of positive integers, called parts, summing up to n, possibly subject to one or more constraints. For instance, one may want the parts to be distinct, odd, prime, powers of some integer, etc. Strictly chained partitions are finite sequences of integers that decrease for the divisibility order. In other words, partitions of the form n = a1 + a2 + ... + ak into distinct positive integers a1, ..., ak such that ak | ak-1 | ... | a1. If p(n) denotes the number of strictly chained partitions of n, Erdös and Loxton proved that the sum $P(x) = \sum_{1 \leq n \leq x} p(n)$ function behaves like $cx^\rho$, where c is an unknown constant and $\rho$ is the unique root of $\zeta(\rho) = 2, where $\zeta$ is the Riemann zeta function. In this talk, we discuss a special case of this type of partitions. We consider strictly chained (p,q)-ary partitions, i.e., partitions with distinct parts of the form paqb, with the further constraint that each part is a multiple of the following one. For sake of simplicity, we further assume that p and q are relatively prime integers greater than 1. This work arose from recent developments on so-called double-base chains, in particular their use in speeding-up exponentiation in various groups. We investigate several problems including those of generating, encoding and counting these partitions. We also give some results on the length (the number of parts) of the shortest partitions of that type. The special case min(p,q)=2 will be given a special attention, in particular the case (p,q)=(2,3).
Type de document :
Communication dans un congrès
Alberta Number Theory Day, 2009, Calgary, Canada. 2009, 〈〉
Liste complète des métadonnées
Contributeur : Laurent Imbert <>
Soumis le : lundi 25 mai 2009 - 19:46:36
Dernière modification le : jeudi 11 janvier 2018 - 06:26:07


  • HAL Id : lirmm-00387809, version 1



Laurent Imbert. Strictly Chained (p,q)-ary Partitions. Alberta Number Theory Day, 2009, Calgary, Canada. 2009, 〈〉. 〈lirmm-00387809〉



Consultations de la notice