1
$\begingroup$

I was thinking about this question and thought about it for quite a while but couldn't come up with an answer.

Firstly, we fix two sets $R$ and $S$. We consider "cycles", which are tuples in the form of $(a_1, a_2, \cdots, a_k)$, where $k$ is not necessarily $N$, such that

  1. All elements belong to $R$. That is, $a_i \in R$.
  2. All elements are distinct. That is, $a_i \neq a_j \iff i \neq j$
  3. Adjacent elements sum to elements in $S$. That is, $\forall 1 \leq i < k, a_i + a_{i + 1} \in S$ and $a_k + a_1 \in S$.

The task is to count the number of such cycles. Examples of sets that I want to consider are sparse sets such as when $R = \mathbb{N}$ and $S = \{k^2 : k \in \mathbb{Z}\}$ or $S = \mathbb{P}$ the prime numbers.

The structure of the problem immediately reminds me of DP, but the issue is that the "adjacent" condition combined with the "distinct" condition makes it very annoying. If it didn't have to be distinct numbers, I suppose I can do dp[length][last_number] or something like that, but I don't see how to modify this for the problem above. Obviously we can't include any information about the bit mask used.

This problem can also be phrased as a graph theory problem, where edges are such that the endpoints satisfy the property, and if my intuition is correct it seems that this problem is harder than Hamiltonian cycle problem. Therefore, I was wondering if there's still some general approach possible.

$\endgroup$
5
  • $\begingroup$ @D.W. My bad, I did phrase it quite badly. For a concrete example, consider $N = 100$ or some large number. Then, $[3, 4, 1, 2]$ is a cycle such that every adjacent sums to a prime, since $3 + 4 = 7, 4 + 1 = 5, 1 + 2 = 3, 2 + 3 = 5$ (the final relation makes it a cycle). Or you can draw a polygon labelling the vertices that. I don't think it must be done with DP, just asking if there are general known approaches to handle the "distinct elements" requirement, since if duplicate elements are allowed i.e. the list $(a_1, a_2, \cdots, a_k) \in Z_N^k$, $\endgroup$
    – Gareth Ma
    Jun 5, 2023 at 1:37
  • $\begingroup$ Then you can do it by dp quite easily - if it doesn't have to be a cycle then just maintain a dp on the final element of the list, and if it has to be a cycle then also maintain the starting element $a_1$. It can be done in $O(N^3 \log k)$ via matrix exponentiation or some other ways. Also, I just realised that if adjacent elements sum to primes then it's less interesting (since $2 \in \vec{a}$), but if we replace "summing to prime" with "summing to squares", then I believe it becomes interesting, and I was wondering if this was also a known problem. $\endgroup$
    – Gareth Ma
    Jun 5, 2023 at 1:39
  • $\begingroup$ Also to answer your original question, no it doesn't have to be a permutation of the entire list (that'll be a hamiltonian cycle on the "relation graph"), but just count any list. $\endgroup$
    – Gareth Ma
    Jun 5, 2023 at 1:40
  • $\begingroup$ @D.W. Sorry for the late reply, see if it is more clear $\endgroup$
    – Gareth Ma
    Jun 5, 2023 at 21:38
  • 1
    $\begingroup$ I suspect it's hard. I don't know of any way to handle the distinctness condition without introducing an exponential running time. If you replace $a_i+a_{i+1}\in S$ with some general binary relation on $a_i,a_{i+1}$ and you require the cycles to be full-length (of length $|R|$), this is the problem of counting the number of Hamiltonian cycles in an arbitrary graph, which I believe is #P-hard. $\endgroup$
    – D.W.
    Jun 6, 2023 at 9:01

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.