Journal of Integer Sequences, Vol. 17 (2014), Article 14.3.4

Addition Chains Meet Postage Stamps: Reducing the Number of Multiplications


Jukka Kohonen and Jukka Corander
Department of Mathematics and Statistics
P. O. Box 68
FI-00014 University of Helsinki
Finland

Abstract:

We introduce stamp chains. A stamp chain is a finite set of integers that is both an addition chain and an additive 2-basis, i.e., a solution to the postage stamp problem. We provide a simple method for converting known postage stamp solutions of length k into stamp chains of length k + 1. Using stamp chains, we construct an algorithm that computes u(xi) for i = 1, ... , n in less than n - 1 multiplications, if u is a function that can be computed at zero cost, and if there exists another zero-cost function v such that v(a, b) = u(ab). This can substantially reduce the computational cost of repeated multiplication, as illustrated by application examples related to matrix multiplication and data clustering using subset convolution. In addition, we report the extremal postage stamp solutions of length k = 24.


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequences A001212 A234941.)


Received October 24 2013; revised version received February 3 2014. Published in Journal of Integer Sequences, February 15 2014.


Return to Journal of Integer Sequences home page