1

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

clueless
  • 771
  • 1
    $1,2,4,7,13,24,44$ is the Tribonacci sequence (https://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. – lhf Jun 11 '18 at 11:38
  • 1
    $f_n$ is not a partition of the set ${1,\ldots,n}$, it's a partition of the integer $n$. – Arnaud Mortier Jun 11 '18 at 11:41
  • @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)$ – clueless Jun 11 '18 at 12:48

1 Answers1

0

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$.

lhf
  • 216,483
  • That's correct. The problem is where to get the $a_m$'s from then. – clueless Jun 11 '18 at 13:37
  • @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? – lhf Jun 11 '18 at 13:43
  • 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. – clueless Jun 11 '18 at 13:49