Number of partitions of integer
AUTHOR:
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 Partitons, 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: it.next()
[4]
sage: type(_)
<type 'list'>
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: it.next()
[4]
sage: type(_)
<type 'list'>
Returns the number of partitions of the integer .
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 up to 500:
sage: len([n for n in [1..500] if number_of_partitions(n) != Partitions(n).cardinality(algorithm='pari')])
0
Test Bober’s algorithm.
EXAMPLES:
sage: from sage.combinat.partitions import run_tests
sage: run_tests(False, False)
Computing p(1)... OK.
...
Done.