# How to calculate the number of vector not multiple of other in $\mathbb{N}$.

I want to determine the number of vectors that are multiple of other vectors given the following constraints. $$A= \lbrace(x_0,x_1, \ldots, x_n): x_i\in \mathbb{N}\hspace{5pt}\left| \hspace{5pt}\sum x_i\leq c\right. \rbrace$$

With a vector multiple of another i mean $$v,u \in A, ~\exists ~x \in \mathbb{N} ~|~u = x\cdot v$$ Let's say i have $c=1$, in this case I would just have $\lbrace(0,0),(0,1),(1,0)\rbrace$ in which all vectors are unique. I thought about doing this iteratively and look for $c=2$ which has $\lbrace(0,0),(0,1),(0,2),(1,0),(1,1),(2,0)\rbrace$, here we have 3+1 unique elements, 3 from the previous step, and also (1,1). (0,2) and (2,0) are respectively multiples of (0,1) and (2,0), for example $(2,0)=2\cdot(1,0)$.

I kept trying for a while and I realized that maybe i can get the number of vectors which are not multiple of other counting how many elements in $A$ have all of the $x_i$ components co-prime.

Is this intuition right? and is there a general formula to count them other then iteratively calculate the result, that can be extended to more dimensions?

• Title says "not multiple," body of the question omits "not." Jul 25, 2013 at 18:41
• Presumably, you want $\exists x\in \mathbb N: x>1\dots$, since $x=0$ and $x=1$ makes all vectors multiples. Jul 25, 2013 at 18:43
• You are correct that the count is really counting vectors where all the components have no common factor. Jul 25, 2013 at 18:46
• If the condition was simply $0\leq x_i \leq c$ for all $i$, the approximate count would be $\dfrac{c^n}{\zeta(n)}$. I think this approximation might work here, too, with some factoring: $\dfrac{c^n}{n!\zeta(n)}$. Here, $\zeta$ is the Riemann zeta function. Jul 25, 2013 at 18:50
• Sorry for omitting the not, the idea is that i need both, and once i have a value I can deduce the other. What do you mean with the approximate count?
Jul 25, 2013 at 18:58

Only some beginning thoughts.

Let's formalize a bit. Let $$A_{n,c}$$ be the set of all $$n$$-tuples of natural numbers with component sum less than or equal to $$c$$:

$$A_{n,c}=\{(x_1,\ldots,x_n)\in\mathbb{N}^n\mid\sum x_i\le c\}$$

Let $$B_{n,c}\subset A_{n,c}$$ be those $$n$$-tuples whose greatest common divisor is $$1$$:

$$B_{n,c}=\{(x_1,\ldots,x_n)\in A_{n,c}|\gcd(x_1,\ldots,x_n)=1\}$$

The question asks for $$|B_{n,c}|$$. Here are some preliminary calculations for $$n=2$$:

$$|B_{2,0}|=1\\|B_{2,1}|=3\\|B_{2,2}|=4\\|B_{2,3}|=6\\|B_{2,4}|=8\\|B_{2,5}|=12\\\vdots$$

This is actually A225531. There is a link that calculates all values for $$c\le 400$$, but they don't give a general formula.

For $$n=3$$, I've found the sequence begins with $$1,4,8,17,32,47,74$$, but this doesn't show up in OEIS. If we let $$a_c$$ be the number of partitions of $$c$$ into $$2$$ or $$3$$ parts of distinct and relatively prime size, and $$b_c$$ be the number of partitions of $$c$$ into $$3$$ parts of relatively prime size, $$2$$ of the same size and $$1$$ a different size, then we have the following recursion:

$$|B_{3,c}|=|B_{3,c-1}|+6a_c+3b_c$$

Of course, this might not make things any easier because we have to calculate $$a_c$$ and $$b_c$$, and then resolve the recursion. However, a method like this would generalize to higher dimensions.

• How do you search OEIS? Jul 25, 2013 at 19:21
• @metacompactness: visit oeis.org Jul 25, 2013 at 19:21
• You didn't understand my question. How do you SEARCH the database; the sequences are coded like A225531 Jul 25, 2013 at 19:33
• @metacompactness: I'm not exactly sure what you are asking, but here is how I use OEIS. I first calculate a few terms in the sequence I'm looking for by hand, and then type them in to see what comes up. For instance, if you type 1,3,4,6,8,12,14,20 into the search function on oeis.org, sequence A225531 will pop up. Jul 25, 2013 at 19:35
• @fady: Can you post your answer? I'd like to see it, because what I've provided is certainly not a complete answer. Jul 26, 2013 at 15:32