The Frobenius problem for special progressions

1.   Introduction

Let $n$ be a positive integer greater than 1. For a given set $S = \{a_1, a_2, \ldots, a_n\}$ with each $a_i$ being a positive integer and $\gcd(S): = \gcd(a_1, a_2, \ldots, a_n) = 1$, define $L(S)$ to be the set of integers represented as nonnegative integer linear forms of integers in $S$; that is,

where $\mathbb{N}$ represents the natural number set containing zero. It is well known that (see, for example, Theorem 1.16 in ^[1]) for any positive integer $z$ if

then $z$ belongs to $L(S)$. It follows that there are finitely many nonnegative integers that are not in $L(S)$. So, if $L^c(S): = \mathbb{N}\setminus L(S)$, then $L^c(S)$ is a finite set. Define

where $|\cdot|$ denotes the size of a set. Perhaps Sylvester was the first person who asked to determine $g(S)$ and $n(S)$. He also proved that

During the early part of the twentieth century, Frobenius raised the same problem in his lectures (according to ^[2]). Frobenius was largely instrumental in giving this problem the early recognition, and it was after him that the problem was named. This problem of determining $g(S)$ is called the Frobenius problem and $g(S)$ is the Frobenius number. The Frobenius problem has a rich and long history, with several applications, extensions and connections to several areas of research. A comprehensive survey covering all aspects of the problem was given by Ramíres-Alfonsín ^[3].

Exact determination of the $g(S)$ and $n(S)$ is a difficult problem in general. There are only a few cases where the $g(S)$ and $n(S)$ have been exactly determined for any $n$ variables. Table 1 shows some of the results in the case of $S$ being special progressions, which were obtained by researchers over the past few decades.

Here, $√$ means that the responding result was obtained. The results in the table show that scholars were gradually attacking the Frobenius problem for more general sets. For some very recent development aspects of this field, one can refer to ^[11,12,13].

For any nonnegative integer $c$, let

where $k, a, b, d$ and $h$ are positive integers with $\gcd(a, d) = 1$. It is natural to consider the Frobenius problem for $S_c$. In the paper, we present formulas for $g(S_c)$ and $n(S_c)$ for all sufficiently large values of $d$ in the condition that $c$ is a multiple of $a$ or a multiple of $d$.

In order to state our theorem well, let us first define some notations. Let $b, k$ and $u$ be nonnegative integers with $b\ge 2$ and $k\ge 1$. For any positive integer $x$, define two sequences of nonnegative integers, denoted by $\{q_i(x)\}_{i = 0}^{k}$ and $\{r_i(x)\}_{i = 0}^{k}$, as follows:

where $0\le r_i(x)\le b^i+ui-1$ for each $1\le i\le k$ and $r_0(x) = 0$. From Euclidean division, we know that $\{q_i(x)\}_{i = 0}^{k}$ and $\{r_i(x)\}_{i = 0}^{k}$ are uniquely determined by $x$, so they are well defined. It is immediate that

and

i.e., $0\le q_i(x)\le b$ for any $1\le i\le k-1$. In particular, when $u = 0$, we use $\{\overline{q}_i(x)\}_{i = 0}^{k}$ and $\{\overline{r}_i(x)\}_{i = 0}^{k}$ to replace $\{q_i(x)\}_{i = 0}^{k}$ and $\{r_i(x)\}_{i = 0}^{k}$, respectively. Thus,

and

is the $b$-adic representation of $\overline{r}_m(x)$. Let

where $v$ is a nonnegative integer.

Now, we can report the main theorem as follows.

Theorem 1.1. Let $k, a, b, d$ and $h$ be positive integers with $\gcd(a, d) = 1$ and $b\ge 2$. For any nonnegative integer $c$, let $S_c: = \{a, ha+d, ha+c+bd, ha+2c+b^2d, \ldots, ha+kc+b^kd\}$. The following statements are true.

(a) If $c = ud$ for a nonnegative integer $u$ and $d\ge ah(k(b-1)+u)$, then

and

(b) If $c = va$ for a nonnegative integer $v$ with $v\le b-1$ and $d\ge \frac{1}{2}akh(b-1)(2+(k-1)v)$, then

and

where $M_i = \frac{1}{2}b^i\left\lfloor\frac{a-1}{b^i}\right\rfloor(\left\lfloor\frac{a-1}{b^i}\right\rfloor-1) +\left\lfloor\frac{a-1}{b^i}\right\rfloor(a-b^i\left\lfloor\frac{a-1}{b^i}\right\rfloor)$.

Here, and are defined as (1.3).

Clearly, Theorem 1.1 extends a result of Tripathi ^[10]. The paper is organized as follows. First, in Section 2, two key lemmas are given. Second, in Section 3, we present the proof of Theorem 1.1. Finally, in Section 4, another possible direction of the generalizations of $S$ for the Frobenius problem is introduced, which can be served as a future research for the interested.

2.   Lemmas

Let $S$ be any given finite set of positive integers with $\gcd(S) = 1$. Let $a$ be a positive integer of $S$. For any integer $x$ with $1\le x\le a-1$, denote $\langle x\rangle$ to be the residue class of integers congruent to $x$ modulo $a$. Let $\boldsymbol{m}(S, x)$ represent the least positive integer in $L(S)\cap \langle x\rangle$. Brauer and Shockley ^[14] obtained the following results, which give $g(S)$ and $n(S)$ from $\boldsymbol{m}(S, x)$.

Lemma 2.1. Let $S$ be any finite set of positive integers with $\gcd(S) = 1$. For any $a\in S$,

The second lemma presents results of $\min (L(S)\cap \langle x\rangle)$.

Lemma 2.2. Let $c$ be a fixed nonnegative integer, $k, a, b, d$ and $h$ be positive integers with $\gcd(a, d) = 1$ and $b\ge 2$. Let $S_c = \{a, ha+d, ha+c+bd, ha+2c+b^2d, \ldots, ha+kc+b^kd\}$. For any integer $x$ with $1\le x\le a-1$, let $\boldsymbol{m}(x): = \min\left(L(S_c)\cap \langle dx\rangle\right)$, where $\langle dx\rangle$ denotes the residue class of integers congruent to $dx$ modulo $a$. The following results are derived.

(a) if $c = ud$ for a nonnegative integer $u$, then for any positive integer $x$ with $x\le a-1$ we have

In particular, if $d\ge h\left(k(b-1)+u-\left\lfloor\frac{a}{b^k+uk}\right\rfloor\right)$ with $\gcd(a, d) = 1$, then

(b) if $c = va$ for a nonnegative integer $v$ with $v\le b-1$, then for any positive integer $x$ with $x\le a-1$ we have

Moreover, if $d\ge \frac{1}{2}kh(b-1)(2+(k-1)v)-h(1+kv)\left\lfloor\frac{a}{b^{k}}\right\rfloor$, then

Here, and are defined as (1.3).

Proof. Let $x$ be a positive integer with $x\le a-1$. For any $N\in L(S_c)\cap \langle dx\rangle$, one writes

with each $x_i$ being a nonnegative integer.

First, let $c = ud$ for a nonnegative integer $u$. Rewrite

Since $N\in\langle dx\rangle$, then (2.1) implies that

Let $\sum_{i = 0}^k(b^i+ui)x_i = at+x$ for some nonnegative integer $t$. On the one hand, we can regard as $N$ a function of the variables $t, x_{-1}, x_0, x_1, \ldots, x_k$ and write $N = N(t; x_{-1}, x_0, x_1, \ldots, x_k)$. It then follows that

On the other hand, for any fixed $t$, one readily finds that

where $\texttt{W}_{b, u}$ is defined in (1.3). Therefore,

Let $F(t): = ah\left(\left\lfloor\frac{at+x}{b^k+uk}\right\rfloor+\texttt{W}_{b, u}(at+x)\right)+d(at+x)$, and consider $F(t+1)-F(t)$, which equals

Note that

and

By (2.2), one then has that $F(t+1)\ge F(t)$ for any nonnegative integer $t$ if $d\ge h\left(k(b-1)+u-\left\lfloor\frac{a}{b^k+uk}\right\rfloor\right)$. Thus

whenever $d\ge h\left(k(b-1)+u-\left\lfloor\frac{a}{b^k+uk}\right\rfloor\right)$, as desired. Item (a) is proved.

Next, let $c = va$ for an integer $v$ with $0\le v\le b-1$, then

Note that $N\equiv dx\pmod{a}$, then by (2.3) one may let $\sum_{i = 0}^kb^ix_i = as+x$ for some nonnegative integer $s$. For any fixed nonnegative integer $s$, let

be a function of the variables $x_0, \ldots, x_k$ subject to $\sum_{i = 0}^kb^ix_i = as+x$, then one claims that

where each $\overline{q}_i$ is defined as (1.1). Now, let us prove the claim by mathematical induction on $k$ as follows.

$\bullet$ Let $k = 1$. Let $as+x = x_0+bx_1 = g_1$. Write $g_1 = \overline{q}_1(g_1)b+\overline{r}_1(g_1)$ with $0\le \overline{r}_1(g_1)\le b-1$ and let $\overline{q}_0(g_1) = \overline{r}_1(g_1)$. Note that $x_1\le \lfloor\frac{g_1}{b}\rfloor = \overline{q}_1(g_1)$, then we have

where the inequality in the third line holds because $v\le b-1$. It follows that

This is to say that the claim of (2.5) is true for $k = 1$.

$\bullet$ Assume that the claim of (2.5) holds for $k-1$ with $k\ge 2$. Let $g_k: = \sum_{i = 0}^kb^ix_i = as+x$ and $\widetilde{f}(x_0, x_1, \ldots, x_{k-1}): = \sum_{i = 0}^{k-1}(1+vi)x_i$. By (2.4), one then deduces that

By the inductive hypothesis we have

where

and

for $j = k-2, k-3, \ldots, 0$. For $g_k = as+x$, let $\{\overline{q}_i(g_k)\}_{i = 0}^k$ be the sequence defined as (1.1). It is observed that $g_k-x_kb^k\pmod{b^{k-1}}$ is independent on $x_k$. One then finds that

for any $0\le j\le k-2$. This together with (2.6) implies that

that is,

Hence, we arrive at

which means that (2.5) is true for $k$, so the claim of (2.5) is proved. It then follows from (2.3)–(2.5) that

Let $G(s): = ah\sum_{i = 0}^k(1+vi)\overline{q}_i(as+x)+d(as+x)$. It is direct to check that $G(s+1)-G(s) = ah(1+kv)\left(\left\lfloor\frac{as+x+a}{b^{k}}\right\rfloor- \left\lfloor\frac{as+x}{b^{k}}\right\rfloor\right)+ah\sum_{i = 0}^{k-1}(1+iv)(\overline{q}_i(as+x+a)- \overline{q}_i(as+x))$. Note that

and

for any $0\le i\le k-1$. It infers that

so $G(s+1)-G(s)\ge 0$ for any nonnegative integer $s$ whenever

Therefore,

for these values of $d\ge \frac{1}{2}kh(b-1)(2+(k-1)v)-h(1+kv)\left\lfloor\frac{a}{b^{k}}\right\rfloor$. The proof of Item (b) is finished.

This completes the proof of Lemma 2.2. □

3.   Proof of Theorem 1.1

In this section, we use Lemmas 2.1 and 2.2 to prove Theorem 1.1.

Proof of Theorem 1.1. First, let $c = ud$ for a nonnegative integer and $d\ge ah(k(b-1)+u)$. Note that $\gcd(a, d) = 1$, then by Lemmas 2.1 and 2.2 we have that

Let $H(x): = ah\left(\left\lfloor\frac{x}{b^k+uk}\right\rfloor+\texttt{W}_{b, u}(x)\right)+dx$, then

for any positive integer $x$. It follows from (3.1) that

Next, applying Lemmas 2.1 and 2.2 to computing $n(S_c)$, one has that

Write $a-1 = q(b^k+ku)+r$ with $0\le r\le b^k-1$, then

Putting (3.3) into (3.2), we derive that

as desired. Item (a) is proved.

Now, we let $c = va$ for a nonnegative integer $v$ with $v\le b-1$ and $d\ge \frac{1}{2}akh(b-1)(2+(k-1)v)$. To be similar as the proof of Item (a), we also can obtain that

Next, let us compute $n(S_c)$ in the following. First, by employing Lemmas 2.1 and 2.2 we have that

Second, we compute $\sum_{x = 1}^{a-1}\left\lfloor\frac{x}{b^k}\right\rfloor$ and $\sum_{x = 1}^{a-1}\texttt{V}_{b, v}(x)$. For the purpose, define two sequences $\{q_i\}_{i = 1}^{k}$ and $\{r_i\}_{i = 1}^{k}$ by

Then, for any $0\le i\le k$, one deduces that

which is denoted by $M_i$ for brevity. Recall that $\overline{q}_i(x)$ is defined as (1.1), and it is checked that

for any $0\le i\le k-1$. It then follows that

Finally, putting (3.6) and (3.7) into (3.4) we arrive at

where $M_i = \frac{1}{2}b^iq_i(q_i-1)+q_i(r_i+1)$, $q_i$ and $r_i$ are defined as (3.5). Thus, the proof of Item (b) is done.

The proof of Theorem 1.1 is completed. □

4.   Conclusions

Let $S = \{a_1, a_2, \ldots, a_n\}$ be a set of positive integers with $\gcd(a_1, a_2, \ldots, a_n) = 1$. The celebrated Frobenius problem is to find $g(S)$ and $n(S)$, which is the largest natural number that is not representable as a nonnegative integer combination of $a_1, a_2, \ldots, a_n$ and the number of natural numbers that are not nonnegative integer combinations of $a_1, a_2, \ldots, a_n$, respectively. In this paper, we determined $g(S_c)$ and $n(S_c)$ for $S_c = \{a, ha+d, ha+c+db, ha+2c+db^2, \ldots, ha+kc+db^k\}$ in the case of that c is divided by one of $a$ and $d$. In fact, we presented a formula for $\boldsymbol{m}(S_c, x)$ by determining the minimum value of certain functions with multi variables, where $\boldsymbol{m}(S_c, x)$ is the least positive integer in $L(S)\cap \langle x\rangle$ (see Lemma 2.2). By employing Lemmas 2.1 and 2.2 and with some technical calculations on some complex sums, we finally derived the explicit expressions of $g(S_c)$ and $n(S_c)$, so the paper extended a result of Tripathi in 2016. However, in this paper we do not say anything about this problem when $a\nmid c$ and $d\nmid c$. Maybe it needs more new ideas to settle the problem for that case. In addition, the following generalization direction for the Frobenius problem is attractive as well.

Problem 4.1. Let $a, k, h, d$ and $s$ be positive integers with $\gcd(a, d) = 1$. Let $b_1, \ldots, b_s\ge 2$ be distinct positive integers. For

find $g(S)$ and $n(S)$.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors would like to thank the anonymous referees for their helpful comments which improved the presentation of this paper. This work was supported partially by the NSF of China (No. 12226335).

Conflict of interest

The authors declare there is no conflicts of interest.