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 typePartition
.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 mostk
(in the decreasing lexicographic order) which returns lists and not objects of typePartition
.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.