def graded_dimension(self, k):
        r"""
        Return the dimension of the ``k``-th graded piece of ``self``.

        The `k`-th graded part of a free Lie algebra on `n` generators
        has dimension

        .. MATH::

            \frac{1}{k} \sum_{d \mid k} \mu(d) n^{k/d},

        where `\mu` is the Mobius function.

        REFERENCES:

        [MKO1998]_

        EXAMPLES::

            sage: L = LieAlgebra(QQ, 'x', 3)
            sage: H = L.Hall()
            sage: [H.graded_dimension(i) for i in range(1, 11)]
            [3, 3, 8, 18, 48, 116, 312, 810, 2184, 5880]
            sage: H.graded_dimension(0)
            0
        """
        if k == 0:
            return 0
        from sage.arith.all import moebius
        s = len(self.lie_algebra_generators())
        k = ZZ(k) # Make sure we have something that is in ZZ
        return sum(moebius(d) * s**(k // d) for d in k.divisors()) // k

    def __iter__(self):
        r"""
        Create an iterator that generates the elements of `\Q/n\Z` without
        repetition, organized by increasing denominator.

        For a fixed denominator, elements are listed by increasing numerator.

        EXAMPLES:

        The first 19 elements of `\Q/5\Z`::

            sage: import itertools
            sage: list(itertools.islice(QQ/(5*ZZ), 19r))
            [0, 1, 2, 3, 4, 1/2, 3/2, 5/2, 7/2, 9/2, 1/3, 2/3, 4/3, 5/3,
             7/3, 8/3, 10/3, 11/3, 13/3]
        """
        if self.n == 0:
            for x in QQ:
                yield self(x)
        else:
            d = ZZ(0)
            while True:
                for a in d.coprime_integers((d * self.n).floor()):
                    yield self(a / d)
                d += 1

def add_sha_tor_primes(N1, N2):
    """
    Add the 'sha', 'sha_primes', 'torsion_primes' fields to every
    curve in the database whose conductor is between N1 and N2
    inclusive.
    """
    query = {}
    query["conductor"] = {"$gte": int(N1), "$lte": int(N2)}
    res = curves.find(query)
    res = res.sort([("conductor", pymongo.ASCENDING)])
    n = 0
    for C in res:
        label = C["lmfdb_label"]
        if n % 1000 == 0:
            print label
        n += 1
        torsion = ZZ(C["torsion"])
        sha = RR(C["sha_an"]).round()
        sha_primes = sha.prime_divisors()
        torsion_primes = torsion.prime_divisors()
        data = {}
        data["sha"] = int(sha)
        data["sha_primes"] = [int(p) for p in sha_primes]
        data["torsion_primes"] = [int(p) for p in torsion_primes]
        curves.update({"lmfdb_label": label}, {"$set": data}, upsert=True)

    def random_element(self):
        r"""
        Return a random element of `\Q/n\Z`.

        The denominator is selected
        using the ``1/n`` distribution on integers, modified to return
        a positive value.  The numerator is then selected uniformly.

        EXAMPLES::

            sage: G = QQ/(6*ZZ)
            sage: G.random_element()
            47/16
            sage: G.random_element()
            1
            sage: G.random_element()
            3/5
        """
        if self.n == 0:
            return self(QQ.random_element())
        d = ZZ.random_element()
        if d >= 0:
            d = 2 * d + 1
        else:
            d = -2 * d
        n = ZZ.random_element((self.n * d).ceil())
        return self(n / d)

        def phi(self, i):
            r"""
            Return `\varphi_i` of ``self``.

            EXAMPLES::

                sage: S = crystals.OddNegativeRoots(['A', [2,2]])
                sage: mg = S.module_generator()
                sage: [mg.phi(i) for i in S.index_set()]
                [0, 0, 1, 0, 0]
                sage: b = mg.f(0)
                sage: [b.phi(i) for i in S.index_set()]
                [0, 1, 0, 1, 0]
                sage: b = mg.f_string([0,1,0,-1,0,-1]); b
                {-e[-2]+e[1], -e[-2]+e[2], -e[-1]+e[1]}
                sage: [b.phi(i) for i in S.index_set()]
                [2, 0, 0, 1, 1]

            TESTS::

                sage: S = crystals.OddNegativeRoots(['A', [2,1]])
                sage: def count_f(x, i):
                ....:     ret = -1
                ....:     while x is not None:
                ....:         x = x.f(i)
                ....:         ret += 1
                ....:     return ret
                sage: for x in S:
                ....:     for i in S.index_set():
                ....:         assert x.phi(i) == count_f(x, i)
            """
            if i == 0:
                return ZZ.zero() if (-1,1) in self.value else ZZ.one()

            count = 0
            ret = 0
            if i < 0:
                lst = sorted(self.value, key=lambda x: (x[1], -x[0]))
                for val in reversed(lst):
                    # We don't have to check val[1] because this is an odd root
                    if val[0] == i:
                        if count == 0:
                            ret += 1
                        else:
                            count -= 1
                    elif val[0] == i - 1:
                        count += 1

            else: # i > 0
                lst = sorted(self.value, key=lambda x: (-x[0], -x[1]))
                for val in lst:
                    # We don't have to check val[0] because this is an odd root
                    if val[1] == i:
                        if count == 0:
                            ret += 1
                        else:
                            count -= 1
                    elif val[1] == i + 1:
                        count += 1
            return ret

def twoadic(line):
    r""" Parses one line from a 2adic file.  Returns the label and a dict
    containing fields with keys '2adic_index', '2adic_log_level',
    '2adic_gens' and '2adic_label'.

    Input line fields:

    conductor iso number ainvs index level gens label

    Sample input lines:

    110005 a 2 [1,-1,1,-185793,29503856] 12 4 [[3,0,0,1],[3,2,2,3],[3,0,0,3]] X24
    27 a 1 [0,0,1,0,-7] inf inf [] CM
    """
    data = split(line)
    assert len(data) == 8
    label = data[0] + data[1] + data[2]
    model = data[7]
    if model == "CM":
        return label, {"2adic_index": int(0), "2adic_log_level": None, "2adic_gens": None, "2adic_label": None}

    index = int(data[4])
    level = ZZ(data[5])
    log_level = int(level.valuation(2))
    assert 2 ** log_level == level
    if data[6] == "[]":
        gens = []
    else:
        gens = data[6][1:-1].replace("],[", "];[").split(";")
        gens = [[int(c) for c in g[1:-1].split(",")] for g in gens]

    return label, {"2adic_index": index, "2adic_log_level": log_level, "2adic_gens": gens, "2adic_label": model}

 def mult_order(x):
     ct = ZZ.one()
     cur = x
     while cur != one:
         cur *= x
         ct += ZZ.one()
     return ZZ(ct)

    def __init__(self, params, asym=False):
        # set parameters
        (self.alpha, self.beta, self.rho, self.rho_f, self.eta, self.bound, self.n, self.k) = params

        self.x0 = ZZ(1)
        
        self.primes = [random_prime(2**self.eta, lbound = 2**(self.eta - 1), proof=False) for i in range(self.n)]
        primes = self.primes
        
        self.x0 = prod(primes)

        # generate CRT coefficients
        self.coeff = [ZZ((self.x0/p_i) * ZZ(Zmod(p_i)(self.x0/p_i)**(-1))) for p_i in primes]

        # generate secret g_i
        self.g = [random_prime(2**self.alpha, proof=False) for i in range(self.n)]

        # generate zs and zs^(-1)
        z = []
        zinv = []

        # generate z and z^(-1)
        if not asym:
            while True:
                z = ZZ.random_element(self.x0)  
                try:
                    zinv = ZZ(Zmod(self.x0)(z)**(-1))
                    break
                except ZeroDivisionError:
                    ''' Error occurred, retry sampling '''

            z, self.zinv = zip(*[(z,zinv) for i in range(self.k)])

        else: # asymmetric version
            for i in range(self.k):
                while True:
                    z_i = ZZ.random_element(self.x0)  
                    try:
                        zinv_i = ZZ(Zmod(self.x0)(z_i)**(-1))
                        break
                    except ZeroDivisionError:
                        ''' Error occurred, retry sampling '''

                z.append(z_i)
                zinv.append(zinv_i)

            self.zinv = zinv

        # generate p_zt
        zk = Zmod(self.x0)(1)
        self.p_zt = 0
        for z_i in z:
            zk *= Zmod(self.x0)(z_i)
        for i in range(self.n):
            self.p_zt += Zmod(self.x0)(ZZ(Zmod(self.primes[i])(self.g[i])**(-1) * Zmod(self.primes[i])(zk)) * ZZ.random_element(2**self.beta) * (self.x0/self.primes[i]))

        self.p_zt = Zmod(self.x0)(self.p_zt)

def iterator_fast(n, l):
    """
    Iterate over all ``l`` weighted integer vectors with total weight ``n``.

    INPUT:

    - ``n`` -- an integer
    - ``l`` -- the weights in weakly decreasing order

    EXAMPLES::

        sage: from sage.combinat.integer_vector_weighted import iterator_fast
        sage: list(iterator_fast(3, [2,1,1]))
        [[1, 1, 0], [1, 0, 1], [0, 3, 0], [0, 2, 1], [0, 1, 2], [0, 0, 3]]
        sage: list(iterator_fast(2, [2]))
        [[1]]

    Test that :trac:`20491` is fixed::

        sage: type(list(iterator_fast(2, [2]))[0][0])
        <type 'sage.rings.integer.Integer'>
    """
    if n < 0:
        return

    zero = ZZ.zero()
    one = ZZ.one()

    if not l:
        if n == 0:
            yield []
        return
    if len(l) == 1:
        if n % l[0] == 0:
            yield [n // l[0]]
        return

    k = 0
    cur = [n // l[k] + one]
    rem = n - cur[-1] * l[k] # Amount remaining
    while cur:
        cur[-1] -= one
        rem += l[k]
        if rem == zero:
            yield cur + [zero] * (len(l) - len(cur))
        elif cur[-1] < zero or rem < zero:
            rem += cur.pop() * l[k]
            k -= 1
        elif len(l) == len(cur) + 1:
            if rem % l[-1] == zero:
                yield cur + [rem // l[-1]]
        else:
            k += 1
            cur.append(rem // l[k] + one)
            rem -= cur[-1] * l[k]

def dimension__jacobi_scalar(k, m) :
    raise RuntimeError( "There is a bug in the implementation" )
    m = ZZ(m)
    
    dimension = 0
    for d in (m // m.squarefree_part()).isqrt().divisors() :
        m_d = m // d**2
        dimension += sum ( dimension__jacobi_scalar_f(k, m_d, f)
                            for f in m_d.divisors() )
    
    return dimension

    def __iter__(self):
        """
        Iterate over ``self``.

        EXAMPLES::

            sage: S = SignedPermutations(2)
            sage: [x for x in S]
            [[1, 2], [1, -2], [-1, 2], [-1, -2],
             [2, 1], [2, -1], [-2, 1], [-2, -1]]
        """
        pmone = [ZZ.one(), -ZZ.one()]
        for p in self._P:
            for c in itertools.product(pmone, repeat=self._n):
                yield self.element_class(self, c, p)

    def __init__(self, p, base_ring):
        r"""
        Initialisation function.

        EXAMPLE::

            sage: pAdicWeightSpace(17)
            Space of 17-adic weight-characters defined over '17-adic Field with capped relative precision 20'
        """
        ParentWithBase.__init__(self, base=base_ring)
        p = ZZ(p)
        if not p.is_prime(): 
            raise ValueError, "p must be prime"
        self._p = p
        self._param = Qp(p)((p == 2 and 5) or (p + 1))

def random_solution(B,K):
    r"""
    Returns a random solution in non-negative integers to the equation `a_1 + 2
    a_2 + 3 a_3 + ... + B a_B = K`, using a greedy algorithm.

    Note that this is *much* faster than using
    ``WeightedIntegerVectors.random_element()``.

    INPUT:

    - ``B``, ``K`` -- non-negative integers.

    OUTPUT:

    - list.

    EXAMPLES::

        sage: from sage.modular.overconvergent.hecke_series import random_solution
        sage: random_solution(5,10)
        [1, 1, 1, 1, 0]
    """
    a = []
    for i in xrange(B,1,-1):
        ai = ZZ.random_element((K // i) + 1)
        a.append(ai)
        K = K - ai*i
    a.append(K)
    a.reverse()

    return a

    def __init__(self, field, num_integer_primes=10000, max_iterations=100):
        r"""
        Construct a new iterator of small degree one primes.

        EXAMPLES::

            sage: x = QQ['x'].gen()
            sage: K.<a> = NumberField(x^2 - 3)
            sage: K.primes_of_degree_one_list(3) # random
            [Fractional ideal (2*a + 1), Fractional ideal (-a + 4), Fractional ideal (3*a + 2)]
        """
        self._field = field
        self._poly = self._field.absolute_field("b").defining_polynomial()
        self._poly = ZZ["x"](self._poly.denominator() * self._poly())  # make integer polynomial

        # this uses that [ O_K : Z[a] ]^2 = | disc(f(x)) / disc(O_K) |
        from sage.libs.pari.all import pari

        self._prod_of_small_primes = ZZ(
            pari("TEMPn = %s; TEMPps = primes(TEMPn); prod(X = 1, TEMPn, TEMPps[X])" % num_integer_primes)
        )
        self._prod_of_small_primes //= self._prod_of_small_primes.gcd(self._poly.discriminant())

        self._integer_iter = iter(ZZ)
        self._queue = []
        self._max_iterations = max_iterations

    def _inner_pp(self, pelt1, pelt2):
        """
        Symmetric form between an two elements of the weight lattice
        associated to ``self``.

        EXAMPLES::

            sage: P = RootSystem(['G',2,1]).weight_lattice(extended=true)
            sage: Lambda = P.fundamental_weights()
            sage: V = IntegrableRepresentation(Lambda[0])
            sage: alpha = V.root_lattice().simple_roots()
            sage: Matrix([[V._inner_pp(Lambda[i],P(alpha[j])) for j in V._index_set] for i in V._index_set])
            [  1   0   0]
            [  0 1/3   0]
            [  0   0   1]
            sage: Matrix([[V._inner_pp(Lambda[i],Lambda[j]) for j in V._index_set] for i in V._index_set])
            [  0   0   0]
            [  0 2/3   1]
            [  0   1   2]
        """
        mc1 = pelt1.monomial_coefficients()
        mc2 = pelt2.monomial_coefficients()
        zero = ZZ.zero()
        mc1d = mc1.get('delta', zero)
        mc2d = mc2.get('delta', zero)
        return sum(mc1.get(i,zero) * self._ac[i] * mc2d
                   + mc2.get(i,zero) * self._ac[i] * mc1d
                   for i in self._index_set) \
               + sum(mc1.get(i,zero) * mc2.get(j,zero) * self._ip[ii,ij]
                     for ii, i in enumerate(self._index_set_classical)
                     for ij, j in enumerate(self._index_set_classical))

    def __classcall_private__(cls, n=1, R=0):
        """
        Normalize input to ensure a unique representation.

        EXAMPLES::

            sage: H1 = groups.matrix.Heisenberg(n=2, R=5)
            sage: H2 = groups.matrix.Heisenberg(n=2, R=ZZ.quo(5))
            sage: H1 is H2
            True

            sage: H1 = groups.matrix.Heisenberg(n=2)
            sage: H2 = groups.matrix.Heisenberg(n=2, R=ZZ)
            sage: H1 is H2
            True
        """
        if n not in ZZ or n <= 0:
            raise TypeError("degree of Heisenberg group must be a positive integer")
        if R in ZZ:
            if R == 0:
                R = ZZ
            elif R > 1:
                R = ZZ.quo(R)
            else:
                raise ValueError("R must be a positive integer")
        elif R is not ZZ and R not in Rings().Finite():
            raise NotImplementedError("R must be a finite ring or ZZ")
        return super(HeisenbergGroup, cls).__classcall__(cls, n, R)

    def _inner_qq(self, qelt1, qelt2):
        """
        Symmetric form between two elements of the root lattice
        associated to ``self``.

        EXAMPLES::

            sage: P = RootSystem(['F',4,1]).weight_lattice(extended=true)
            sage: Lambda = P.fundamental_weights()
            sage: V = IntegrableRepresentation(Lambda[0])
            sage: alpha = V.root_lattice().simple_roots()
            sage: Matrix([[V._inner_qq(alpha[i], alpha[j]) for j in V._index_set] for i in V._index_set])
            [   2   -1    0    0    0]
            [  -1    2   -1    0    0]
            [   0   -1    2   -1    0]
            [   0    0   -1    1 -1/2]
            [   0    0    0 -1/2    1]

        .. WARNING:

            If ``qelt1`` or ``qelt1`` accidentally gets coerced into
            the extended weight lattice, this will return an answer,
            and it will be wrong. To make this code robust, parents
            should be checked. This is not done since in the application
            the parents are known, so checking would unnecessarily slow
            us down.
        """
        mc1 = qelt1.monomial_coefficients()
        mc2 = qelt2.monomial_coefficients()
        zero = ZZ.zero()
        return sum(mc1.get(i, zero) * mc2.get(j, zero)
                   * self._cartan_matrix[i,j] / self._eps[i]
                   for i in self._index_set for j in self._index_set)

    def long_element(self, index_set=None):
        """
        Return the longest element of ``self``, or of the
        parabolic subgroup corresponding to the given ``index_set``.

        INPUT:

        - ``index_set`` -- (optional) a subset (as a list or iterable)
          of the nodes of the indexing set

        EXAMPLES::

            sage: S = SignedPermutations(4)
            sage: S.long_element()
            [-1, -2, -3, -4]

        TESTS:

        Check that this is the element of maximal length (:trac:`25200`)::

            sage: S = SignedPermutations(4)
            sage: S.long_element().length() == max(x.length() for x in S)
            True
            sage: all(SignedPermutations(n).long_element().length() == n^2
            ....:     for n in range(2,10))
            True
        """
        if index_set is not None:
            return super(SignedPermutations, self).long_element()
        return self.element_class(self, [-ZZ.one()] * self._n, self._P.one())

    def residue_field(self):
        r"""
        Return the residue class field of this ideal, which must be prime.

        .. TODO::

            Implement this for more general rings. Currently only defined
            for `\ZZ` and for number field orders.

        EXAMPLES::

            sage: P = ZZ.ideal(61); P
            Principal ideal (61) of Integer Ring
            sage: F = P.residue_field(); F
            Residue field of Integers modulo 61
            sage: pi = F.reduction_map(); pi
            Partially defined reduction map:
              From: Rational Field
              To:   Residue field of Integers modulo 61
            sage: pi(123/234)
            6
            sage: pi(1/61)
            Traceback (most recent call last):
            ...
            ZeroDivisionError: Cannot reduce rational 1/61 modulo 61: it has negative valuation
            sage: lift = F.lift_map(); lift
            Lifting map:
              From: Residue field of Integers modulo 61
              To:   Integer Ring
            sage: lift(F(12345/67890))
            33
            sage: (12345/67890) % 61
            33

        TESTS::

            sage: ZZ.ideal(96).residue_field()
            Traceback (most recent call last):
            ...
            ValueError: The ideal (Principal ideal (96) of Integer Ring) is not prime

        ::

            sage: R.<x>=QQ[]
            sage: I=R.ideal(x^2+1)
            sage: I.is_prime()
            True
            sage: I.residue_field()
            Traceback (most recent call last):
            ...
            TypeError: residue fields only supported for polynomial rings over finite fields.
        """
        if not self.is_prime():
            raise ValueError("The ideal (%s) is not prime"%self)
        from sage.rings.integer_ring import ZZ
        if self.ring() is ZZ:
            return ZZ.residue_field(self, check = False)
        raise NotImplementedError("residue_field() is only implemented for ZZ and rings of integers of number fields.")

def allbsd(line):
    r""" Parses one line from an allbsd file.  Returns the label and a
    dict containing fields with keys 'conductor', 'iso', 'number',
    'ainvs', 'rank', 'torsion', 'torsion_primes', 'tamagawa_product',
    'real_period', 'special_value', 'regulator', 'sha_an', 'sha',
    'sha_primes', all values being strings or floats or ints or lists
    of ints.

    Input line fields:

    conductor iso number ainvs rank torsion tamagawa_product real_period special_value regulator sha_an

    Sample input line:

    11 a 1 [0,-1,1,-10,-20] 0 5 5 1.2692093042795534217 0.25384186085591068434 1 1.00000000000000000000

    """
    data = split(line)
    label = data[0] + data[1] + data[2]
    ainvs = parse_ainvs(data[3])

    torsion = ZZ(data[5])
    sha_an = RR(data[10])
    sha = sha_an.round()
    sha_primes = sha.prime_divisors()
    torsion_primes = torsion.prime_divisors()

    data = {
        'conductor': int(data[0]),
        'iso': data[0] + data[1],
        'number': int(data[2]),
        'ainvs': ainvs,
        'rank': int(data[4]),
        'tamagawa_product': int(data[6]),
        'real_period': float(data[7]),
        'special_value': float(data[8]),
        'regulator': float(data[9]),
        'sha_an': float(sha_an),
        'sha':  int(sha),
        'sha_primes':  [int(p) for p in sha_primes],
        'torsion':  int(torsion),
        'torsion_primes':  [int(p) for p in torsion_primes]
        }

    return label, data