# Algorithm for finding numbers with an even partition number

NOTE: After edit question became about set partitions, which not was I intended, so this is second try.

Is there an algorithm for producing an infinite subset of set of integer partition numbers p(n) such that all elements of this subset are even and we don't need to use some sieve (for example, find all elements of p(n) and then throw out odd). I don't necessarily need all even p(n), just infinite subset of them.

• These are the Bell numbers, oeis.org/A000110, right? Inspection suggests they're even if and only if $n\equiv2\bmod3$. – Gerry Myerson Jun 6 '16 at 0:29
• See, in particular, the discussion of Touchard's congruence at en.wikipedia.org/wiki/Bell_number – Gerry Myerson Jun 6 '16 at 0:46
• Questions about parity of partition numbers seem to turn out fairly deep. Even proving that there are infinitely many even partition numbers is a very nontrivial task. You can find some of the history of the problem in the introduction to this paper. – Wojowu Jun 6 '16 at 10:51
• For what it's worth, numbers $n$ such that $p(n)$ is even are tabulated at oeis.org/A001560 and there is a reference to T. R. Parkin and D. Shanks, On the distribution of parity in the partition function, Math. Comp., 21 (1967), 466-480. – Gerry Myerson Jun 6 '16 at 12:45
• @Wojowu, proving there are infinitely many even partition numbers (and infinitely many odd partition numbers) is actually pretty easy. It's done in half a page in Kolberg, Note on the parity of the partition function, Math Scand 7 (1959) 377-378. This may not be what OP wants, but I'd recommend OP have a look at it, anyway. – Gerry Myerson Jun 6 '16 at 23:35

These are Bell numbers $B_n$.
It can be shown that for $n>1$, $B_{n}\equiv B_{n-1}+B_{n-2}\pmod{2}$, which together with initial values implies that $B_{n}\equiv 0\pmod{2}$ iff $n\equiv 2\pmod{3}$.
Namely, consider a mapping on the set partitions of $\{1,2,\dots,n\}$ that exchanges elements $1$ and $2$. This mapping is an involution, which maps a set partition to some other (and vice versa), unless $1$ and $2$ appear in the same part or form their own singleton parts (in which cases the set partition is mapped to itself). The number of such exceptional set partitions of the former type is $B_{n-1}$, and the number of those of the latter type is $B_{n-2}$. This observation implies the congruence $B_{n}\equiv B_{n-1}+B_{n-2}\pmod{2}$.