Pattern recognition from sample data

90 Views Asked by At

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

There are 1 best solutions below

3
On

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