Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working on a problem for an online judge and I'm stuck. I'd like a nudge in the right direction (not an outright solution, please), relevant references, theorems, etc. After reading through relevant entries here and on the web, I believe the correct mathematical statement of the problem is to count the exact number of elements in a subset of a numerical semigroup $\lbrace a, b \rbrace$ (the set of all linear combinations of $a,b$ with non-negative integer coefficients). Specifically, to count the element of set $S$: \begin{equation} S = \lbrace x \vert x \in \lbrace a,b \rbrace, X_{min} \le x \le X_{max} \rbrace \end{equation} The range of possible values is: $1 \le a, b, X_{min}, X_{max} \le \approx 2^{63}$. With these sizes, only a closed form $O(1)$ solution will do. I already have a solution for the cases: $a=b$ (trivial) and $b = a + 1$ (not trivial but not too challenging, interesting case). From the answers to this question: Determine the Set of a Sum of Numbers, I suspect some sort of generalization of the gap counting formula for the case where $gcd(a,b)=1$: $gaps=(a-1)(b-1)/2$, to be able to quickly calculate the number of gaps below an arbitrary $x$ is the key for answering this question.

What I've noticed so far: I've investigated trying to find a pattern for the gaps between successive multiples of $a$ (assuming $a<b$). I've noticed that each multiple of $b$ occupies one of the $(a-1)$ positions between multiples of $a$, and that the $(a-1)$th multiple of $b$ fills that last gap. The first $b$ fills position $b_a$ and the next multiple of b occupies $(b_a + (b-a)_a)_a$. But I haven't been able to generalize anything from that yet.

(My math background is undergraduate level calculus (2 years), linear algebra/matrix theory, discrete math (for CS students), and a real analysis course, but no number theory.) Thanks for any hints / pointers!

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

Your problem is a specific case of counting lattice points (vectors all of whose coordinates are integers) inside of a polytope (a region in $n$-space which is the intersection of a finite number of half spaces -- sets of vectors $x$ satisfying $a \cdot x \le b$, where $a$ is some non-zero vector and $b$ is a scalar). In your case you're in dimension 2 which makes some things simpler. The ingredients are a method to calculate the number of lattice points on a line segment, and in the interior of a right triangle). You can find the details in "A Simple Algorithm for Lattice Point Counting in Rational Polygons: by Hiroki Yanagisawa in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.5275&rep=rep1&type=pdf . Here is the idea: If $a,b,c$ are positive integers define $N(a,b,c)$ to be the number of lattice points in $\{ x \in \mathbb{R}^2 | a x + by \le c \}$. The first observations is that $N(a,b,c) = N(b,a,c)$ and that $N(a,a,c) = \lfloor c/a \rfloor (\lfloor c/a \rfloor - 1)/2$, and if $a > b$ let $m = \lfloor c/a \rfloor, h = \lfloor (c-am)/b\rfloor, k = \lfloor (a-1)/b\rfloor, c' = c - b(km + h)$. Then $N(a,b,c) = N(a-bk,b,c') + km(m-1)/2 + m h$. The latter comes from dividing the triangle into regions some of which have numbers of lattice points that are easy to calculate. This gives a recursive algorithm (something like the Euclidean algorithm) which runs in time $O(\max(\log(a),\log(b),\log(c)))$.

share|improve this answer
    
This looks very promising, I'll try it out, thanks! –  Bogatyr Nov 26 '12 at 10:30
    
This was the missing element, I've now had my solution accepted. I had to add the cases where one of x or y is zero. Thanks! –  Bogatyr Nov 27 '12 at 12:51
add comment

You can reduce the general problem to the problem for $\gcd(a,b)=1$ using

$$ \begin{align} a&\to a/g\;,\\ b&\to b/g\;,\\ X_{\text{min}}&\to\lceil X_{\text{min}}/g\rceil\;,\\ X_{\text{max}}&\to\lfloor X_{\text{max}}/g\rfloor\;, \end{align} $$

where $g=\gcd(a,b)$. Then you can find a solution to $ma+nb=1$ (with $m$ or $n$ negative), use it to represent all integers in $[1,ab]$ as linear combinations of $a$ and $b$, and add a sufficient multiple of $a$ or $b$ to make all coefficients nonnegative. All numbers in and beyond the resulting interval are in the semigroup, and you only have to deal with the cases below the interval.

share|improve this answer
    
I'll check that out, thanks. I was wondering/hoping that there was some sort of reduction to the gcd = 1 case! –  Bogatyr Oct 10 '12 at 11:24
    
joriki, I've thought about your hints some more. This resulting interval you mention, it contains no "gaps," right? If so, isn't that just the same as the information provided by the Frobenius number ($F = ab-a-b$)? The region above which there are no gaps? What I was hoping to find was some hints in calculating how many gaps there are below a particular value $x$, since that's where I'm stuck... –  Bogatyr Oct 10 '12 at 17:26
    
@Bogatyr: Yes, you're right -- you hadn't said that you're aware of that. –  joriki Oct 10 '12 at 20:57
    
Any hints in how to approach counting the gaps below an arbitrary x (or counting the elements themselves, if that's easier) in a closed form expression appreciated... –  Bogatyr Oct 12 '12 at 10:49
    
Thanks again for your help this observation was also critical, I'd like to accept your answer as well. –  Bogatyr Nov 27 '12 at 12:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.