Sum of partition's product modulo 5 up to 41

26 Views Asked by At

If we define $S(n)$ as

$4=3+1=2+2=2+1+1=1+1+1+1$

$S(4)=3\cdot1+2\cdot2+2\cdot1\cdot1+1\cdot1\cdot1\cdot1=3+4+2+1=10$

$5=4+1=3+2=2+2+1=2+1+1+1=1+1+1+1+1$

$S(5)=4\cdot1+3\cdot2+2\cdot2\cdot1+2\cdot1\cdot1\cdot1+1\cdot1\cdot1\cdot1\cdot1=4+6+4+2+1=20$

$6=5+1=4+2=4+1+1=3+3=3+2+1=3+1+1+1=2+2+2=2+2+1+1=2+1+1+1+1=1+1+1+1+1+1$

$S(6)=5\cdot1+4\cdot2+4\cdot1\cdot1+3\cdot3+3\cdot2\cdot1+ 3\cdot1\cdot1\cdot1+2\cdot2\cdot2+2\cdot2\cdot1\cdot1+2\cdot1\cdot1\cdot1\cdot1+1\cdot1\cdot1\cdot1\cdot1\cdot1=5+8+4+9+6+3+8+4+2+1=50$

so what quantity of $n$ up to $41$ which $S(n)\equiv0\pmod5$?

1

There are 1 best solutions below

0
On

Rephrasing the question: let $S(n) = \sum_{\lambda\, \vdash \, n,\, \lambda_1 < n} \prod_i \lambda_i$. Then what is $S(n) \bmod 5$?

As a calculation strategy, define $S(n, k) = \sum_{\lambda\,\vdash\,n,\, \lambda_1 \le k} \prod_i \lambda_i$ to be the corresponding sum over partitions of $n$ into parts no greater than $k$, so that $S(n) = S(n, n-1)$. Then we can consider the largest part in each partition and find the recursion $S(n, k) = \sum_{j=1}^{\min(k,n)} j S(n - j, j)$ with base case $S(0, k) = 1$ as there is one partition of $0$ and it has an empty product.

Using this recursion it is easy to write a computer program to output a table of $S(n, k)$, but neither the table nor the values of $n$ for which $S(n, n-1) \equiv 0 \pmod 5$ are in OEIS, so this may not have been previously studied.