Open-source software must have four freedoms:
![]() | | | ![]() |
Over 100 components (pre-existing software) are now in Sage, and included with its installation.
These libraries, softwares and databases are often very good and extensively used.
Sage interfaces with common mathematical databases
We can ask SageMath some simple questions, and it gives us the answer!
How many subsets of $\{1,2,...,6\}$ have no two consecutive numbers?
How many subsets of $\{1,2,...,6\}$ have no two consecutive numbers?
# Very naive algorithm
n = 6
S = Set(range(1, n+1)) # range(a, b) gives all the integers between a and b-1, including the boundary
number_not_consecutive = 0
for E in S.subsets():
has_consecutive = False
for e in E:
if e + 1 in E:
has_consecutive = True
break # to make the execution of the code shorter (will not ask for all e in E)
if not has_consecutive:
number_not_consecutive += 1 # Add 1 to number_not_consecutive
number_not_consecutive
21
We can generalize this question:
How many subsets of $\{1,2,...,n\}$ have no two consecutive numbers?
# Very naive algorithm
sequence_no_consecutive = []
for n in range(10):
S = Set(range(1, n+1)) # range(a, b) gives all the integers between a and b-1, including the boundary
number_not_consecutive = 0
for E in S.subsets():
has_consecutive = False
for e in E:
if e + 1 in E:
has_consecutive = True
break # to make the execution of the code shorter (will not ask for all e in E)
if not has_consecutive:
number_not_consecutive += 1 # Add 1 to number_not_consecutive
sequence_no_consecutive.append(number_not_consecutive)
print(sequence_no_consecutive)
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
What is this sequence?
# What is this sequence?
oeis(sequence_no_consecutive)
0: A000045: Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1. 1: A212804: Expansion of (1 - x)/(1 - x - x^2). 2: A104763: Triangle read by rows: Fibonacci(1), Fibonacci(2), ..., Fibonacci(n) in row n.
# Is it really counted by the Fibonacci numbers?!
oeis.browse()
We can look up the documentation, and explore SageMath's code, right from the interface!
Example (for which you don't even need to know the math!)
How many (integer) partitions of 13 have only parts at most 3?
Partitions?
len(Partitions(13, max_part=3))
21
Notice that we did not even need to know what a partition or a part is to solve this problem. But it is always good to know what you are doing (as a piece of advice...)
An integer partition (often just called a partition) of the number $n$ is a decreasing list of positive integers whose sum is $n$.
For example, $(2,1,1)$ is a partition of $4$.
How are partitions counted, anyway? We can read the source code by using ??
.
number_of_partitions??
The code refers to the algorithm 'FLINT', which stands for Fast Library for Number Theory. This means that it uses external code (that is included in Sage anyway), but this code might be written in another programming language.
We can verify that this is a fast algorithm, by asking Sage how long it takes to count partitions of 1000.
%time number_of_partitions(1000)
CPU times: user 575 µs, sys: 76 µs, total: 651 µs Wall time: 2.23 ms
24061467864032622473692149727991
The algorithm is very fast to count all 24061467864032622473692149727991 partitions of 1,000.
Let us compare it with the method that enumerates all partitions, then counts them.
%time len(Partitions(1000))
--------------------------------------------------------------------------- OverflowError Traceback (most recent call last) File <timed eval>:1 OverflowError: cannot fit 'int' into an index-sized integer
There are too many partitions of 1,000 to store them before counting them.
The size of many combinatorial sets grows very rapidly. This is called the combinatorial explosion. It means that there exists a threshold where obtaining data is impossible. It can be because:
print(f"There are {number_of_partitions(10)} partitions of 10, and {number_of_partitions(100)} partitions of 100.")
print(f"There are {factorial(4)} permutations of 4, and {factorial(10)} permutations of 10.")
There are 42 partitions of 10, and 190569292 partitions of 100. There are 24 permutations of 4, and 3628800 permutations of 10.
Algorithms that are already in SageMath are often, not always, optimized to use just what is needed of memory and time.
If you want to do "large" computations, you have to be mindful of the limitations of your machine.
Asking for help with SageMath:
number of partitions?
number of partitions??
Why I use SageMath?