##########################################################################
#  Copyright (C) 2006 Jaap Spies, jaapspies@gmail.com
#  Copyright (C) 2006 William Stein, wstein@gmail.com
#
#  Distributed under the terms of the GNU General Public License (GPL):
#
#                  http://www.gnu.org/licenses/
###############################################################

def A111787(n):
    r"""
    This function returns the $n$-th number of Sloane's sequence A111787


    $a(n)=0$ if $n$ is an odd prime or a power of 2. For numbers of the third
    kind we proceed as follows: suppose $n$ is to be written as sum of $k$
    consecutive integers starting with $m$, then $2n = k(2m + k - 1)$.
    Let $p$ be the smallest odd prime divisor of $n$ then
    $a(n) = min(p,2n/p)$.

    See: http://www.jaapspies.nl/mathfiles/problem2005-2C.pdf

    INPUT:
        n -- positive integer

    OUTPUT:
        function value

    EXAMPLES:
        sage: A111787(6)
        3

        sage: A111787(15)
        3

        sage: A111787(23)
        0

        sage: A111787(128)
        0

        AUTHOR:
            - Jaap Spies (2006-12-09)
    """
    if is_prime(n) or is_power_of_two(n):
        return 0
    else:
        for d in range(3,n,2):
            if n % d == 0:
                return min(d, 2*n/d)


def A111787_list(N):
    r"""
    This function returns a list of A111787


    INPUT:
        N -- positive integer

    OUTPUT:
        list of integers

    EXAMPLES:
        sage: A111787_list(20)
        [0, 0, 0, 0, 0, 3, 0, 0, 3, 4, 0, 3, 0, 4, 3, 0, 0, 3, 0, 5]
        

    AUTHOR:
        - Jaap Spies (2006-12-09)

    """
    return [A111787(i) for i in range(1,N+1)]

def is_power_of_two(n):
    r"""
    This function returns True iff $n$ is a power of 2

    INPUT:
        n -- integer

    OUTPUT:
        True -- if n is a power of 2
        False -- if not

    EXAMPLES:
        sage: is_power_of_two(1024)
        True

        sage: is_power_of_two(1)
        True

        sage: is_power_of_two(24)
        False

        sage: is_power_of_two(0)
        False

        sage: is_power_of_two(-4)
        False

    AUTHOR:
        - Jaap Spies (2006-12-09)

    """
    while n > 0 and n%2 == 0: 
        n = n >> 1
    return n == 1

# From the Programming Guide:

#def is2pow(n):
#    while n != 0 and n%2 == 0: 
#        n = n >> 1
#    return n == 1
#