Skip to Main content Skip to Navigation
Conference papers

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).
Complete list of metadata
Contributor : Laurent Imbert Connect in order to contact the contributor
Submitted on : Monday, May 25, 2009 - 7:46:36 PM
Last modification on : Tuesday, September 6, 2022 - 5:00:29 PM


  • HAL Id : lirmm-00387809, version 1



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



Record views