natural.py

Aller à la documentation de ce fichier.

#!/usr/bin/env python
# -*- coding: latin-1 -*-
##\package DSPython.natural Naturels : fonctions arithmétiques

##\file
# Naturels : fonctions arithmétiques

# (c) Olivier Pirson --- DragonSoft
# http://www.opimedia.be/DS/
# Débuté le 25 septembre 2006
####################################
from __future__ import division
from __future__ import print_function

## Date du dernier changement pour ce module
VERSION = 'natural --- 2010 April 12'

import fractions, math, types

import DSPython
import DSPython.bit32 as bit32
import DSPython.nat32 as nat32



# ###########
# Fonctions #
#############
## n en binaire dans un string
def bin(n):
    """Renvoie un string représentant n en binaire
      (Si n == 0 alors renvoie '0')

    Pre: n: naturel

    Result: string

    O(n) = lg(n)"""
    assert DSPython.natural_is(n), n

    if n <= bit32.MERSENNE32:
        return bit32.bin(n)
    else:
        l = [bit32.bin(n & bit32.MERSENNE32)]
        while n > bit32.MERSENNE32:
            if len(l[0]) < 32:
                l.insert(0, '0' * (32 - len(l[0])))
            n >>= 32
            l.insert(0, bit32.bin(n & bit32.MERSENNE32))
        return ''.join(l)


## Coefficient binomial de n et k
def binom(n, k):
    """Renvoie le coefficient binomial (n)
                                    (k)

    Pre: n: naturel
         k: naturel

    Result: naturel

    O(n, k) = ..."""
    assert DSPython.natural_is(n), n
    assert DSPython.natural_is(k), k

    if k <= n:
        if n - k < k:
            k = n - k
        return falling_factorial_pow(n, k) // math.factorial(k)
    else:
        return 0


## Le bit d'indice i de n vaut 1 ?
def bit(n, i):
    """Renvoie True si le bit d'indice i de n vaut 1,
      False sinon

    Pre: n: naturel
         i: naturel

    Result: bool

    O(n) = 1"""
    assert DSPython.natural_is(n), n
    assert DSPython.natural_is(i), i

    return bool(n & (1 << i))


## n avec son bit d'indice i à b
def bitset(n, i, b):
    """Si b alors renvoie n avec son bit d'indice i à 1,
      sinon renvoie n avec son bit d'indice i à 0

    Pre: n: naturel
         i: naturel
         b: bool

    Result: naturel

    O(n) = 1"""
    assert DSPython.natural_is(n), n
    assert DSPython.natural_is(i), i

    return (n | (1 << i) if b
            else n & ~(1 << i))


## n avec son bit d'indice i à 0
def bitset0(n, i):
    """Renvoie n avec son bit d'indice i à 0

    Pre: n: naturel
         i: naturel

    Result: naturel

    O(n) = 1"""
    assert DSPython.natural_is(n), n
    assert DSPython.natural_is(i), i

    return n & ~(1 << i)


## n avec son bit d'indice i à 1
def bitset1(n, i):
    """Renvoie n avec son bit d'indice i à 1

    Pre: n: naturel
         i: naturel

    Result: naturel

    O(n) = 1"""
    assert DSPython.natural_is(n), n
    assert DSPython.natural_is(i), i

    return n | (1 << i)


## m et n sont premiers entre eux ?
def coprime_is(m, n):
    """Renvoie True si m et n sont premiers entre eux,
      False sinon
      (Si m == n == 0 alors renvoie False)

    Pre: m: naturel
         n: naturel

    O(m, n) = ..."""
    assert DSPython.natural_is(m), m
    assert DSPython.natural_is(n), n

    return (not ((m&1 == 0) and (n&1 == 0))) and (fractions.gcd(m, n) == 1)


##\brief Distance de Dominici
#
# (cf. <i>An Arithmetic Metric</i>,
# Diego <span style="font-variant:small-caps">Dominici</span>,
# <a href="http://arxiv.org/abs/0906.0632/"
#   target="_blank"><tt>http://arxiv.org/abs/0906.0632/</tt></a>)
def distance_dominici(a, b):
    """Renvoie la distance de Dominici entre a et b

    Pre: a: naturel >= 1
         b: naturel >= 1

    Result: naturel

    O(s) = ..."""
    assert DSPython.natural_is(a), a
    assert a > 0, a
    assert DSPython.natural_is(b), b
    assert b > 0, b

    import DSPython.factors as factors

    return factors.distance_dominici(factors.primaries(a), factors.primaries(b))


## Liste des diviseurs de n
def divisors(n):
    """Renvoie la liste des diviseurs de n
      (dans l'ordre strictement croissant)
      (Si n == 1 alors renvoie [1])

    Pre: n: naturel >= 1

    Result: séquence strictement ordonnée non vide de naturels >= 1

    O(n) = ..."""
    assert DSPython.natural_is(n), n
    assert n > 0, n

    l = []
    for d in range(1, n):
        if n%d == 0:
            l.append(d)
    l.append(n)
    return l


## Liste des diviseurs de n restreint à la condition cond
def divisors_cond(n, cond):
    """Renvoie la liste des diviseurs de n vérifiant la condition cond
      (dans l'ordre strictement croissant)
    Pre: n: naturel >= 1
         cond: fonction à une variable naturelle et renvoyant un bool
    Result: séquence strictement ordonnée non vide de naturels >= 1
    O(n) = ..."""
    assert DSPython.natural_is(n), n
    assert n > 0, n
    assert isinstance(cond, types.FunctionType), type(cond)

    l = []
    for d in range(1, n + 1):
        if (n%d == 0) and cond(d):
            l.append(d)
    return l


## n!
def factorial(n):
    """Renvoie n!, la factorielle de n
      == 1 * 2 * 3 * ... * n
      (Si n == 0 alors renvoie 1)

    Pre: n: naturel

    Result: naturel >= 1

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    return math.factorial(n)


## k<sup>e</sup> puissance factorielle descendante de n
def falling_factorial_pow(n, k):
    """Renvoie la kème puissance factorielle descendante de n
      == n * (n - 1) * (n - 2) * ... * (n - k + 1)

    Pre: n: naturel
         k: naturel

    Result: naturel

    O(n, k) = ..."""
    assert DSPython.natural_is(n), n
    assert DSPython.natural_is(k), k

    if n - 1 > k > 0:               # n - 1 > k > 0
        if n <= 12:
            return nat32.FACTORIAL_TUPLE[n] // nat32.FACTORIAL_TUPLE[n - k]
        else:
            if k&1 == 0:
                f = n * (n - 1)
                n -= 2
                k -= 2
            else:
                f = n
                n -= 1
            k >>= 1
            while k > 0:  # multiplie les 2k facteurs restants
                f *= n * (n - 1)
                n -= 2
                k -= 1
            return f
    elif (n - 1 == k) or (n == k):  # n = k + (0 ou 1)
        return math.factorial(n)
    elif k == 0:                    # n > 1, k = 0
        return 1
    else:                       # n < k > 0
        return 0


#
# Nombres de Fibonacci :
#   F_0 = 0
#   F_1 = 1
#   pour tout k entier : F_k = F_(k-2) + F_(k-1)
#
#   k   : -1 0 1 2 3 4 5 6  7  8  9 10 11  12  13  14  15  16   17   18   19   20    21...
#   F_k :  1 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
#
#   ==> Pour tout k naturel : F_(2k-1) == F_(k  )**2 + F_(k-1)**2
#                             F_(2k  ) == F_(k+1)**2 - F_(k-1)**2
#                             F_(2k+1) == F_(k+1)**2 + F_(k  )**2
#

## F<sub>k</sub>
def fibonacci(k):
    """Renvoie F_k, le kième nombre de Fibonacci

    Pre: k: naturel

    Result: naturel

    O(k) = ..."""
    assert DSPython.natural_is(k), k

    return fibonacci2(k)[1]


## (F<sub>k-1</sub>, F<sub>k</sub>)
def fibonacci2(k):
    """Renvoie (F_(k-1), F_k), les (k-1)ième et kième nombres de Fibonacci

    Pre: k: naturel

    Result: couple de naturels

    O(k) = ..."""
    assert DSPython.natural_is(k), k

    if k > 47:
        Fq_1, Fq = fibonacci2(k//2)  # F_(q-1), F_q avec q == k/2
        Fq1S = Fq + Fq_1             # F_(q+1)
        Fq1S *= Fq1S                 # F_(q+1)**2
        if k&1 == 0:  # k pair
            Fq_1S = Fq_1 * Fq_1  # F_(q-1)**2
            return (Fq*Fq + Fq_1S, Fq1S - Fq_1S)     # ( F_(2q-1), F_(2q  ) )
        else:         # k impair
            return (Fq1S - Fq_1*Fq_1, Fq1S + Fq*Fq)  # ( F_(2q  ), F_(2q+1) )
    else:
        return nat32.fibonacci2(k)


## Le naturel n est un nombre de Fibonacci ?
def fibonacci_is(n):
    """Renvoie True si n est un nombre de Fibonacci,
      False sinon

    Pre: n: naturel

    Result: bool

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    if n <= bit32.MERSENNE32:
        return nat32.fibonacci_is(n)
    else:
        Fk_1, Fk = fibonacci2(48)
        while Fk < n:
            Fk_1, Fk = Fk, Fk+Fk_1
        return Fk == n


## Indice du nombre de Fibonacci correspondant au naturel n, ou None
def fibonacci_to_index(n):
    """Si n == F_k alors renvoie k
                      (si n == 1 alors renvoie toujours 1, jamais 2),
                sinon renvoie None

    Pre: n naturel ou None

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    if n <= bit32.MERSENNE32:
        return nat32.fibonacci_to_index(n)
    else:
        k = 48
        Fk_1, Fk = fibonacci2(k)
        while Fk < n:
            Fk_1, Fk = Fk, Fk+Fk_1
            k += 1
        return (k if Fk == n
                else None)


## PGCD de m et n (Plus Grand Commun Diviseur/ Greatest Common Divisor)
def gcd(m, n):
    """Renvoie le PGCD de m et n
      (Si m == n == 0 alors renvoie 0)
      (Plus Grand Commun Diviseur/ Greatest Common Divisor)

    Pre: m: naturel
         n: naturel

    Result: naturel

    O(m, n) = ..."""
    assert DSPython.natural_is(m), m
    assert DSPython.natural_is(n), n

    return fractions.gcd(m, n)


## PPCM de m et n (Plus Petit Commun Multiple/ Least Common Multiple)
def lcm(m, n):
    """Renvoie le PPCM de m et n
      (Si m == 0 ou n == 0 alors renvoie 0)
      (Plus Petit Commun Multiple/ Least Common Multiple)

    Pre: m: naturel
         n: naturel

    Result: naturel

    O(m, n) = ..."""
    assert DSPython.natural_is(m), m
    assert DSPython.natural_is(n), n

    return (m*n//fractions.gcd(m, n) if (m != 0) and (n != 0)
            else 0)


## lg(n) == log<sub>2</sub>(n) == nbbits(n) - 1 == l'indice du dernier bit à 1 de n
## &nbsp; &nbsp; (n != 0)
def lg(n):
    """Renvoie lg(n) == log_2(n) == nbbits(n) - 1
      == l'indice du dernier bit à 1 de n

    Pre: n: 1 <= naturel

    Result: naturel

    O(n) = 1"""
    assert DSPython.natural_is(n), n

    return nbbits(n) - 1


#
# Nombres de Lucas :
#   L_0 = 2
#   L_1 = 1
#   pour tout k entier : L_k = L_(k-2) + L_(k-1)
#
#   k   : 0 1 2 3 4 5   6  7  8  9 10 11  12  13  14  15  16   17   18   19   20...
#   L_k : 2 1 3 4 7 11 18 29 47 76
#
#   ==> Pour tout k naturel : L_k == F_{k-1} + F_{k+1} == 2F_{k-1} + F_k
#

## L<sub>k</sub>
def lucas(k):
    """Renvoie L_k, le kième nombre de Lucas

    Pre: k: naturel

    Result: naturel

    O(k) = ..."""
    assert DSPython.natural_is(k), k

    Fk_1, Fk= fibonacci2(k)
    return (Fk_1 << 1) + Fk


## (L<sub>k-1</sub>, L<sub>k</sub>)
def lucas2(k):
    """Renvoie (L_(k-1), L_k), les (k-1)ième et kième nombres de Lucas

    Pre: k: naturel

    Result: (-1, 2) si k == 0, sinon couple de naturels

    O(k) = ..."""
    assert DSPython.natural_is(k), k

    if k > 0:
        Fk_2, Fk_1= fibonacci2(k - 1)
        Fk = Fk_1 + Fk_2
        return (Fk + Fk_2, (Fk_1 << 1) + Fk)
    else:
        return (-1, 2)


## Le naturel n est un nombre de Lucas ?
def lucas_is(n):
    """Renvoie True si n est un nombre de Lucas,
      False sinon

    Pre: n: naturel

    Result: bool

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    if n != 2:
        Lk_1, Lk = 2, 1
        while Lk < n:
            Lk_1, Lk = Lk, Lk + Lk_1
        return Lk == n
    else:
        return True


## Indice du nombre de Lucas correspondant au naturel n, ou None
def lucas_to_index(n):
    """Si n == L_k alors renvoie k
                sinon renvoie None

    Pre: n: naturel

    Result: naturel ou None

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    if n != 2:
        k = 1
        Lk_1, Lk = 2, 1
        while Lk < n:
            Lk_1, Lk = Lk, Lk + Lk_1
            k += 1
        return (k if Lk == n
                else None)
    else:
        return 0


## M<sub>k</sub>
def mersenne(k):
    """Renvoie le kième nombre de Mersenne Mk == 2**k - 1

    Pre: k: naturel

    Result: naturel

    O(k) = 1"""
    assert DSPython.natural_is(k), k

    return (bit32.MERSENNE_TUPLE[k] if k <= 32
            else (2 << (k - 1)) - 1)
#???        else (2L << (k - 1)) - 1L)


## Indice du nombre de Mersenne correspondant au naturel n, ou None
def mersenne_to_index(n):
    """Si n == M_k alors renvoie k
                sinon renvoie None

    Pre: n: naturel ou None

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    k = scan0(n)
    return (k if mersenne(k) == n
            else None)


## Fonction de Mertens
def mertens(n):
    """Renvoie la fonction de Mertens en n
      (Si n == 0 alors renvoie 0)

    Pre: n: naturel

    Result: entier

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    import DSPython.factors as factors

    r = 0
    for i in range(1, n + 1):
        r += factors.mobius(factors.primaries(i))
    return r


## Nombre de bits à 0 de n
def nbbits0(n):
    """Renvoie le nombre de bits à 0 de n
      (sans tenir compte des 0 après le dernier 1)
      (Si n == 0 alors renvoie 0)

    Pre: n: naturel

    Result: naturel

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    nb = 0
    while n > 0:
        n32 = n & bit32.MERSENNE32
        n >>= 32
        if n32 > 0:
            nb += bit32.nbbits0(n32)
            if n > 0:
                 nb += 31 - bit32.rscan1(n32)
        elif n > 0:
            nb += 32
    return nb


## Nombre de bits à 1 de n
def nbbits1(n):
    """Renvoie le nombre de bits à 1 de n
      (Si n == 0 alors renvoie 0)

    Pre: n: naturel

    Result: naturel

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    nb = 0
    while n > 0:
        nb += bit32.nbbits1(n & bit32.MERSENNE32)
        n >>= 32
    return nb


## Nombre de bits de n
def nbbits(n):
    """Renvoie le nombre de bits de n
      == nbbits0(n) + nbbits1(n)
      (sans tenir compte des 0 après le dernier 1)
      (Si n == 0 alors renvoie 0)

    Pre: n: naturel

    Result: naturel

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    k = 0
    while n > bit32.MERSENNE32:
        n >>= 32
        k += 1
    return (k<<5) + bit32.nbbits(n)


## Produit des facteurs non communs de m et n (Not common Factors Product)
def nfp(m, n):
    """Renvoie le produit des facteurs non communs de m et n
      (Si m == 0 ou n == 0 alors renvoie 0)
      (Not common Factors Product)

    Pre: m: naturel
         n: naturel

    Result: naturel

    O(m, n) = ..."""
    assert DSPython.natural_is(m), m
    assert DSPython.natural_is(n), n

    return (m*n//(fractions.gcd(m, n)**2) if (m != 0) and (n != 0)
            else 0)


## Liste des nontotatives de n
def nontotatives(n):
    """Renvoie la liste des nontotatives de n
      (dans l'ordre strictement croissant)
      càd les naturels non nuls <= n et non premiers avec n
      (Si n == 0 ou 1 alors renvoie [])

    Pre: n: naturel

    Result: séquence strictement ordonnée de naturels

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    if n > 1:
        l = []
        for d in range(2, n):
            if not coprime_is(n, d):
                l.append(d)
        l.append(n)
        return l
    else:
        return []


## Nontotient de n
def nontotient(n):
    """Renvoie le nombre de nontotatives de n
      (Si n == 0 ou 1 alors renvoie 0)

    Pre: n: naturel

    Result: naturel

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    import DSPython.factors as factors

    return (n - factors.totient(factors.primaries(n)) if n > 1
            else 0)


## Nombre polygonal à k côtés de n
def polygonal(k, n):
    """Nombre polygonal à k côtés de n

    Pre: k: naturel >= 2
         n: naturel

    Result: naturel

    O(n) = ..."""
    assert DSPython.natural_is(k), k
    assert k >= 2, k
    assert DSPython.natural_is(n), n

    return ((n*(n - 1)) >> 1) * (k - 2) + n


## 2<sup>k</sup>
def pow2(k):
    """Renvoie la kième puissance de 2 : 2**k

    Pre: k: naturel

    Result: naturel >= 1

    O(k) = 1"""
    assert DSPython.natural_is(k), k

    return (bit32.POW2_TUPLE[k] if k < 32
            else 1<<k)


## 3<sup>k</sup>
def pow3(k):
    """Renvoie la kième puissance de 3 : 3**k

    Pre: k: naturel

    Result: naturel >= 1

    O(k) = ..."""
    assert DSPython.natural_is(k), k

    k, rem = divmod(k, 20)
    return (nat32.POW3_TUPLE[20]**k) * nat32.POW3_TUPLE[rem]


## n est premier ?
def prime_is(n):
    """Renvoie True si n est premier,
      False sinon

    Pre: n: naturel

    Result: bool

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    if n < 2**32:
        return nat32.prime_is(n)
    elif n <= 2**32 + 14:
        return False
    else:
        raise NotImplementedError


## Nombre pyramidal à c côtés de n
def pyramidal(k, n):
    """Nombre pyramidal à k côtés de n

    Pre: k: naturel >= 2
         n: naturel

    Result: naturel

    O(n) = ..."""
    assert DSPython.natural_is(k), k
    assert k >= 2, k
    assert DSPython.natural_is(n), n

    s = n**2
    return (s*n*(k - 2) + s*3 - n*(k - 5)) // 6


## k<sup>e</sup> puissance factorielle montante de n
def rising_factorial_pow(n, k):
    """Renvoie la kème puissance factorielle montante de n
      == n * (n + 1) * (n + 2) * ... * (n + k - 1)

    Pre: n: naturel
         k: naturel

    Result: naturel

    O(n, k) = ..."""
    assert DSPython.natural_is(n), n
    assert DSPython.natural_is(k), k

    if (n > 0) and (k > 0):  # n, k > 0
        if n + k < 14:  # n + k - 1 <= 12
            return nat32.FACTORIAL_TUPLE[n + k - 1] // nat32.FACTORIAL_TUPLE[n - 1]
        else:
            if k&1 == 0:
                f = n * (n + 1)
                n += 2
                k -= 2
            else:
                f = n
                n += 1
            k >>= 1
            while k > 0:  # multiplie les 2k facteurs restants
                f *= n * (n + 1)
                n += 2
                k -= 1
            return f
    elif k == 0:             # n >= k = 0
        return 1
    else:                    # n = 0 < k
        return 0


## Indice du dernier bit à 1 de, n == nbbits(n) - 1 ou None
def rscan1(n):
    """Renvoie l'indice du dernier bit à 1 de n
      ou None si n == 0

    Pre: n: naturel

    Result: naturel ou None

    O(n) = 1"""
    assert DSPython.natural_is(n), n

    return (nbbits(n) - 1 if n > 0
            else None)


## Indice du premier bit à 0 de n
def scan0(n):
    """Renvoie l'indice du premier bit à 0 de n
      (si n == 0 alors renvoie 0)

    Pre: n: naturel

    Result: naturel

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    k = 0
    while n & bit32.MERSENNE32 == bit32.MERSENNE32:
        n >>= 32
        k += 1
    return (k << 5) + bit32.scan0(n & bit32.MERSENNE32)


## Indice du premier bit à 1 de n, ou None
def scan1(n):
    """Renvoie l'indice du premier bit à 1 de n
      ou None si n == 0

    Pre: n: naturel

    Result: naturel ou None

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    if n > 0:
        k = 0
        while n&bit32.MERSENNE32 == 0:
            n >>= 32
            k += 1
        return (k << 5) + bit32.scan1(n & bit32.MERSENNE32)
    else:
        return None


## Liste des totatives de n
def totatives(n):
    """Renvoie la liste des totatives de n
      (dans l'ordre strictement croissant)
      càd les naturels non nuls <= n et premiers avec n
      (Si n == 0 alors renvoie []
       Si n == 1 alors renvoie [1])

    Pre: n: naturel

    Result: séquence strictement ordonnée de naturels

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    if n > 0:
        l = [1]
        for d in range(2, n):
            if coprime_is(n, d):
                l.append(d)
        return l
    else:
        return []


## Totient de n (fonction phi, indicatrice d'Euler)
def totient(n):
    """Si n > 0 alors renvoie le nombre de totatives de n
             sinon renvoie 1
      (Si n == 0 ou 1 alors renvoie 1)

    Pre: n: naturel

    Result: naturel >= 1

    O(n) = ..."""
    assert DSPython.natural_is(n), n

    import DSPython.factors as factors

    return (factors.totient(factors.primaries(n)) if n > 1
            else 1)


## Liste des diviseurs unitaires de n
def unitarydivisors(n):
    """Renvoie la liste des diviseurs unitaires de n
      (dans l'ordre strictement croissant)
      (Si n == 1 alors renvoie [1])

    Pre: n: naturel >= 1

    Result: séquence strictement ordonnée non vide de naturels >= 1

    O(n) = ..."""
    assert DSPython.natural_is(n), n
    assert n > 0, n

    l = [1]
    for d in range(2, n + 1):
        (q, r) = divmod(n, d)
        if (r == 0) and coprime_is(q, d):
            l.append(d)
    return l



# ######\cond MAINTEST
# Main #
########
if __name__ == '__main__':
    def main_test():
        """Test du module"""
        import sys

        try:
            if not 'profile' in dir():
                import psyco
                psyco.full()
        except ImportError:
            pass

        import DSPython.debug as debug

        import DSPython.factors as factors

        debug.test_begin(VERSION, __debug__)

        print('bin()...', end=''); sys.stdout.flush()
        assert bin(0) == '0', bin(0)
        assert bin(1) == '1', bin(1)
        for i in range(1, 50):
            assert bin(2**i - 1) == '1'*i, (i, bin(2**i - 1))                    #  1...11
            assert bin(2**i) == '1' + '0'*i, (i, bin(2**i))                      # 10...00
            assert bin(2**i + 1) == '1' + '0'*(i - 1) + '1', (i, bin(2**i + 1))  # 10...01
        for n in range(1, 16384):
            assert int(bin(n), 2) == n, (n, bin(n))
            assert len(bin(n)) == nbbits(n), (n, bin(n), nbbits(n))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**40, 1000000000):
                assert int(bin(n), 2) == n, (n, bin(n))
                assert len(bin(n)) == nbbits(n), (n, bin(n), nbbits(n))
            for n in range(2**32 - 16384, 2**32 + 16384):
                assert int(bin(n), 2) == n, (n, bin(n))
                assert len(bin(n)) == nbbits(n), (n, bin(n), nbbits(n))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('binom()...', end=''); sys.stdout.flush()
        for n in range(100):
            assert binom(n, 0) == 1, (n, binom(n, 0))
            assert binom(n, 1) == n, (n, binom(n, 1))
            for k in range(1, 10):
                assert binom(n, n+k) == 0, (n, k, binom(n, n+k))
            s = 0
            for k in range(n + 1):
                s += binom(n, k)
            assert s == 2**n, (n, s, 2**n)
        for n in range(1, 50):
            for k in range(1, n + 1):
                assert binom(n, k) == binom(n, n - k), (n, k, binom(n, k), binom(n, n - k))
                assert binom(n, k) == binom(n - 1, k - 1) * n // k, \
                       (n, k, binom(n, k), binom(n - 1, k - 1))
                assert binom(n, k) == binom(n, k - 1) * (n - k + 1) // k, \
                       (n, k, binom(n, k), binom(n, k - 1) * (n - k + 1))
        for n in range(3, 100):
            assert binom(n, 2) == ((n - 1)*n)//2, (n, binom(n, 2), ((n - 1)*n)//2)
        print('ok'); sys.stdout.flush()


        print('bit()...', end=''); sys.stdout.flush()
        for i in range(40):
            assert bit(2**i, i) == True, (i, 2**i, bit(2**i, i))
            for j in range(40):
                assert bit(0, i)            == False, (i, bit(0, i))
                assert bit(mersenne(40), i) == True,  (i, bit(mersenne(40), i))
                if i != j:
                    assert bit(2**i, j) == False, (i, j, 2**i, bit(2**i, j))
        print('ok'); sys.stdout.flush()


        print('bitset()...', end=''); sys.stdout.flush()
        for n in range(2048):
            for i in range(32):
                if bit(n, i):
                    assert bitset(n, i, False) == n - (1<<i), (n, n - (1<<i), bitset(n, i, False))
                    assert bitset(n, i, True) == n, (n, bitset(n, i, True))
                else:
                    assert bitset(n, i, False) == n, (n, bitset(n, i, False))
                    assert bitset(n, i, True) == n + (1<<i), (n, n + (1<<i), bitset(n, i, True))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**32, 10000000):
                for i in range(32):
                    if bit(n, i):
                        assert bitset(n, i, False) == n - (1<<i), (n, n - (1<<i),
                                                                   bitset(n, i, False))
                        assert bitset(n, i, True) == n, (n, bitset(n, i, True))
                    else:
                        assert bitset(n, i, False) == n, (n, bitset(n, i, False))
                        assert bitset(n, i, True) == n + (1<<i), (n, n + (1<<i), bitset(n, i, True))
            for n in range(2**32 - 2048, 2**32 + 5000):
                for i in range(32):
                    if bit(n, i):
                        assert bitset(n, i, False) == n - (1<<i), (n, n - (1<<i),
                                                                   bitset(n, i, False))
                        assert bitset(n, i, True) == n, (n, bitset(n, i, True))
                    else:
                        assert bitset(n, i, False) == n, (n, bitset(n, i, False))
                        assert bitset(n, i, True) == n + (1<<i), (n, n + (1<<i), bitset(n, i, True))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('bitset0()...', end=''); sys.stdout.flush()
        for n in range(2048):
            for i in range(32):
                if bit(n, i):
                    assert bitset0(n, i) == n - (1<<i), (n, n - (1<<i), bitset0(n, i))
                else:
                    assert bitset0(n, i) == n, (n, bitset0(n, i))
            assert bitset0(n, i) == bitset(n, i, False), (n, bitset(n, i, False), bitset0(n, i))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**32, 10000000):
                for i in range(32):
                    if bit(n, i):
                        assert bitset0(n, i) == n - (1<<i), (n, n - (1<<i), bitset0(n, i))
                    else:
                        assert bitset0(n, i) == n, (n, bitset0(n, i))
                assert bitset0(n, i) == bitset(n, i, False), (n, bitset(n, i, False), bitset0(n, i))
            for n in range(2**32 - 2048, 2**32 + 5000):
                for i in range(32):
                    if bit(n, i):
                        assert bitset0(n, i) == n - (1<<i), (n, n - (1<<i), bitset0(n, i))
                    else:
                        assert bitset0(n, i) == n, (n, bitset0(n, i))
                assert bitset0(n, i) == bitset(n, i, False), (n, bitset(n, i, False), bitset0(n, i))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('bitset1()...', end=''); sys.stdout.flush()
        for n in range(2048):
            for i in range(32):
                if bit(n, i):
                    assert bitset1(n, i) == n, (n, bitset1(n, i))
                else:
                    assert bitset1(n, i) == n + (1<<i), (n, n + (1<<i), bitset1(n, i))
            assert bitset1(n, i) == bitset(n, i, True), (n, bitset(n, i, True), bitset1(n, i))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**32, 10000000):
                for i in range(32):
                    if bit(n, i):
                        assert bitset1(n, i) == n, (n, bitset1(n, i))
                    else:
                        assert bitset1(n, i) == n + (1<<i), (n, n + (1<<i), bitset1(n, i))
                assert bitset1(n, i) == bitset(n, i, True), (n, bitset(n, i, True), bitset1(n, i))
            for n in range(2**32 - 2048, 2**32 + 5000):
                for i in range(32):
                    if bit(n, i):
                        assert bitset1(n, i) == n, (n, bitset1(n, i))
                    else:
                        assert bitset1(n, i) == n + (1<<i), (n, n + (1<<i), bitset1(n, i))
                assert bitset1(n, i) == bitset(n, i, True), (n, bitset(n, i, True), bitset1(n, i))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('coprime_is()...', end=''); sys.stdout.flush()
        assert not coprime_is(0, 0), coprime_is(0, 0)
        assert coprime_is(1, 0), coprime_is(1, 0)
        assert coprime_is(0, 1), coprime_is(0, 1)
        assert coprime_is(1, 1), coprime_is(1, 1)
        for m in range(50):
            if m != 1:
                assert not coprime_is(m, 0), (m, coprime_is(m, 0))
            assert coprime_is(m, 1), (m, coprime_is(m, 1))
            for p in nat32.PRIME_16_ARRAY[:100]:
                if m%p == 0:
                    assert not coprime_is(m, p), (m, p, coprime_is(m, p))
                else:
                    assert coprime_is(m, p), (m, p, coprime_is(m, p))
            assert coprime_is(m, m + 1), m
        for m in range(50):
            for n in range(10):
                assert coprime_is(m, n) == coprime_is(n, m), (m, n, coprime_is(m, n),
                                                              fractions.gcd(n, m))
        for m in range(2**32 - 4096, 2**32 + 4096):
            assert coprime_is(m, m + 1), m
        print('ok'); sys.stdout.flush()


        print('distance_dominici()...', end='') ; sys.stdout.flush()
        assert distance_dominici(11, 12) == 4, distance_dominici(11, 12)
        for a in range(1, 50):
            assert distance_dominici(a, a) == 0, distance_dominici(a, a)
            for b in range(1, 50):
                assert distance_dominici(a, b) == distance_dominici(b, a), \
                       (distance_dominici(a, b), distance_dominici(b, a))
        print('???', end='')
        print('ok') ; sys.stdout.flush()


        print('divisors()...', end=''); sys.stdout.flush()
        assert divisors(1) == [1],          divisors(1)
        assert divisors(2) == [1, 2],       divisors(2)
        assert divisors(3) == [1, 3],       divisors(3)
        assert divisors(4) == [1, 2, 4],    divisors(4)
        assert divisors(5) == [1, 5],       divisors(5)
        assert divisors(6) == [1, 2, 3, 6], divisors(6)
        for n in range(1, 1000):
            for d in divisors(n):
                assert d > 0, (n, d)
                assert n%d == 0, (n, d, n%d)
        print('ok'); sys.stdout.flush()


        print('divisors_cond()...', end=''); sys.stdout.flush()
        f = lambda d: True
        assert divisors_cond(1, f) == [1],          divisors_cond(1, f)
        assert divisors_cond(2, f) == [1, 2],       divisors_cond(2, f)
        assert divisors_cond(3, f) == [1, 3],       divisors_cond(3, f)
        assert divisors_cond(4, f) == [1, 2, 4],    divisors_cond(4, f)
        assert divisors_cond(5, f) == [1, 5],       divisors_cond(5, f)
        assert divisors_cond(6, f) == [1, 2, 3, 6], divisors_cond(6, f)
        f = lambda d: d%2 == 0
        assert divisors_cond(1, f) == [],     divisors_cond(1, f)
        assert divisors_cond(2, f) == [2],    divisors_cond(2, f)
        assert divisors_cond(3, f) == [],     divisors_cond(3, f)
        assert divisors_cond(4, f) == [2, 4], divisors_cond(4, f)
        assert divisors_cond(5, f) == [],     divisors_cond(5, f)
        assert divisors_cond(6, f) == [2, 6], divisors_cond(6, f)
        for n in range(1, 1000):
            assert divisors_cond(n, lambda d: False) == [], \
                   (n, divisors_cond(n, lambda d: False))
            for d in divisors_cond(n, lambda d: True):
                assert d > 0, (n, d)
                assert n%d == 0, (n, d, n%d)
            for d in divisors_cond(n, lambda d: d%3 == 0):
                assert d > 0, (n, d)
                assert n%d == 0 and d%3 == 0, (n, d, n%d)
            for d in divisors_cond(n, lambda d: d%3 == 1):
                assert d > 0, (n, d)
                assert n%d == 0 and d%3 == 1, (n, d, n%d)
            for d in divisors_cond(n, lambda d: d%3 == 2):
                assert d > 0, (n, d)
                assert n%d == 0 and d%3 == 2, (n, d, n%d)
            assert len(divisors_cond(n, lambda d: d%3 == 0)
                       + divisors_cond(n, lambda d: d%3 == 1)
                       + divisors_cond(n, lambda d: d%3 == 2)) == len(divisors(n)), \
                       (n, divisors_cond(n, lambda d: d%3 == 0),
                        divisors_cond(n, lambda d: d%3 == 1),
                        divisors_cond(n, lambda d: d%3 == 2),
                        divisors(n))
        print('ok'); sys.stdout.flush()


        print('factorial()...', end=''); sys.stdout.flush()
        assert factorial(0) == 1, factorial(0)
        f = 1
        for n in range(1, 1000):
            f *= n
            assert factorial(n) == f, (n, factorial(n), f)
            assert factorial(n) == math.factorial(n), (n, factorial(n), math.factorial(n))
        print('ok'); sys.stdout.flush()


        print('falling_factorial_pow()...', end=''); sys.stdout.flush()
        assert falling_factorial_pow(0, 0) == 1, falling_factorial_pow(0, 0)
        for n in range(2000):
            assert falling_factorial_pow(n, 0) == 1,         (n, falling_factorial_pow(n, 0))
            assert falling_factorial_pow(n, 1) == n,         (n, falling_factorial_pow(n, 1))
            assert falling_factorial_pow(n, 2) == n*(n - 1), (n, falling_factorial_pow(n, 2))
            assert falling_factorial_pow(n, 3) == n*(n - 1)*(n - 2), \
                   (n, falling_factorial_pow(n, 3))
            assert falling_factorial_pow(n, n + 1) == 0,     (n, falling_factorial_pow(n, n+1))
        for k in range(20):
            assert falling_factorial_pow(k, k) == math.factorial(k), \
                   (k, math.factorial(k), falling_factorial_pow(k, k))
        for k in range(20):
            assert falling_factorial_pow(k + 1, k) == math.factorial(k + 1), \
                   (k, math.factorial(k + 1), falling_factorial_pow(2, k))
        for k in range(1, 100):
            assert falling_factorial_pow(0, k) == 0, (k, falling_factorial_pow(0, k))
        for k in range(1, 20):
            for n in range(k, min(100, int(pow(bit32.MERSENNE32, 1/k)) + 3)):
                assert falling_factorial_pow(n, k) == math.factorial(n)//math.factorial(n - k), \
                       (n, k, math.factorial(n + k - 1)//math.factorial(n - 1),
                        falling_factorial_pow(n, k))
        print('ok'); sys.stdout.flush()


        print('fibonacci()...', end=''); sys.stdout.flush()
        assert fibonacci(0) == 0, fibonacci(0)
        assert fibonacci(1) == 1, fibonacci(1)
        assert fibonacci(2) == 1, fibonacci(2)
        assert fibonacci(3) == 2, fibonacci(3)
        Fk_1 = 1
        Fk  = 0
        for k in range(5000):
            assert fibonacci(k) == Fk, (k, fibonacci(k))
            Fk_1, Fk = Fk, Fk + Fk_1
        print('ok'); sys.stdout.flush()


        print('fibonacci2()...', end=''); sys.stdout.flush()
        assert fibonacci2(0) == (1, 0), fibonacci2(0)
        assert fibonacci2(1) == (0, 1), fibonacci2(1)
        assert fibonacci2(2) == (1, 1), fibonacci2(2)
        assert fibonacci2(3) == (1, 2), fibonacci2(3)
        Fk_1 = 1
        Fk  = 0
        for k in range(5000):
            assert fibonacci2(k) == (Fk_1, Fk), (k, fibonacci2(k))
            Fk_1, Fk = Fk, Fk + Fk_1
        print('ok'); sys.stdout.flush()


        print('fibonacci_is()...', end=''); sys.stdout.flush()
        assert fibonacci_is(0)
        assert fibonacci_is(1)
        assert fibonacci_is(2)
        assert fibonacci_is(3)
        assert not fibonacci_is(4)
        for k in range(0, 1000):
            assert fibonacci_is(fibonacci(k)), (k, fibonacci(k))
        for n in range(32768):
            if fibonacci_is(n):
                assert 0 <= fibonacci_to_index(n) <= 47, (n, fibonacci_to_index(n))
            else:
                assert fibonacci_to_index(n) == None, (n, fibonacci_to_index(n))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**45, 1000000000):
                if fibonacci_is(n):
                    assert 0 <= fibonacci_to_index(n) <= 47, (n, fibonacci_to_index(n))
                else:
                    assert fibonacci_to_index(n) == None, (n, fibonacci_to_index(n))
            for n in range(2**32 - 32768, 2**32 + 32768):
                if fibonacci_is(n):
                    assert 0 <= fibonacci_to_index(n) <= 47, (n, fibonacci_to_index(n))
                else:
                    assert fibonacci_to_index(n) == None, (n, fibonacci_to_index(n))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('fibonacci_to_index()...', end=''); sys.stdout.flush()
        assert fibonacci_to_index(0) == 0,    fibonacci_to_index(0)
        assert fibonacci_to_index(1) == 1,    fibonacci_to_index(1)
        assert fibonacci_to_index(2) == 3,    fibonacci_to_index(2)
        assert fibonacci_to_index(3) == 4,    fibonacci_to_index(3)
        assert fibonacci_to_index(4) == None, fibonacci_to_index(4)
        for k in range(3, 1000):
            assert fibonacci_to_index(fibonacci(k)) == k, \
                   (k, fibonacci_to_index(fibonacci(k)))
        for n in range(32768):
            k = fibonacci_to_index(n)
            if k != None:
                assert fibonacci(k) == n, (n, k, fibonacci(k))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**45, 1000000000):
                k = fibonacci_to_index(n)
                if k != None:
                    assert fibonacci(k) == n, (n, k, fibonacci(k))
            for n in range(2**32 - 32768, 2**32 + 32768):
                k = fibonacci_to_index(n)
                if k != None:
                    assert fibonacci(k) == n, (n, k, fibonacci(k))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('gcd()...', end=''); sys.stdout.flush()
        for m in range(100):
            assert gcd(m, 0) == m, (m, gcd(m, 0))
            assert gcd(m, 1) == 1, (m, gcd(m, 1))
            assert gcd(0, m) == m, (m, gcd(0, m))
            assert gcd(1, m) == 1, (m, gcd(1, m))
            assert gcd(m, m) == m, (m, gcd(m, m))
            for p in nat32.PRIME_16_ARRAY[:100]:
                if m%p == 0:
                    assert gcd(m, p) == p, (m, p, gcd(m, p))
                else:
                    assert gcd(m, p) == 1, (m, p, gcd(m, p))
        for m in range(100):
            for n in range(50):
                assert gcd(m, n) == fractions.gcd(m, n), (m, n, gcd(m, n), fractions.gcd(m, n))
                assert gcd(m, n) == gcd(n, m), (m, n, gcd(m, n), gcd(n, m))
        assert gcd(2**34, 3) == 1,     gcd(2**34, 3)
        assert gcd(2**34 + 1, 3) == 1, gcd(2**34 + 1, 3)
        assert gcd(2**34 + 2, 3) == 3, gcd(2**34 + 2, 3)
        print('ok'); sys.stdout.flush()


        print('lcm()...', end=''); sys.stdout.flush()
        for m in range(100):
            assert lcm(m, 0) == 0, (m, lcm(m, 0))
            assert lcm(m, 1) == m, (m, lcm(m, 1))
            assert lcm(0, m) == 0, (m, lcm(0, m))
            assert lcm(1, m) == m, (m, lcm(1, m))
            assert lcm(m, m) == m, (m, lcm(m, m))
            for p in nat32.PRIME_16_ARRAY[:100]:
                if m%p == 0:
                    assert lcm(m, p) == m, (m, p, lcm(m, p))
                else:
                    assert lcm(m, p) == m * p, (m, p, lcm(m, p))
        for m in range(100):
            for n in range(50):
                assert lcm(m, n) == lcm(n, m), (m, n, lcm(m, n), lcm(n, m))
                assert lcm(m, n)*fractions.gcd(m, n) == m*n, (m, n, lcm(m, n),
                                                              fractions.gcd(n, m),
                                                              lcm(m, n)*fractions.gcd(n, m),
                                                              m*n)
        assert lcm(2**34, 3) == 2**34 * 3,           (lcm(2**34, 3), 2**34 * 3)
        assert lcm(2**34 + 1, 3) == (2**34 + 1) * 3, (lcm(2**34 + 1, 3), (2**34 + 1) * 3)
        assert lcm(2**34 + 2, 3) == 2**34 + 2,       (lcm(2**34 + 2, 3), 2**34 + 2)
        print('ok'); sys.stdout.flush()


        print('lg()...', end=''); sys.stdout.flush()
        for n in range(1, 4096):
            assert lg(n) == len(bin(n)) - 1, (n, lg(n), len(bin(n)))
        for n in range(1, 2**32, 10000000):
            assert lg(n) == len(bin(n)) - 1, (n, lg(n), len(bin(n)))
        for n in range(2**32 - 4096, 2**32 + 10000):
            assert lg(n) == len(bin(n)) - 1, (n, lg(n), len(bin(n)))
        print('ok'); sys.stdout.flush()


        print('lucas()...', end=''); sys.stdout.flush()
        Lk_1 = -1
        Lk  = 2
        for k in range(5000):
            assert lucas(k) == Lk, (k, lucas(k))
            Lk_1, Lk = Lk, Lk + Lk_1
        print('ok'); sys.stdout.flush()


        print('lucas2()...', end=''); sys.stdout.flush()
        assert lucas2(0) == (-1, 2), lucas2(0)
        assert lucas2(1) == (2, 1),  lucas2(1)
        assert lucas2(2) == (1, 3),  lucas2(2)
        assert lucas2(3) == (3, 4),  lucas2(3)
        Lk_1 = -1
        Lk  = 2
        for k in range(5000):
            assert lucas2(k) == (Lk_1, Lk), (k, lucas2(k))
            Lk_1, Lk = Lk, Lk + Lk_1
        print('ok'); sys.stdout.flush()


        print('lucas_is()...', end=''); sys.stdout.flush()
        assert not lucas_is(0)
        assert lucas_is(1)
        assert lucas_is(2)
        assert lucas_is(3)
        assert lucas_is(4)
        assert not lucas_is(5)
        for k in range(0, 1000):
            assert lucas_is(lucas(k)), (k, lucas(k))
        for n in range(32768):
            if lucas_is(n):
                assert 0 <= lucas_to_index(n) <= 46, (n, lucas_to_index(n))
            else:
                assert lucas_to_index(n) == None, (n, lucas_to_index(n))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**45, 1000000000):
                if lucas_is(n):
                    assert 0 <= lucas_to_index(n) <= 46, (n, lucas_to_index(n))
                else:
                    assert lucas_to_index(n) == None, (n, lucas_to_index(n))
            for n in range(2**32 - 32768, 2**32 + 32768):
                if lucas_is(n):
                    assert 0 <= lucas_to_index(n) <= 46, (n, lucas_to_index(n))
                else:
                    assert lucas_to_index(n) == None, (n, lucas_to_index(n))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('lucas_to_index()...', end=''); sys.stdout.flush()
        assert lucas_to_index(0) == None, lucas_to_index(0)
        assert lucas_to_index(1) == 1,    lucas_to_index(1)
        assert lucas_to_index(2) == 0,    lucas_to_index(2)
        assert lucas_to_index(3) == 2,    lucas_to_index(3)
        assert lucas_to_index(4) == 3,    lucas_to_index(4)
        assert lucas_to_index(5) == None, lucas_to_index(5)
        for k in range(3, 1000):
            assert lucas_to_index(lucas(k)) == k, (k, lucas_to_index(lucas(k)))
        for n in range(32768):
            k = lucas_to_index(n)
            if k != None:
                assert lucas(k) == n, (n, k, lucas(k))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**45, 1000000000):
                k = lucas_to_index(n)
                if k != None:
                    assert lucas(k) == n, (n, k, lucas(k))
            for n in range(2**32 - 32768, 2**32 + 32768):
                k = lucas_to_index(n)
                if k != None:
                    assert lucas(k) == n, (n, k, lucas(k))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('mersenne()...', end=''); sys.stdout.flush()
        for k in range(50):
            assert mersenne(k) + 1 == 2**k, (k, mersenne(k))
        print('ok'); sys.stdout.flush()


        print('mersenne_to_index()...', end=''); sys.stdout.flush()
        assert mersenne_to_index(0) == 0,    mersenne_to_index(0)
        assert mersenne_to_index(1) == 1,    mersenne_to_index(1)
        assert mersenne_to_index(2) == None, mersenne_to_index(2)
        assert mersenne_to_index(3) == 2,    mersenne_to_index(3)
        assert mersenne_to_index(4) == None, mersenne_to_index(4)
        for k in range(3, 1000):
            assert mersenne_to_index(mersenne(k)) == k, \
                   (k, mersenne_to_index(mersenne(k)))
        for n in range(32768):
            k = mersenne_to_index(n)
            if k != None:
                assert mersenne(k) == n, (n, k, mersenne(k))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**45, 1000000000):
                k = mersenne_to_index(n)
                if k != None:
                    assert mersenne(k) == n, (n, k, mersenne(k))
            for n in range(2**32 - 32768, 2**32 + 32768):
                k = mersenne_to_index(n)
                if k != None:
                    assert mersenne(k) == n, (n, k, mersenne(k))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('mertens()...', end=''); sys.stdout.flush()
        assert mertens(0) == 0,  mertens(0)
        assert mertens(1) == 1,  mertens(1)
        assert mertens(2) == 0,  mertens(2)
        assert mertens(3) == -1, mertens(3)
        assert mertens(4) == -1, mertens(4)
        assert mertens(5) == -2, mertens(5)
        for n in range(100):
            assert mertens(n + 1) == mertens(n) + factors.mobius(factors.primaries(n + 1)), \
                   (n, mertens(n + 1), mertens(n), factors.mobius(factors.primaries(n + 1)))
        print('ok'); sys.stdout.flush()


        print('nbbits0()...', end=''); sys.stdout.flush()
        assert nbbits0(0) == 0
        for n in range(1, 4096):
            nb = 0
            for i in range(rscan1(n)):
                if not bit(n, i):
                    nb += 1
            assert nbbits0(n) == nb, (n, nb, nbbits0(n), bin(n))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**34, 10000000):
                nb = 0
                for i in range(rscan1(n)):
                    if not bit(n, i):
                        nb += 1
                assert nbbits0(n) == nb, (n, nb, nbbits0(n), bin(n))
            for n in range(2**32 - 4096, 2**32 + 4096):
                nb = 0
                for i in range(rscan1(n)):
                    if not bit(n, i):
                        nb += 1
                assert nbbits0(n) == nb, (n, nb, nbbits0(n), bin(n))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('nbbits1()...', end=''); sys.stdout.flush()
        assert nbbits1(0) == 0
        for n in range(4096):
            nb = 0
            for i in range(40):
                if bit(n, i):
                    nb += 1
            assert nbbits1(n) == nb, (n, nb, nbbits1(n), bin(n))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**34, 10000000):
                nb = 0
                for i in range(40):
                    if bit(n, i):
                        nb += 1
                assert nbbits1(n) == nb, (n, nb, nbbits1(n), bin(n))
            for n in range(2**32 - 4096, 2**32 + 4096):
                nb = 0
                for i in range(40):
                    if bit(n, i):
                        nb += 1
                assert nbbits1(n) == nb, (n, nb, nbbits1(n), bin(n))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('nbbits()...', end=''); sys.stdout.flush()
        assert nbbits(0) == 0
        assert nbbits(1) == 1
        assert nbbits(2) == 2
        assert nbbits(3) == 2
        assert nbbits(4) == 3
        for n in range(1, 16384):
            l = nbbits(n)
            assert (1<<(l - 1)) <= n, (n, l)
            assert n < (1<<l),        (n, l)
            assert nbbits(n) == len(bin(n)), (n, nbbits(n), bin(n))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**40, 1000000000):
                l = nbbits(n)
                assert (1<<(l - 1)) <= n, (n, l)
                assert n < (1<<l),        (n, l)
                assert nbbits(n) == len(bin(n)), (n, nbbits(n), bin(n))
            for n in range(2**32 - 16384, 2**32 + 32768):
                l = nbbits(n)
                assert (1<<(l - 1)) <= n, (n, l)
                assert n < (1<<l),        (n, l)
                assert nbbits(n) == len(bin(n)), (n, nbbits(n), bin(n))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('nfp()...', end=''); sys.stdout.flush()
        for m in range(100):
            assert nfp(m, 0) == 0, (m, nfp(m, 0))
            assert nfp(m, 1) == m, (m, nfp(m, 1))
            assert nfp(0, m) == 0, (m, nfp(0, m))
            assert nfp(1, m) == m, (m, nfp(1, m))
            if m > 0:
                assert nfp(m, m) == 1, (m, nfp(m, m))
            for p in nat32.PRIME_16_ARRAY[:100]:
                if m%p == 0:
                    assert nfp(m, p) == m // p, (m, p, nfp(m, p))
                else:
                    assert nfp(m, p) == m * p, (m, p, nfp(m, p))
        for m in range(100):
            for n in range(50):
                assert nfp(m, n) == nfp(n, m), (m, n, nfp(m, n), nfp(n, m))
                assert nfp(m, n)*(fractions.gcd(m, n)**2) == m*n, (m, n, nfp(m, n),
                                                                   fractions.gcd(n, m)**2,
                                                                   nfp(m, n)*(fractions.gcd(n,
                                                                                            m)**2),
                                                                   m*n)
        assert nfp(2**34, 3) == 2**34 * 3,           (nfp(2**34, 3), 2**34 * 3)
        assert nfp(2**34 + 1, 3) == (2**34 + 1) * 3, (nfp(2**34 + 1, 3), (2**34 + 1) * 3)
        assert nfp(2**34 + 2, 3) == (2**34 + 2) // 3, (nfp(2**34 + 2, 3), (2**34 + 2) // 3)
        print('ok'); sys.stdout.flush()


        print('nontotatives()...', end=''); sys.stdout.flush()
        assert nontotatives(0) == [],           nontotatives(0)
        assert nontotatives(1) == [],           nontotatives(1)
        assert nontotatives(2) == [2],          nontotatives(2)
        assert nontotatives(3) == [3],          nontotatives(3)
        assert nontotatives(4) == [2, 4],       nontotatives(4)
        assert nontotatives(5) == [5],          nontotatives(5)
        assert nontotatives(6) == [2, 3, 4, 6], nontotatives(6)
        assert nontotatives(24) == [2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24], \
               nontotatives(24)
        for n in range(500 if debug.assertspeed >= debug.ASSERT_NORMAL
                       else 50):
            for d in nontotatives(n):
                assert d <= n, (n, d)
                assert not coprime_is(n, d), (n, d)
        for p in nat32.PRIME_16_ARRAY[:100]:
            assert nontotatives(p) == [p], (p, nontotatives(p))
        if debug.assertspeed < debug.ASSERT_NORMAL:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('nontotient()...', end=''); sys.stdout.flush()
        assert nontotient(0) == 0,   nontotient(0)
        assert nontotient(1) == 0,   nontotient(1)
        assert nontotient(2) == 1,   nontotient(2)
        assert nontotient(3) == 1,   nontotient(3)
        assert nontotient(4) == 2,   nontotient(4)
        assert nontotient(5) == 1,   nontotient(5)
        assert nontotient(6) == 4,   nontotient(6)
        assert nontotient(24) == 16, nontotient(24)
        for n in range(500 if debug.assertspeed >= debug.ASSERT_NORMAL
                       else 50):
            assert nontotient(n) == len(nontotatives(n)), \
                   (n, nontotient(n), len(nontotatives(n)), nontotatives(n))
        for p in nat32.PRIME_16_ARRAY[:100]:
            assert nontotient(p) == 1, (p, nontotient(p))
        if debug.assertspeed < debug.ASSERT_NORMAL:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('polygonal()...', end=''); sys.stdout.flush()
        for n in range(1000):
            assert polygonal(2, n) == n,              (n, polygonal(2, n))
            assert polygonal(3, n) == n*(n + 1)//2,   (n, polygonal(3, n), n*(n + 1)//2)
            assert polygonal(4, n) == n**2,           (n, polygonal(4, n), n**2)
            assert polygonal(5, n) == n*(3*n - 1)//2, (n, polygonal(5, n), n*(3*n - 1)//2)
        for k in range(2, 1000):
            assert polygonal(k, 0) == 0,         (k, polygonal(k, 0))
            assert polygonal(k, 1) == 1,         (k, polygonal(k, 1))
            assert polygonal(k, 2) == k,         (k, polygonal(k, 2))
            assert polygonal(k, 3) == 3*(k - 1), (k, polygonal(k, 3), 3*(k - 1))
        print('ok'); sys.stdout.flush()


        print('pow2()...', end=''); sys.stdout.flush()
        for k in range(1000):
            assert pow2(k) == 2**k, (k, pow2(k))
        print('ok'); sys.stdout.flush()


        print('pow3()...', end=''); sys.stdout.flush()
        for k in range(1000):
            assert pow3(k) == 3**k, (k, pow3(k))
        print('ok'); sys.stdout.flush()


        print('prime_is()...', end=''); sys.stdout.flush()
        assert not prime_is(0)
        assert not prime_is(1)
        assert prime_is(2)
        assert prime_is(3)
        assert not prime_is(4)
        assert prime_is(5)
        assert prime_is(2**32 - 5)
        for n in range(2**32 - 4, 2**32 + 15):
            assert not prime_is(n), n
        print('ok'); sys.stdout.flush()


        print('pyramidal()...', end=''); sys.stdout.flush()
        for n in range(1000):
            assert pyramidal(2, n) == n*(n + 1)//2, (n, pyramidal(2, n), n*(n + 1)//2)
            assert pyramidal(3, n) == n*(n + 1)*(n + 2)//6, \
                   (n, pyramidal(3, n), n*(n + 1)*(n + 2)//6)
            assert pyramidal(4, n) == n*(n + 1)*(2*n + 1)//6, \
                   (n, pyramidal(4, n), n*(n + 1)*(2*n + 1)//6)
            assert pyramidal(5, n) == n**2 * (n + 1)//2, (n, pyramidal(5, n), n**2 * (n + 1)//2)
        for k in range(2, 1000):
            assert pyramidal(k, 0) == 0,       (k, pyramidal(k, 0))
            assert pyramidal(k, 1) == 1,       (k, pyramidal(k, 1))
            assert pyramidal(k, 2) == k + 1,   (k, pyramidal(k, 2), k + 1)
            assert pyramidal(k, 3) == 4*k - 2, (k, pyramidal(k, 3), 4*k - 2)
        print('ok'); sys.stdout.flush()


        print('rising_factorial_pow()...', end=''); sys.stdout.flush()
        assert rising_factorial_pow(0, 0) == 1, rising_factorial_pow(0, 0)
        for n in range(2000):
            assert rising_factorial_pow(n, 0) == 1,                 (n, rising_factorial_pow(n, 0))
            assert rising_factorial_pow(n, 1) == n,                 (n, rising_factorial_pow(n, 1))
            assert rising_factorial_pow(n, 2) == n*(n + 1),         (n, rising_factorial_pow(n, 2))
            assert rising_factorial_pow(n, 3) == n*(n + 1)*(n + 2), (n, rising_factorial_pow(n, 3))
        for k in range(20):
            assert rising_factorial_pow(1, k) == math.factorial(k), \
                   (k, math.factorial(k), rising_factorial_pow(1, k))
        for k in range(20):
            assert rising_factorial_pow(2, k) == math.factorial(k + 1), \
                   (k, math.factorial(k+1), rising_factorial_pow(2, k))
        for k in range(1, 20):
            assert rising_factorial_pow(0, k) == 0, (k, rising_factorial_pow(0, k))
            for n in range(1, min(100, int(pow(bit32.MERSENNE32, 1/k) - k + 4))):
                assert rising_factorial_pow(n, k) \
                       == math.factorial(n + k - 1)//math.factorial(n - 1), \
                       (n, math.factorial(n + k - 1)//math.factorial(n - 1),
                        rising_factorial_pow(n, k))
        print('ok'); sys.stdout.flush()


        print('rscan1()...', end=''); sys.stdout.flush()
        assert rscan1(0)                == None
        assert rscan1(1)                == 0
        assert rscan1(2)                == 1
        assert rscan1(3)                == 1
        assert rscan1(4)                == 2
        assert rscan1(5)                == 2
        assert rscan1(bit32.MERSENNE32) == 31
        for n in range(1, 4096):
            assert rscan1(n) == len(bin(n)) - 1, (n, rscan1(n), len(bin(n)))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**34, 10000000):
                assert rscan1(n) == len(bin(n)) - 1, (n, rscan1(n), len(bin(n)))
            for n in range(2**32 - 4096, 2**32 + 4096):
                assert rscan1(n) == len(bin(n)) - 1, (n, rscan1(n), len(bin(n)))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('scan0()...', end=''); sys.stdout.flush()
        for i in range(33):
            assert scan0(2**i - 1) == i, (i, scan0(2**i - 1))
            assert scan0(2**32 - 1) == 32, scan0(2**32 - 1)
        for n in range(32768):
            if n&1 == 0:
                assert scan0(n) == 0, (n, scan0(n))
            else:
                assert scan0(n) == scan0(n>>1) + 1, (n, scan0(n), scan0(n>>1))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**45, 1000000000):
                if n&1 == 0:
                    assert scan0(n) == 0, (n, scan0(n))
                else:
                    assert scan0(n) == scan0(n>>1) + 1, (n, scan0(n), scan0(n>>1))
            for n in range(2**32 - 32768, 2**32 + 32768):
                if n&1 == 0:
                    assert scan0(n) == 0, (n, scan0(n))
                else:
                    assert scan0(n) == scan0(n>>1) + 1, (n, scan0(n), scan0(n>>1))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('scan1()...', end=''); sys.stdout.flush()
        assert scan1(0) == None, scan1(0)
        for i in range(32):
            assert scan1(2**i) == i, (i, scan1(2**i))
        for n in range(1, 32768):
            if n&1 == 1:
                assert scan1(n) == 0, (n, scan1(n))
            else:
                assert scan1(n) == scan1(n>>1) + 1, (n, scan1(n), scan1(n>>1))
        if debug.assertspeed >= debug.ASSERT_NORMAL:
            for n in range(1, 2**45, 1000000000):
                if n&1 == 1:
                    assert scan1(n) == 0, (n, scan1(n))
                else:
                    assert scan1(n) == scan1(n>>1) + 1, (n, scan1(n), scan1(n>>1))
            for n in range(2**32 - 32768, 2**32 + 32768):
                if n&1 == 1:
                    assert scan1(n) == 0, (n, scan1(n))
                else:
                    assert scan1(n) == scan1(n>>1) + 1, (n, scan1(n), scan1(n>>1))
        else:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('totatives()...', end=''); sys.stdout.flush()
        assert totatives(0) == [],                             totatives(0)
        assert totatives(1) == [1],                            totatives(1)
        assert totatives(2) == [1],                            totatives(2)
        assert totatives(3) == [1, 2],                         totatives(3)
        assert totatives(4) == [1, 3],                         totatives(4)
        assert totatives(5) == [1, 2, 3, 4],                   totatives(5)
        assert totatives(6) == [1, 5],                         totatives(6)
        assert totatives(24) == [1, 5, 7, 11, 13, 17, 19, 23], totatives(24)
        for n in range(500 if debug.assertspeed >= debug.ASSERT_NORMAL
                       else 50):
            t = totatives(n)
            for d in t:
                assert d <= n, (n, d)
                assert coprime_is(n, d), (n, d)
            tnt = t + nontotatives(n)
            tnt.sort()
            assert tnt == [x for x in range(1, n + 1)], \
                   (n, t, tnt, [x for x in range(1, n + 1)])
        for p in nat32.PRIME_16_ARRAY[:100]:
            assert totatives(p) == [x for x in range(1, p)], (p, totatives(p))
        if debug.assertspeed < debug.ASSERT_NORMAL:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('totient()...', end=''); sys.stdout.flush()
        assert totient(0) == 1, totient(0)
        assert totient(1) == 1, totient(1)
        assert totient(2) == 1, totient(2)
        assert totient(3) == 2, totient(3)
        assert totient(4) == 2, totient(4)
        assert totient(5) == 4, totient(5)
        assert totient(6) == 2, totient(6)
        assert totient(24) == 8, totient(24)
        for n in range(1, 500 if debug.assertspeed >= debug.ASSERT_NORMAL
                          else 50):
            assert totient(n) == len(totatives(n)), (n, totient(n), len(totatives(n)), totatives(n))
            assert totient(n) + nontotient(n) == n, (n, totient(n), nontotient(n))
        for p in nat32.PRIME_16_ARRAY[:100]:
            for k in range(1, 10):
                assert totient(p**k) == (p - 1) * p**(k - 1), (p, k, totient(p**k))
        if debug.assertspeed < debug.ASSERT_NORMAL:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('unitarydivisors()...', end=''); sys.stdout.flush()
        assert unitarydivisors(1) == [1],            unitarydivisors(1)
        assert unitarydivisors(2) == [1, 2],         unitarydivisors(2)
        assert unitarydivisors(3) == [1, 3],         unitarydivisors(3)
        assert unitarydivisors(4) == [1, 4],         unitarydivisors(4)
        assert unitarydivisors(5) == [1, 5],         unitarydivisors(5)
        assert unitarydivisors(6) == [1, 2, 3, 6],   unitarydivisors(6)
        assert unitarydivisors(12) == [1, 3, 4, 12], unitarydivisors(12)
        for n in range(1, 1000):
            divs = unitarydivisors(n)
            for d in divs:
                assert d > 0, (n, d)
                assert n%d == 0, (n, d, n%d)
                assert nat32.coprime_is(n//d, d), (n, d, n//d)
            assert divs == \
                   divisors_cond(n, lambda d: nat32.coprime_is(n//d, d)), \
                   (n, divs,
                    divisors_cond(n, lambda d: nat32.coprime_is(n//d, d)))
        print('ok'); sys.stdout.flush()
        debug.test_end()

    main_test()
##\endcond MAINTEST