Problem Statement
Update: This problem has an update. See Edits section at the end.
Given a finite set $A \subset Z$, the Subset Sum Problem is a decision problem that answers the question Does any subset of $A$ sum to precisely $W$? This problem is known to be NP-Complete.
Geometric Sequences are sequences of the form ${a, ar, a{r^2}, \dots, a{r^k}}$ where $a$ is an initial value and $r$ the common ratio. Since $gcd(a, ar, a{r^2}, \dots, a{r^k})$ must equal one, then we have that $a = m^k$ and $r = n/m$ where $m, n$ are relatively prime integers.
If we restrict $A$ to contain the terms of a Geometric Sequence, is the Subset Sum Problem easier to solve? (It appears so.)
Approach
Given a set, the Frobenius number of the set is the largest number that cannot be represented as a weighted sum of subset of elements from the set. This occurs in the Coin Exchange Problem.
There exists a closed form formula (D. C. Ong, V. Ponomarenko., The Frobenius Number of Geometric Sequences) for a set of integers that form a geometric sequence. In the notation of their paper $g(m^k, m^{k-1}n, m^{k-2}n^2, \dots, n^k)$ is the Frobenius number of the geometric sequence. We abbreviate this as $G(m, n, k)$. Their main result is given below:
Theorem: Let $m,n,k$ be integers such that $\gcd(m,n)=1$. Then $$ g(m^k,m^{k-1}n,m^{k-2}n^2,\ldots,n^k) = n^{k-1}(mn-m-n)+\frac{(n-1)m^2(m^{k-1}-n^{k-1})}{m-n} $$
It then follows that if $W$ is lesser than $G(m, n, k)$, the subset sum decision problem can be trivially solved for sets that are geometric sequences.
Questions
Is there a different line of reasoning that would help us arrive at the same conclusion (I am essentially looking for validation of the reasoning above)?
Are there any class of problems where this result might be useful?
Edits
A flaw in the reasoning using the Frobenius number of the set was pointed out by @Servaes. The gist is that existence of the Frobenius number does not mean numbers less than that are not representable as a linear combination of the members of the set.
This pushed another line of thinking - a far simpler one.
Consider the geometric sequence $1, r, r^2, r^3, \dots, r^{n-1}$
Given W, we can simply compute the base-$r$ representation of W. By definition, this gives a weighted sum where the base-$r$ coefficients are in the range $[0, r-1]$. If we are looking for an exact subset sum solution, we are looking for coefficients to be { 0,1 } in the base-r representation. If we are looking for the multiset version, the coefficients can run the full range of $[0, r-1]$. If the base-$r$ representation is longer than $n$ digits (i.e., remainder after $n$ divisions by $r$ is greater than $r$), we subtract the value of the base-$r$ representation obtained so far ($ = W \mod r^n$) and continue with the quotient $\times$ divisor ($ = W - (W \mod r^n)$) after adjustment (see below) and keep repeating it until the remainder is zero. At the end all the partial coefficients for each radix position can be added up without any carry to get the multiset subset sum solution.
Adjusting the quotient:
($r^n = 1 + (r^n - 1))$. The 1 needs to be added to the previous partial representation and $r^n - 1$ needs to be multiplied with the quotient.
Requesting a review and validation of this.
See also
E.S. Selmer. On the linear diophantine problem of Frobenius. J. Reine Angew. Math., 293/294:1–17, 1977.)