On the Frobenius Problem for Some Generalized Fibonacci Subsequences - II
Ryan Azim Shaikh, Amitabha Tripathi · 2025
Read On the Frobenius Problem for Some Generalized Fibonacci Subsequences - II by Ryan Azim Shaikh, Amitabha Tripathi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-00495.txt.
Introduction
With a handful of coin sizes, only some totals can be formed, and the largest impossible total has a name and a long history. Ryan Azim Shaikh and Amitabha Tripathi chase that number for Fibonacci-style coin sets in a 2025 paper. Their sequences follow the Fibonacci rule but start anywhere. The coin set takes every d-th term of the sequence, with d even. Both the largest gap and the count of gaps are the quarry.
Earlier work by the pair handled other spacings. Any starting pair with no common factor leaves only finitely many unmakeable totals. The genus counts those leftovers exactly. The paper is the second in a series on the problem.
Catalog record
| CREATOR | Ryan Azim Shaikh, Amitabha Tripathi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-00495
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Frobenius Problem for Some Generalized Fibonacci Subsequences - II Ryan Azim Shaikh, Amitabha Tripathi Abstract For a set A A of positive integers with gcd ( A ) = 1 \gcd(A)=1 , let ⟨ A ⟩ \langle A\rangle denote the set of all finite linear combinations of elements of A A over the non-negative integers. Then it is well known that only finitely many positive integers do not belong to ⟨ A ⟩ \langle A\rangle . The Frobenius number and the genus associated with the set A A is the largest number and the cardinality of the set of integers non-representable by A A . By a generalized Fibonacci sequence { V n } n ≥ 1 \{V_{n}\}_{n\geq 1} we mean any sequence of positive integers satisfying the recurrence V n = V n − 1 + V n − 2 V_{n}=V_{n-1}+V_{n-2} for n ≥ 3 n\geq 3 . We study the problem of determining the Frobenius number and genus for sets A = { V n , V n + d , V n + 2 d , … } A=\{V_{n},V_{n+d},V_{n+2d},\ldots\} for arbitrary n n and even d d . Keywords. Embedding dimension, Apéry set, Frobenius number, Genus 2020 MSC. 11D07, 20M14, 20M30 1 Introduction For a given subset A of positive integers with \gcd(A)=1 , we write S=\langle A\rangle=\big\{a_{1}x_{1}+\cdots+a_{k}x_{k}:a_{i}\in A,x_{i}\in{\mathbb{Z}}_{\geq 0}\big\}. We say that A is a set of generators for the set S . Further, A is a minimal set of generators for S if no proper subset of A generates S . If A=\{a_{1},\ldots,a_{n}\} is any set of generators of S arranged in increasing order, then A is a minimal set of generators for S if and only if a_{k+1}\notin\langle a_{1},\ldots,a_{k}\rangle for k\in\{1,\ldots,n-1\} . It is known that A=S^{\star}\setminus\big(S^{\star}+S^{\star}\big) , where S^{\star}=S\setminus\{0\} , is the unique minimal set of generators for S . The embedding dimension \textbf{e}(S) of S is the size of the minimal set of generators. For any set of positive integers A with \gcd(A)=1 , the set {\mathbb{Z}}_{\geq 0}\setminus S is necessarily finite; we denote this by \text{G}(S) . The cardinality of \text{G}(S) is the genus of S and is denoted by \textbf{g}(S) . The largest element in \text{G}(S) is the Frobenius number of S and is denoted by \textbf{F}(S) . The Apéry set of S corresponding to any fixed a\in S , denoted by \text{Ap}(S,a) , consists of those n\in S for which n-a\notin S . Thus, \text{Ap}(S,a) is the set of minimum integers in S\cap\textbf{C} as C runs through the complete set of residue classes modulo a . The integers \textbf{F}(S) and \textbf{g}(S) can be computed from the Apéry set \text{Ap}(S,a) of S corresponding to any a\in S via the following proposition. Proposition 1.1.1 . ( [ 2 , 10 ] ) Let S be a numerical semigroup, let a\in S , and let \text{Ap}(S,a) be the Apéry set of S corresponding to a . Then (i) \textbf{F}(S)=\max\Big(\text{Ap}(S,a)\Big)-a; (ii) \textbf{g}(S)=\frac{1}{a}\left(\sum_{n\in\text{Ap}(S,a)}n\right)-\frac{a-1}{2}; The case where \textbf{e}(S)=2 is well known and easy to establish. If S=\langle a,b\rangle , then it is easy to see that \text{Ap}(S,a)=\{bx:0\leq x\leq a-1\} , and consequently \textbf{F}(S)=ab-a-b,\quad\textbf{g}(S)=\tfrac{1}{2}(a-1)(b-1) (1) by Proposition 1.1.1 . The Frobenius Problem is the problem of determining the Frobenius number and the genus of a given numerical semigroup, and was first studied by Sylvester, and later by Frobenius; see [ 7 ] for a survey of the problem. Connections with Algebraic Geometry revived interest in Numerical Semigroups around the middle of the twentieth century; we refer to [ 8 ] as a basic textbook on the subject. Curtis [ 3 ] proved that there exists no closed form expression for the Frobenius number of a numerical semigroup S with \textbf{e}(S)>2 . As a consequence, a lot of research has focussed on the Frobenius number of semigroups whose generators are of a particular form. There are three particular instances of such results that are perhaps the closest to our work, and hence bear mentioning. Marín et. al. [ 4 ] determined the Frobenius number and genus of numerical semigroups of the form \langle F_{i},F_{i+2},F_{i+k}\rangle , where i,k\geq 3 . These are called Fibonacci semigroups by the authors. Matthews [ 5 ] considers semigroups of the form \langle a,a+b,aF_{k-1}+bF_{k}\rangle where a>F_{k} and \gcd(a,b)=1 . Taking a=F_{i} and b=F_{i+1} , one gets the semigroup \langle F_{i},F_{i+2},F_{i+k}\rangle , considered in [ 4 ] . Thus, such semigroups were termed generalized Fibonacci semigroups by Matthews, who determined the Frobenius number of a generalized Fibonacci semigroup, thereby generalizing the result in [ 4 ] for Frobenius number. Batra et. al. [ 1 ] determined the Frobenius number and genus of numerical semigroups of the form \langle a,a+b,2a+3b,\ldots,F_{2k-1}a+F_{2k}b\rangle and \langle a,a+3b,4a+7b,\ldots,L_{2k-1}a+L_{2k}b\rangle where \gcd(a,b)=1 . By a generalized Fibonacci sequence we mean any sequence \{V_{n}\} of positive integers which satisfies the recurrence V_{n}=V_{n-1}+V_{n-2} for each n\geq 3 . A study of some subsequences of a generalized Fibonacci sequence \{V_{n}\} was initiated by Panda et. al. [ 6 ] , in which the authors study the semigroup S generated by \langle V_{n},V_{n+d},V_{n+2d},\rangle when d is odd and when d=2 , and n is arbitrary. They show that S is a numerical semigroup if and only if \gcd(V_{1},V_{2})=1 and \gcd(V_{n},F_{d})=1 . The case of odd d is easy to resolve since \textbf{e}(S)=2 , that is, each V_{n+kd}\in\langle V_{n},V_{n+d}\rangle . For d=2 , \textbf{e}(S)=\kappa where \kappa satisfies F_{2(\kappa-1)}\leq V_{n}-1<F_{2\kappa} . Elements of the Apéry set \text{Ap}(S,V_{n}) are obtained by applying the Greedy Algorithm to each integer in \{1,\ldots,V_{n}-1\} with respect to the sequence F_{2},F_{4},F_{6},\ldots . There can be no closed form expression for this in general, but there is a simple expression for the Frobenius number in special cases V_{n}=F_{n} and V_{n}=L_{n} , and a recurrence relation satisfied by \textbf{g}(S) in the special case V_{n}=F_{n} . This paper completes the study of the cases initiated in [ 6 ] by extending the results of d=2 to even d . Throughout this paper, let S=\langle V_{n},V_{n+d},V_{n+2d},\ldots\rangle , where \gcd(V_{1},V_{2})=1 , \gcd(V_{n},F_{d})=1 and d is even. The main results are similar to the ones in [ 6 ] ; we list them below: (i) The embedding dimension e(S)=\kappa , where \kappa is the smallest positive integer for which F_{\kappa d}/F_{d}\geq V_{n} ; refer Theorem 3.1.1 . (ii) The Apéry set \text{Ap}(S,V_{n})=\left\{V_{n+d}\,x-\left\lfloor\frac{F_{(k-1)d}\,x}{F_{kd}}\right\rfloor V_{n}:1\leq x\leq V_{n}-1\right\}\cup\{0\} ; refer Theorem 3.3.3 and Proposition 3.2.5 , part (iii). (iii) The Frobenius number \textbf{F}(S) in the general case (refer Theorem 3.4.1 ), and in the special cases when V_{n}=F_{n} and V_{n}=L_{n} (refer Corollary 3.4.2 ). (iv) A recurrence for the genus \textbf{g}(S) in some special cases when V_{n}=F_{n} and V_{n}=L_{n} (refer Proposition 3.4.3 ). 2 Preliminary Results A generalized Fibonacci sequence \langle V_{n}\rangle_{n\geq 1} is defined by V_{n}=V_{n-1}+V_{n-2},\;\;n\geq 3,\quad\;\text{with}\;V_{1}=a,V_{2}=b, (2) where a and b are any positive integers. Two important special cases are (i) Fibonacci sequence \{F_{n}\}_{n\geq 1} when a=b=1 , and (ii) Lucas sequence \{L_{n}\}_{n\geq 1} when a=1 and b=3 . It is customary to extend these definitions to F_{0}=F_{2}-F_{1}=0 and L_{0}=L_{2}-L_{1}=2 . Binet’s formula give explicit values for F_{n} and L_{n} : F_{n}=\frac{{\alpha}^{n}-{\beta}^{n}}{\alpha-\beta},\qquad L_{n}={\alpha}^{n}+{\beta}^{n}, where \alpha=(1+\sqrt{5})/2 and \beta=(1-\sqrt{5})/2 are the roots of the equation x^{2}-x-1=0 . From these formulae, it is easy to see that F_{2n}=L_{n}F_{n} , and