Subsequence sums: Direct and inverse problems

JOURNAL OF NUMBER THEORY

卷:148

Article

Mistri, Raj Kumar¹  Pandey, Ram Krishna²  Praksh, Om¹ 

[1] Indian Inst Technol, Dept Math, Patna 800013, Bihar, India

[2] Indian Inst Technol, Dept Math, Roorkee 247667, Uttar Pradesh, India

关键词: Subsequence sums;    Subset sums;    Direct problems;    Inverse problems;   

DOI  :  10.1016/j.jnt.2014.09.010

来源: Elsevier

【 摘 要 】

Let A = (a(0),...,a(0),(r0 copies)a(1),...,a(1),(r1 copies)...,a(k-1),...,a(k-1rk-1 copies)) be a finite sequence of integers with k distinct terms, denoted alternatively by (a(0), a(1),...,a(k-1))(r) over bar, where a(0) < a(1) < ... < a(k-1), <(r)over bar> = (r(0),r(1),...,r(k-1)), r(i) >= 1 for i = 0,1,...,k - 1. The sum of all the terms of a subsequence of length at least one of the sequence A is said to be a subsequence sum of A. The set of all subsequence sums of A is denoted by S((r) over bar, A). The direct problem for subsequence sums is to find the lower bound for vertical bar S((r) over bar, A)vertical bar in terms of the number of distinct terms in the sequence A. The inverse problem for subsequence sums is to determine the structure of the finite sequence A of integers for which vertical bar S((r) over bar, A)vertical bar is minimal. In this paper, both the problems are solved and some well-known results for subset sum problem are obtained as corollaries of the results for subsequence sum problem. (C) 2014 Elsevier Inc. All rights reserved.

【 授权许可】

Free