Fast decomposition of small integers into sums of squares

Implement fast version of decomposition of (small) integers into sum of squares by direct method not relying on factorisation.

AUTHORS:

  • Vincent Delecroix (2014): first implementation (Issue #16374)

sage.rings.sum_of_squares.four_squares_pyx(n)[source]

Return a 4-tuple of nonnegative integers (i,j,k,l) such that \(i^2 + j^2 + k^2 + l^2 = n\) and \(i \leq j \leq k \leq l\).

The input must be less than \(2^{32}=4294967296\), otherwise an OverflowError is raised.

See also

four_squares() is much more suited for large input

EXAMPLES:

sage: from sage.rings.sum_of_squares import four_squares_pyx
sage: four_squares_pyx(15447)
(2, 5, 17, 123)
sage: 2^2 + 5^2 + 17^2 + 123^2
15447

sage: four_squares_pyx(523439)
(3, 5, 26, 723)
sage: 3^2 + 5^2 + 26^2 + 723^2
523439

sage: four_squares_pyx(2**32)
Traceback (most recent call last):
...
OverflowError: ...

>>> from sage.all import *
>>> from sage.rings.sum_of_squares import four_squares_pyx
>>> four_squares_pyx(Integer(15447))
(2, 5, 17, 123)
>>> Integer(2)**Integer(2) + Integer(5)**Integer(2) + Integer(17)**Integer(2) + Integer(123)**Integer(2)
15447

>>> four_squares_pyx(Integer(523439))
(3, 5, 26, 723)
>>> Integer(3)**Integer(2) + Integer(5)**Integer(2) + Integer(26)**Integer(2) + Integer(723)**Integer(2)
523439

>>> four_squares_pyx(Integer(2)**Integer(32))
Traceback (most recent call last):
...
OverflowError: ...

from sage.rings.sum_of_squares import four_squares_pyx
four_squares_pyx(15447)
2^2 + 5^2 + 17^2 + 123^2
four_squares_pyx(523439)
3^2 + 5^2 + 26^2 + 723^2
four_squares_pyx(2**32)
sage.rings.sum_of_squares.is_sum_of_two_squares_pyx(n)[source]

Return True if n is a sum of two squares and False otherwise.

The input must be smaller than \(2^{32} = 4294967296\), otherwise an OverflowError is raised.

EXAMPLES:

sage: from sage.rings.sum_of_squares import is_sum_of_two_squares_pyx
sage: [x for x in range(30) if is_sum_of_two_squares_pyx(x)]
[0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29]

sage: is_sum_of_two_squares_pyx(2**32)
Traceback (most recent call last):
...
OverflowError: ...

>>> from sage.all import *
>>> from sage.rings.sum_of_squares import is_sum_of_two_squares_pyx
>>> [x for x in range(Integer(30)) if is_sum_of_two_squares_pyx(x)]
[0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29]

>>> is_sum_of_two_squares_pyx(Integer(2)**Integer(32))
Traceback (most recent call last):
...
OverflowError: ...

from sage.rings.sum_of_squares import is_sum_of_two_squares_pyx
[x for x in range(30) if is_sum_of_two_squares_pyx(x)]
is_sum_of_two_squares_pyx(2**32)
sage.rings.sum_of_squares.three_squares_pyx(n)[source]

If n is a sum of three squares return a 3-tuple (i,j,k) of Sage integers such that \(i^2 + j^2 + k^2 = n\) and \(i \leq j \leq k\). Otherwise raise a ValueError.

The input must be less than \(2^{32}=4294967296\), otherwise an OverflowError is raised.

EXAMPLES:

sage: from sage.rings.sum_of_squares import three_squares_pyx
sage: three_squares_pyx(0)
(0, 0, 0)
sage: three_squares_pyx(1)
(0, 0, 1)
sage: three_squares_pyx(2)
(0, 1, 1)
sage: three_squares_pyx(3)
(1, 1, 1)
sage: three_squares_pyx(4)
(0, 0, 2)
sage: three_squares_pyx(5)
(0, 1, 2)
sage: three_squares_pyx(6)
(1, 1, 2)
sage: three_squares_pyx(7)
Traceback (most recent call last):
...
ValueError: 7 is not a sum of 3 squares
sage: three_squares_pyx(107)
(1, 5, 9)

sage: three_squares_pyx(2**32)
Traceback (most recent call last):
...
OverflowError: ...

>>> from sage.all import *
>>> from sage.rings.sum_of_squares import three_squares_pyx
>>> three_squares_pyx(Integer(0))
(0, 0, 0)
>>> three_squares_pyx(Integer(1))
(0, 0, 1)
>>> three_squares_pyx(Integer(2))
(0, 1, 1)
>>> three_squares_pyx(Integer(3))
(1, 1, 1)
>>> three_squares_pyx(Integer(4))
(0, 0, 2)
>>> three_squares_pyx(Integer(5))
(0, 1, 2)
>>> three_squares_pyx(Integer(6))
(1, 1, 2)
>>> three_squares_pyx(Integer(7))
Traceback (most recent call last):
...
ValueError: 7 is not a sum of 3 squares
>>> three_squares_pyx(Integer(107))
(1, 5, 9)

>>> three_squares_pyx(Integer(2)**Integer(32))
Traceback (most recent call last):
...
OverflowError: ...

from sage.rings.sum_of_squares import three_squares_pyx
three_squares_pyx(0)
three_squares_pyx(1)
three_squares_pyx(2)
three_squares_pyx(3)
three_squares_pyx(4)
three_squares_pyx(5)
three_squares_pyx(6)
three_squares_pyx(7)
three_squares_pyx(107)
three_squares_pyx(2**32)
sage.rings.sum_of_squares.two_squares_pyx(n)[source]

Return a pair of nonnegative integers (i,j) such that \(i^2 + j^2 = n\).

If n is not a sum of two squares, a ValueError is raised. The input must be less than \(2^{32}=4294967296\), otherwise an OverflowError is raised.

See also

two_squares() is much more suited for large inputs

EXAMPLES:

sage: from sage.rings.sum_of_squares import two_squares_pyx
sage: two_squares_pyx(0)
(0, 0)
sage: two_squares_pyx(1)
(0, 1)
sage: two_squares_pyx(2)
(1, 1)
sage: two_squares_pyx(3)
Traceback (most recent call last):
...
ValueError: 3 is not a sum of 2 squares
sage: two_squares_pyx(106)
(5, 9)

sage: two_squares_pyx(2**32)
Traceback (most recent call last):
...
OverflowError: ...

>>> from sage.all import *
>>> from sage.rings.sum_of_squares import two_squares_pyx
>>> two_squares_pyx(Integer(0))
(0, 0)
>>> two_squares_pyx(Integer(1))
(0, 1)
>>> two_squares_pyx(Integer(2))
(1, 1)
>>> two_squares_pyx(Integer(3))
Traceback (most recent call last):
...
ValueError: 3 is not a sum of 2 squares
>>> two_squares_pyx(Integer(106))
(5, 9)

>>> two_squares_pyx(Integer(2)**Integer(32))
Traceback (most recent call last):
...
OverflowError: ...

from sage.rings.sum_of_squares import two_squares_pyx
two_squares_pyx(0)
two_squares_pyx(1)
two_squares_pyx(2)
two_squares_pyx(3)
two_squares_pyx(106)
two_squares_pyx(2**32)