Monthly Archives: June 2010

Euler Problem 50

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

This took a while to solve partly because I went on vacation and partly because I was being a stubborn bonehead.

I initially tried to solve for all possible starting positions. It worked but I soon discovered it would take days to solve. Wanting to avoid using brute force, I instead went about being a smart ass and used a complicated sifter technique. Needless to say it didn’t work very well.

So, I went back to my original algorithm (which works — see below) dropped the starting position to the first 10 rather than the first 500K. Voila: solved in 12 seconds.

import java.util.*;

public class Euler50
{
    public static void main(String[] args)
    {
        Euler50 e = new Euler50();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<Integer> P = new ArrayList<Integer>();
        P = makePrimes(1000000);
        int maxTerms = 0, maxSum = 0, sum = 0, count = 0;
        for (int p: P)
        {
            for (int i = 0; i < 10 ; i++)
            {
                count = 0;
                sum = 0;
                for (int n = i; P.get(n) < p/2; n++)
                {
                    sum += P.get(n);
                    count++;
                    if (sum > p)
                        break;
                    if (sum == p)
                    {
                        if (count > maxTerms)
                        {
                            maxTerms = count;
                            maxSum = sum;
                            System.out.format(“sum:%d, terms:%d\n”, sum, count);
                        }
                    }
                }
            }
        }
        return String.valueOf(maxSum);
    }
    public ArrayList<Integer> makePrimes (int lim)
    {
        ArrayList<Integer> P = new ArrayList<Integer>();
        boolean [] isPrime = new boolean [lim+1];
        for (int i = 2; i < lim; i++)
            isPrime[i] = true;
        for (int p = 2; p*p < lim; p++)
            if (isPrime[p] == true)
                for (int m = p*p; m < lim; m = m+p)
                    if (m % p == 0)
                        isPrime[m] = false;
        for (int i = 2; i < lim; i++)
            if (isPrime[i])
                P.add(i);
        return P;
    }
}

Euler Problem 49

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

Nothing extrordinary here. I could have made the code tighter, but it still ran in 7 seconds.

import java.util.*;

public class Euler49
{
    public static void main(String[] args)
    {
        Euler49 e = new Euler49();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<Integer> allP = new ArrayList<Integer>();
        ArrayList<Integer> P4 = new ArrayList<Integer>();
        allP = makePrimes (10000);
        String S = “”;
        for (int p: allP)
            if (p > 1487 && Integer.toString(p).length() == 4)
                P4.add(p);
        A:for (int i: P4)
        {
            for (int n = 1000; n < (9999-i)/2; n++)
            {
                if (P4.contains(i+n))
                    if (isPerm(i,i+n))
                        if (P4.contains(i+n+n))
                            if (isPerm(i, i+n+n))
                            {
                                S += Integer.toString(i) + Integer.toString(i+n) + Integer.toString(i+n+n);
                                break A;
                            }
            }
        }
        return String.valueOf(S);
    }
    public ArrayList<Integer> makePrimes (int lim)
    {
        ArrayList<Integer> P = new ArrayList<Integer>();
        boolean [] isPrime = new boolean [lim+1];
        for (int i = 2; i < lim; i++)
            isPrime[i] = true;
        for (int p = 2; p*p < lim; p++)
            if (isPrime[p] == true)
                for (int m = p*p; m < lim; m = m+p)
                    if (m % p == 0)
                        isPrime[m] = false;
        for (int i = 2; i < lim; i++)
            if (isPrime[i])
                P.add(i);
        return P;
    }
    public boolean isPerm (int i1, int i2)
    {
        String S1 = Integer.toString(i1);
        String S2 = Integer.toString(i2);
        for (int n = 0; n <= 3; n++)
            S2 = S2.replaceFirst(String.valueOf(S1.charAt(n)), “”);
        if (S2.equals(“”))
            return true;
        else
            return false;
    }
}

Euler Problem 48

The series, 1^(1) + 2^(2) + 3^(3) + … + 10^(10) = 10405071317.

Find the last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + … + 1000^(1000).

The BigInteger class makes this one a joke. I’m sure its gets harder going forward. So I won’t act too smug.

import java.math.*;

public class Euler48
{
    public static void main(String[] args)
    {
        Euler48 e = new Euler48();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        BigInteger big = BigInteger.valueOf(0);
        for (int i = 1; i <= 1000; i++)
            big = big.add(BigInteger.valueOf(i).pow(i));
        return String.valueOf(big.toString().substring(big.toString().length()-10));
    }
}

Euler Problem 47

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2&sup2; × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

I liked this one because it uses two very important routines developed so far. Prime Number generation and Number Factorization. The trick for this one is after factoring a number, filter the set for Prime numbers BEFORE counting the residual factors.

This routine is also getting more complex. In the interest of speeding up the calculation, I moved the Prime ArrayList definition outside of the method so that its a class variable now. This way its only defined once, rather than hundreds of thousands of times.

import java.util.*;

public class Euler47
{
    ArrayList<Integer> P = new ArrayList<Integer>();
    public static void main(String[] args)
    {
        Euler47 e = new Euler47();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<Integer> F = new ArrayList<Integer>();
        int start = 130000, limit = 140000;
        int answer = 0, flag = 0, count = 4;
        for (int i = start; i < limit; i++)
        {
            flag = 0;
            for (int n = 0; n <= count-1; n++)
            {
                F = makeOnlyPrime(Factor(i+n), i+n);
                if (F.size() == count)
                    flag++;
            }
            if (flag == count)
            {
                answer = i;
                break;
            }
        }
        return String.valueOf(answer);
    }
    public ArrayList<Integer> Factor (int num)
    {
        ArrayList<Integer> F = new ArrayList<Integer>();
        //F.add(1);
        for (int n = 2; n <= Math.ceil(Math.sqrt(num)); n++)
            if (num % n == 0 && F.contains(n) == false)
            {
                F.add(n);
                if (F.contains(num/n) == false)
                    F.add(num/n);
            }
        return F;
    }
    public ArrayList<Integer> Prime (int lim)
    {
        P.clear();
        boolean [] isPrime = new boolean [lim+1];
        for (int i = 2; i < lim; i++)
            isPrime[i] = true;
        for (int p = 2; p*p < lim; p++)
            if (isPrime[p] == true)
                for (int m = p*p; m < lim; m = m+p)
                    if (m % p == 0)
                        isPrime[m] = false;
        for (int i = 2; i < lim; i++)
            if (isPrime[i])
                P.add(i);
        return P;
    }
    public ArrayList<Integer> makeOnlyPrime (ArrayList<Integer> F, int i)
    {
        ArrayList<Integer> N = new ArrayList<Integer>();
        for (int f = 0; f <= F.size()-1; f++)
            if (Prime ((int)(i/2)+1).contains(F.get(f)))
                N.add(F.get(f));
        return N;
    }
}

Euler Problem 46

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^(2)
15 = 7 + 2×2^(2)
21 = 3 + 2×3^(2)
25 = 7 + 2×3^(2)
27 = 19 + 2×2^(2)
33 = 31 + 2×1^(2)

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Not too tricky. Need to notice that the prime number and the number squared are always less than the composite.

import java.util.*;

public class Euler46
{
    public static void main(String[] args)
    {
        Euler46 e = new Euler46();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<Integer> C = new ArrayList<Integer>();
        ArrayList<Integer> P = new ArrayList<Integer>();
        ArrayList<Integer> T = new ArrayList<Integer>();
        int n = 10000;
        boolean [] isPrime = new boolean [n+1];
        for (int i = 2; i < n; i++)
            isPrime[i] = true;
        for (int p = 2; p*p < n; p++)
            if (isPrime[p] == true)
                for (int m = p*p; m < n; m = m+p)
                    if (m % p == 0)
                        isPrime[m] = false;
        for (int i = 2; i < n; i++)
            if (isPrime[i])
                P.add(i);
            else
                if (i % 2 != 0)
                    C.add(i);
        boolean flag = true;
        for (int i = 0; i <= C.size()-1; i++)
        {
            flag = true;
            A: for (int p = 0; P.get(p) < C.get(i); p++)
                for (int m = 1; m < Math.sqrt(C.get(i)); m++)
                    if ((P.get(p) + 2*m*m) == C.get(i))
                    {
                        flag = false;
                        System.out.format(“%d: %d + 2*%d^2\n”, C.get(i), P.get(p), m);
                        break A;
                    }
            if (flag)
                T.add(C.get(i));
        }
        return String.valueOf(T.get(0));
    }
}

According to Wiki, every integer greater than one is either a prime number or a composite number.



Euler Problem 45

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle   T_(n)=n(n+1)/2   1, 3, 6, 10, 15, …
Pentagonal   P_(n)=n(3n−1)/2   1, 5, 12, 22, 35, …
Hexagonal   H_(n)=n(2n−1)   1, 6, 15, 28, 45, …

It can be verified that T_(285) = P_(165) = H_(143) = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

Flip each formula using the quadratic equation. Double check your calculations. Iterate over a few billion. Done.

public class Euler45
{
    public static void main(String[] args)
    {
        Euler45 e = new Euler45();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        long next = 0;
        for (long i = 1000000000L; i <= 2000000000L; i++)
            if ((Math.sqrt(1+8*i)-1) % 2 == 0)
                if ((Math.sqrt(1+24*i)+1) % 6 == 0)
                    if ((Math.sqrt(1+8*i)+1) % 4 == 0)
                    {
                        next = i;
                        break;
                    }
        return String.valueOf(next);
    }
}



Euler Problem 44

Pentagonal numbers are generated by the formula, P_(n)=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

It can be seen that P_(4) + P_(7) = 22 + 70 = 92 = P_(8). However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_(j) and P_(k), for which their sum and difference is pentagonal and D = |P_(k) − P_(j)| is minimised; what is the value of D?

It seems simple … and it is, providing you do two things.

  1. Use the standard quadratic equation on P_(n)=n(3n−1)/2 to flip it. This way you can go both ways when needed. Check out Pentagonal Numbers on Wiki.
  2. ALWAYS CHECK YOUR FORMULAS! I spent days and many wrong submissions because one of my formulas was wrong..
public class Euler44
{
    public static void main(String[] args)
    {
        Euler44 e = new Euler44();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        long max = Long.MAX_VALUE;
        for (long j = 1; j <= 10000; j++)
            for (long k = 1; k <= j; k++)
                if (isPent(P(j)+P(k)) && isPent(P(j)-P(k)))
                    if (P(j)-P(k) < max)
                        max = P(j)-P(k);
        return String.valueOf(max);
    }
    public boolean isPent (long n)
    {
        if ((Math.sqrt(1+24*n)+1) % 6 == 0)
            return true;
        return false;
    }
    public long P (long n)
    {
        return n*(3*n-1)/2;
    }
}