Number of $n$-tuples of positive integers having every product of adjacent elements less than or equal to $k$.

How to calculate the number of n-tuples of positive integers, satisfying the property that for each adjacent elements in the tuple, the product of elements $$A[i] \cdot A[i+1] \leq k$$ where $$1 \leq i \leq n$$. For example, if $$n = 2$$ and $$k = 2$$, the answer is $$3$$ as $$2$$-tuples are $$(1,1), (1,2), (2,1)$$.

My Approach: I am trying to approach this problem with Inclusion-Exclusion principle. First, I will calculate all $$n$$-tuples with each element in the range $$[1,k]$$. This is $$k^n$$. Now I will consider all pairs $$(a, b)$$ where $$1 \leq a \leq k$$ and $$1 \leq b \leq k$$ and $$a \cdot b > k$$. Those pairs can be calculated easily. Now I will exclude those cases where at least one such pair occurs, then add cases where at least two such pairs occur and so on. But I am not sure how to do this.

• The general exclusion-inclusion principle is quite complicated, $$| \bigcup_{i=1}^n A_i | = \sum_{i=1}^n |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j | - \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k | - ... + (-1)^{n-1} |\bigcap_{i=1}^n A_i |$$ Aug 10, 2021 at 12:12
• Dynamic programming seems better suited, count the ones that end in $j$ and have length $l$ where $l$ goes from $1$ to $n$. Alternatively build the graph where two vertices are adjacent if thir product is at least $k$ and then raise its adjacency matrix to the $n'th$ and take sum of all terms. Aug 10, 2021 at 12:12
• @Yorch dynamic programming is not possible as 2 ≤ N ≤ 1000 and 1 ≤ k ≤ 10**9. I didn't get the alternative approach that you mentioned, could you please elaborate ? Aug 10, 2021 at 12:56
• What is $P{}{}$? Aug 10, 2021 at 12:57
• Sorry, it's k. Aug 10, 2021 at 12:59

Consider the equivalence relation on $$\{1,\dots, k\}$$ given by $$a\sim b$$ if $$\lfloor k/a \rfloor = \lfloor k/b \rfloor$$.

Build the vector of pairs of ints that tells us for each equivalence class how many elements are in that class and what the value of $$k/a$$ is for its elements.

This can be done in time $$\sqrt{k}$$ with the hyperbola trick.

After we have built this vector we do a dp table with this vector.

In other words, for each length $$l$$ we find how many sequences end with an element in that particular equivalence class, of course we need to build prefix sum table for the previous column each time we want to get a new column.

Complexity is $$\mathcal O (n \sqrt k)$$ so should run fine.

• I got your approach, and it seems to be working perfectly. Could you please elaborate the hyperbolic trick that you mentioned? I didn't get it completely. thanks Aug 11, 2021 at 4:33
• It's basically the idea used here: en.wikipedia.org/wiki/Dirichlet_hyperbola_method . But the idea is just that in order to see how many elements have $\frac{k}{a} = x$ when $x\leq \sqrt{n}$ you can iterate through the values of $x$ and solve each one individually, and in order to find how many elements have $\frac{k}{a} = x$ with $x> \sqrt{n}$ you can just iterate over the values of $a$ where $a< \sqrt{n}$. Glad to help. Aug 11, 2021 at 12:58