Beware! Your computer could crash!

Computer Science Level 5

The partition function $P(n)$ counts the number of distinct ways we can represent $n$ as the sum of positive integers. Currently, there is no known closed form for $P(n)$ , so computing it for large arguments is done recursively using computers. However, it is computationally intensive and can cause your program to crash if implemented naively.

Implement a program to compute $P(n)$ exactly and enter the value of $P(8000) \pmod {10^{10}}$ .

The answer is 8402844164.

1 solution

Agnishom Chattopadhyay
Nov 28, 2016

Partial solution. See here for a broader discussion on this.

We use a result by Euler, namely the pentagonal theorem, to deduce that $p(k) = p(k - 1) + p(k - 2) - p(k - 5) - p(k - 7) + p(k - 12) + p(k - 15) - p(k - 22) - ...$ where the numbers used are generalized Pentagonal Numbers.

import Data.List

genpent = map (\n -> (3*n*n - n) `div` 2) ((concat.transpose) [[1..],[-1,-2..]])

partitions = 1 : go 1
  where go n = sum (zipWith (*) signs (map (\x -> partitions !! (n-x)) (takeWhile (<= n) genpent))) : go (n+1)
        signs = 1: 1: (-1) : (-1) : signs

partitions !! 8000 gives the desired result in about 30 seconds.

Beware! Your computer could crash!

The answer is 8402844164.

1 solution

0 pending reports