-1
$\begingroup$

This question comes from some reasoning I made myself about a "joke block chain" where every new block is labeled with a triplet <S, P, N> where where S = sum of the N transactions so far and P = product of the N transactions.

So let's say we start with:

<5, 5, 1> => [5]
<- include a transaction of 3
<8, 15, 2> => [5, 3] or [3, 5]
<- merge with another branch having <5, 6, 2> ([3,2] or [2,3])
<13, 90, 4> => [5, 3, 3, 2] <- in any order
...

I hypothesise that such triplets are unique because it seems to me that N limits the possible groupings of P factors and S identifies one of those gropings, and you can't apply tricks like "keep multiplying by 1 to tune the sum" because then N will also change.

Is there any literature about this? How could I demonstrate the uniqueness of such triplets?

Given one of those triplets, can the problem of identifying the "original" numbers be considered hard? I know factorisation is NP, does adding S and N change its complexity?

Extra question: could there be a way to check if a triplet is "valid" (meaning there actually exists a set of N integers that satisfy the S and P constraints) without actually solving it?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I think you're asking whether there are positive integers $a_1,\dots,a_n$ and $b_1,\dots,b_n$, $a_i\ne b_j$, such that $\sum a_i=\sum b_i$ and $\prod a_i=\prod b_i$. $\endgroup$
    – Gerry Myerson
    Commented Oct 8, 2020 at 8:59

3 Answers 3

Reset to default
6
$\begingroup$

If I understand the question, then the triple $(30,840,3)$ could come from $6+10+14=30$, $6\times10\times14=840$ or from $7+8+15=30$, $7\times8\times15=840$.

Improve this answer
$\endgroup$
6
$\begingroup$

No, the solution is not always unique. You may be interested in a well-known recreational math puzzle in which, essentially, one needs to find the values of $S$ for which $\langle S, 72, 3\rangle$ does not have a unique solution: https://en.wikipedia.org/wiki/Ages_of_Three_Children_puzzle . I do not write the counterexample here to avoid spoiling the puzzle, but it is on that Wikipedia page.

Improve this answer
$\endgroup$
3
$\begingroup$

As to uniqueness, the answer is no as per the answers by Gerry Myerson and Federico Poloni.

As to hardness: assuming the tuple $\langle S,P,N\rangle$ has a solution, finding it is no harder than factoring $P$ (which in your intended "blockchain" application would likely be not so very hard, given that it would presumably have lots of smallish prime factors). $P$ can have no more than ${\rm O}(\log P)$ and no fewer than $N$ prime factors. For a solution, it remains to partition these into $N$ non-empty sets $S_i$ and to check if $\sum_i\prod_{p\in S_i}p=S$. Since the number of such partitions for $f$ factors is given by the Stirling number of the second kind $\left\{f\atop N\right\}$, you can get a bound on the effort from the asymptotic behavior of those.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .