Number of partitions of an integer

AUTHOR:

  • William Stein (2007-07-28): initial version
  • Jonathan Bober (2007-07-28): wrote the program partitions_c.cc that does all the actual heavy lifting.
sage.combinat.partitions.ZS1_iterator(n)

A fast iterator for the partitions of n (in the decreasing lexicographic order) which returns lists and not objects of type Partition.

This is an implementation of the ZS1 algorithm found in [ZS98].

REFERENCES:

[ZS98]Antoine Zoghbi, Ivan Stojmenovic, Fast Algorithms for Generating Integer Partitions, Intern. J. Computer Math., Vol. 70., pp. 319–332. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.1287

EXAMPLES:

sage: from sage.combinat.partitions import ZS1_iterator
sage: it = ZS1_iterator(4)
sage: next(it)
[4]
sage: type(_)
<type 'list'>
sage.combinat.partitions.ZS1_iterator_nk(n, k)

An iterator for the partitions of n of length at most k (in the decreasing lexicographic order) which returns lists and not objects of type Partition.

The algorithm is a mild variation on ZS1_iterator(); I would not vow for its speed.

EXAMPLES:

sage: from sage.combinat.partitions import ZS1_iterator_nk
sage: it = ZS1_iterator_nk(4, 3)
sage: next(it)
[4]
sage: type(_)
<type 'list'>
sage.combinat.partitions.number_of_partitions(n)

Returns the number of partitions of the integer \(n\).

EXAMPLES:

sage: from sage.combinat.partitions import number_of_partitions
sage: number_of_partitions(3)
3
sage: number_of_partitions(10)
42
sage: number_of_partitions(40)
37338
sage: number_of_partitions(100)
190569292
sage: number_of_partitions(100000)
27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519

TESTS:

sage: n = 500 + randint(0,500)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1500 + randint(0,1500)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 1000000 + randint(0,1000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0
True
sage: n = 100000000 + randint(0,100000000)
sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0  # long time (4s on sage.math, 2011)
True

Another consistency test for \(n\) up to 500:

sage: len([n for n in [1..500] if number_of_partitions(n) != Partitions(n).cardinality(algorithm='pari')])
0
sage.combinat.partitions.run_tests(longtest=False, forever=False)

Test Bober’s algorithm.

EXAMPLES:

sage: from sage.combinat.partitions import run_tests
sage: run_tests(False, False)
Computing p(1)... OK.
...
Done.