Given positive integers $a, d, n$ with $gcd(a, d) = 1$, consider the Arithmetic Sequence
$a, a + d, a + 2d, \dots, a + nd$
Let $A$ be the set consisting this sequence.
The Frobenius number $g$, of this arithmetic sequence is given by the closed form formula:
$g = \lfloor { a - 2 \over n } \rfloor a + d(a - 1)$
The Frobenius number of the arithmetic sequence is the largest number that cannot be represented as a weighted sum of the members the sequence. The weights $w_i$ are positive integers and zero (i.e. $w_i \in W$, the set of whole numbers).
i.e., $g \ne \sum_{i} w_i x_i $, where $x_i \in A, w_i \in W$
The Frobenius number occurs in the Frobenius Coin Problem. The formula above is also available in the same Wikipedia reference in section titled Frobenius numbers for special sets.
For every Arithmetic Sequence, there is a Frobenius number that can be computed using the formula given above.
I am looking at the converse. Given positive integer $g$, find the arithmetic sequence defined by $a, d, n$ such that $g$ is its Frobenius number with
- maximal $n$ i.e., the longest sequence (or)
- smallest $d$ (or)
- minimal $a + d$
(I don't know if one of these implies the other)
Approach
We know that the trivial two member arithmetic sequence $a, a+d$ always exists for any $g$. This is because we can always solve the linear Diophantine equation $aX + (a-1)Y = g$ using the Extended Euclidean algorithm as $gcd(a, a-1) = 1$. We also know that if a solution exists for $X, Y$, there are an infinite number of solutions. We can solve for $n$ by substituting $\lfloor { a - 2 \over n } \rfloor = X$ and $d = Y$.
So, we have an oracle that can give us $d, n$ dependent on $g, a$.
My heuristic approach is to use the given $g$ and choose various $a$ and then select the $a, d, n$ that meets the criteria. I know this does not give me the optimal solutions for any given $g$.
Is there a way to determine the optimal solution(s)?
Let $g$ be an integer and let $(a,d,n)$ be an integral solution to $$g=\left\lfloor\frac{a-2}{n}\right\rfloor a+d(a-1),\tag{1}$$ with $a,d,n>0$. First note that $d(a-1)\geq0$ and $\lfloor\tfrac{a-2}{n}\rfloor\geq-1$, with equality if and only if $a=1$ in both cases. It follows that no such integral solutions exist for $g\leq-1$. For $g=-1$ we must have $a=1$, and then any choice of $d$ and $n$ yields $g=-1$. Of course $g=0$ is impossible, so from here on we consider only the case where also $g$ is positive. Note that then $a>1$.
For every $g>0$ there is no maximum to the values that $n$ can take. After all, for $a=2$ and $d=g$ equation $(1)$ simplifies to $g=d$. In particular we see that there exists a solution for every positive integer $n$.
For every $g>0$ the minimal value of $d$ is $d=1$. For $d=1$ equation $(1)$ becomes $$g=\left\lfloor\frac{a-2}{n}\right\rfloor a+a-1,$$ so taking any $n>a-2$ this further simplifies to $g=a-1$. So for every positice integer $c$ the triple $$(a,d,n)=(g+1,1,g-1+c),$$ is a solution to $(1)$ with $d$ minimal. This shows that there is still no maximum to the values that $n$ can take.
Minimizing $a+d$ seems to be difficult, though. Here is a table of the minimal values $m$ of $a+d$ for small values of $g$: $$\begin{array}{r|rrrrrrrrrrrrr} g&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\ \hline m&2&3&4&5&5&4&6&5&7&6&6&5&8&7&6&9&8&7&10&6&8\\ \end{array}$$ It does not seem to match anything in OEIS.