Strictly Chained (p,q)-ary Partitions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2009

Strictly Chained (p,q)-ary Partitions

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).
No file

Dates and versions

lirmm-00387809 , version 1 (25-05-2009)

Identifiers

  • HAL Id : lirmm-00387809 , version 1

Cite

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

Share

More