Solution to Project Euler Problem 49: Prime permutations - 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?

• Java Code

package sikademy;
/**
 *
 * @author Archangel Macsika
 * Copyright (c) Sikademy. All rights reserved
 */

import java.util.Arrays;

public class SikademyEulerSolution {
	
	private static final int LIMIT = 10000;
	
	public String run() {
		boolean[] isPrime = listPrimality(LIMIT - 1);
		for (int base = 1000; base < LIMIT; base++) {
			if (isPrime[base]) {
				for (int step = 1; step < LIMIT; step++) {
					int a = base + step;
					int b = a    + step;
					if (       a < LIMIT && isPrime[a] && hasSameDigits(a, base)
					        && b < LIMIT && isPrime[b] && hasSameDigits(b, base)
					        && (base != 1487 || a != 4817))
						return "" + base + a + b;
				}
			}
		}
		throw new RuntimeException("Not found");
	}
	
	
	private static boolean hasSameDigits(int x, int y) {
		char[] xdigits = Integer.toString(x).toCharArray();
		char[] ydigits = Integer.toString(y).toCharArray();
		Arrays.sort(xdigits);
		Arrays.sort(ydigits);
		return Arrays.equals(xdigits, ydigits);
	}

        public static boolean[] listPrimality(int n) {
		if (n < 0)
			throw new IllegalArgumentException("Negative array size");
		boolean[] result = new boolean[n + 1];
		if (n >= 2)
			result[2] = true;
		for (int i = 3; i <= n; i += 2)
			result[i] = true;
		// Sieve of Eratosthenes
		for (int i = 3, end = sqrt(n); i <= end; i += 2) {
			if (result[i]) {
				// Note: i * i does not overflow
				for (int j = i * i, inc = i * 2; j <= n; j += inc)
					result[j] = false;
			}
		}
		return result;
	}

        public static int sqrt(int x) {
		if (x < 0)
			throw new IllegalArgumentException("Square root of negative number");
		int y = 0;
		for (int i = 1 << 15; i != 0; i >>>= 1) {
			y |= i;
			if (y > 46340 || y * y > x)
				y ^= i;
		}
		return y;
	

	public static void main(String[] args) {
                SikademyEulerSolution solution = new SikademyEulerSolution();
		System.out.println(solution.run());
	}	
}

• Python Code

# 
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
# 

def compute():
	LIMIT = 10000
	isprime = list_primality(LIMIT - 1)
	for base in range(1000, LIMIT):
		if isprime[base]:
			for step in range(1, LIMIT):
				a = base + step
				b = a + step
				if     a < LIMIT and isprime[a] and has_same_digits(a, base) \
				   and b < LIMIT and isprime[b] and has_same_digits(b, base) \
				   and (base != 1487 or a != 4817):
					return str(base) + str(a) + str(b)
	raise RuntimeError("Not found")

def list_primality(n):
	# Sieve of Eratosthenes
	result = [True] * (n + 1)
	result[0] = result[1] = False
	for i in range(sqrt(n) + 1):
		if result[i]:
			for j in range(i * i, len(result), i):
				result[j] = False
	return result

def sqrt(x):
	assert x >= 0
	i = 1
	while i * i <= x:
		i *= 2
	y = 0
	while i > 0:
		if (y + i)**2 <= x:
			y += i
		i //= 2
	return y

def has_same_digits(x, y):
	return sorted(str(x)) == sorted(str(y))


if __name__ == "__main__":
	print(compute())