import java.util.ArrayList;
import java.math.BigInteger;
public class LP1Morrison
{
    /** 
     * Da main
     */
    public static void main(String[] args)
    {
        String s = "abcdefg";
        System.out.printf("Case %s: %s\n", s, everyOther(s).equals("aceg"));
        BigInteger b = BigInteger.valueOf(5);
        System.out.printf("Casse %s: %s\n", b, !isAPowerOf2(b));
        b = BigInteger.valueOf(1048576);
        System.out.printf("Casse %s: %s\n", b, isAPowerOf2(b));
        ArrayList<Integer> foo = new ArrayList<Integer>();
        foo.add(5);
        foo.add(8);
        foo.add(7);
        foo.add(2);
        foo.add(9);
        System.out.printf("returned %s, expected [5,8,7.9]\n", largerThan(foo,5));
        for(int k = 0; k < 10; k++)
        {
            System.out.println(fibonacci(k));
        }
    }
    /** 
     * This function pulls out all characters of even index
     * and returns them bundled in a string
     * @param s the string you are sampling from
     * @return a string containing all characters, in order,
     * from s.
     */
    public static String everyOther(String s)
    {
        StringBuffer sb = new StringBuffer();
        for(int k = 0; k < s.length(); k+=2)
        {
            sb.append(s.charAt(k));
        }
        return sb.toString();
    }
    /** 
     * This functon tests if the BigInteger passed it is a power of 2.
     * @param b is a BigInteger
     * @return true if b is a power of 2 and false otherwise.
     */
    public static boolean isAPowerOf2(BigInteger b)
    {
        BigInteger start = BigInteger.ONE;
        while(start.compareTo(b) <=0 )
        {
            start = start.multiply(BigInteger.valueOf(2));
            if(start.equals(b))
                return true;
        }
        return false;
    }
    /*  
     * This function returns a new array list with
     * all elements from the array list a that are greater
     * than or equal to n.
     * @param a an array list of integers
     * @param n an integer
     * @return a new array list with all entries in a that are n or larger.
     */
    public static ArrayList<Integer> largerThan(ArrayList<Integer> a, int n)
    {
        ArrayList<Integer> out = new ArrayList<Integer>();
        for(int s: a)
        {
            if(s >= n)
            {
                out.add(s);
            }
        }
        return out;
    }
    /** 
     * This returns the nth Fibonacci number as a BigInteger
     * @param a positive integer
     * @return the nth Fibnacci number. 
     * fib(0) -> 0
     * fib(1) -> 1
     * fib(2) -> 1 etc
     */
    public static BigInteger fibonacci(int n)
    {
        BigInteger little = BigInteger.ZERO;
        BigInteger big = BigInteger.ONE;
        for(int k = 0; k < n; k++)
        {
            BigInteger tmp = big;
            big = big.add(little);
            little = tmp;
        }
        return little;
    }
    /** 
    * This returns the sum of alll of the gcd's of the elements in the list al
    * with the given BigInteger b.
    * @param al a list of BigIntegers
    * @b a BigInteger 
    * @return the sum of the GCDs of the elemnts in al with b.
    * Sample  a = [34, 21, 65]
    * b = 13
    * returns 5.
    */
    public static BigInteger sumGCD(BigInteger b, ArrayList<BigInteger> al)
    {
        BigInteger out = BigInteger.ZERO;
        for(BigInteger s: al)
        {
            out = out.add(b.gcd(s));
        }
        return out;
    }
}