https://hal-lirmm.ccsd.cnrs.fr/lirmm-00387809Imbert, LaurentLaurentImbertARITH - Arithmétique informatique - LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - UM - Université de Montpellier - CNRS - Centre National de la Recherche ScientifiquePIMS - Pacific Institute for the Mathematical Sciences - University of Calgary - CNRS - Centre National de la Recherche ScientifiqueStrictly Chained (p,q)-ary PartitionsHAL CCSD2009[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO][INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Imbert, Laurent2009-05-25 19:46:362022-09-06 17:00:292009-05-26 10:50:58enConference papers1A 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).