I have some running index $n = 1,\ldots$. For each $n$ there exists a vector $f_n = (z_l : \sum_{l}{z_l} = n)$ which elements add up to $n$. The vector $f_n$ describes an integer partition of $n$. Consider the following table for $n \in \{1,\ldots, 80\}$. I want to recognize a general pattern such that I can predict $f_n$ for $n > 80$. Apparently there is some series $1,2,4,7,13,24,24,44,79,...$ which generate $f_n$. But I don't know how to further proceed from here.

enter image description here enter image description here

  • 1
    $\begingroup$ $1,2,4,7,13,24,44$ is the Tribonacci sequence (oeis.org/A000073) but the next term is $81$, not $79$. The table seems to be the representation of integers in the Tribonacci basis up to $78$ and the it breaks down. $\endgroup$ – lhf Jun 11 '18 at 11:38
  • 1
    $\begingroup$ $f_n$ is not a partition of the set $\{1,\ldots,n\}$, it's a partition of the integer $n$. $\endgroup$ – Arnaud Mortier Jun 11 '18 at 11:41
  • $\begingroup$ @Ihf yes, I figured the Tribonacci also. Actually I know the following series $(n : f_n = (n), ~ n<10000) = (1,2,4,7,13,24,44,79,146,268,482,873,1580,2867,5191,9413)$ $\endgroup$ – clueless Jun 11 '18 at 12:48

The sequence $1,2,4,7,13,24,44,79,146,268,482,873,1580,2867,5191,9413$ is the prefix of a complete sequence. The table seems to be the representations of natural numbers in terms of this sequence.

Given a natural number $n$, its representation $f(n)$ is obtained by the greedy algorithm: Let $a_m$ be the largest term of the sequence less than or equal to $n$. Then $f(n) = (f(n-a_m), a_m)$, the concatenation of the representation for $n-a_m$ with $a_m$.

So, the pattern is fully predictable recursively, once we know all values of $a_m$.

With the prefix given, you can find $f(n)$ for all $n\le 20994=1+2+4+7+\cdots+9413$.

The next term must be between $9414$ and $20995$.

  • $\begingroup$ That's correct. The problem is where to get the $a_m$'s from then. $\endgroup$ – clueless Jun 11 '18 at 13:37
  • $\begingroup$ @clueless, there are lots of way to continue your sequence into a complete sequence, but I can't see a natural way. How did you find your sequence? $\endgroup$ – lhf Jun 11 '18 at 13:43
  • $\begingroup$ It's a specific example of endogenous coalition formation (economics). The $f_n$ describes a numeric coalition structure for $n$ agents. If $n = f_n$, then the grand coalition is stable. There seemed to be a non random pattern that's why I was asking the question in the first place. $\endgroup$ – clueless Jun 11 '18 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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