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;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s