Solution to Project Euler Problem 51: Prime digit replacements - By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime. By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property. Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

• Java Code

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

import java.util.Arrays;

public class SikademyEulerSolution {
	
	public String run() {
		boolean[] isPrime = listPrimality(1000000);
		for (int i = 0; i < isPrime.length; i++) {
			if (!isPrime[i])
				continue;
			
			int[] n = toDigits(i);
			for (int mask = 0; mask < (1 << n.length); mask++) {
				int[] digits = doMask(n, mask);
				int count = 0;
				for (int j = 0; j < 10; j++) {
					if (digits[0] != 0 && isPrime[toNumber(digits)])
						count++;
					digits = addMask(digits, mask);
				}
				
				if (count == 8) {
					digits = doMask(n, mask);
					for (int j = 0; j < 10; j++) {
						if (digits[0] != 0 && isPrime[toNumber(digits)])
							return Integer.toString(toNumber(digits));
						digits = addMask(digits, mask);
					}
				}
			}
		}
		throw new RuntimeException("Not found");
	}

       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[] listPrimes(int n) {
		boolean[] isPrime = listPrimality(n);
		int count = 0;
		for (boolean b : isPrime) {
			if (b)
				count++;
		}
		
		int[] result = new int[count];
		for (int i = 0, j = 0; i < isPrime.length; i++) {
			if (isPrime[i]) {
				result[j] = i;
				j++;
			}
		}
		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;
	}
	
	private static int[] toDigits(int n) {
		int[] buf = new int[10];
		int i = buf.length;
		do {
			i--;
			buf[i] = n % 10;
			n /= 10;
		} while (n != 0);
		return Arrays.copyOfRange(buf, i, buf.length);
	}
	
	
	private static int[] doMask(int[] digits, int mask) {
		int[] result = new int[digits.length];
		for (int i = 0; i < digits.length; i++)
			result[i] = digits[i] * (~mask >>> i & 1);
		return result;
	}
	
	
	private static int[] addMask(int[] digits, int mask) {
		int[] result = new int[digits.length];
		for (int i = 0; i < digits.length; i++)
			result[i] = digits[i] + (mask >>> i & 1);
		return result;
	}
	
	
	private static int toNumber(int[] digits) {
		int result = 0;
		for (int x : digits)
			result = result * 10 + x;
		return result;
	}

	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():
	isprime = list_primality(1000000)
	for i in range(len(isprime)):
		if not isprime[i]:
			continue

		n = [int(c) for c in str(i)]
		for mask in range(1 << len(n)):
			digits = do_mask(n, mask)
			count = 0
			for j in range(10):
				if digits[0] != 0 and isprime[to_number(digits)]:
					count += 1
				digits = add_mask(digits, mask)

			if count == 8:
				digits = do_mask(n, mask)
				for j in range(10):
					if digits[0] != 0 and isprime[to_number(digits)]:
						return str(to_number(digits))
					digits = add_mask(digits, mask)
	raise AssertionError("Not found")

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 list_primality(n):
	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 list_primes(n):
	return [i for (i, isprime) in enumerate(list_primality(n)) if isprime]

def do_mask(digits, mask):
	return [d * ((~mask >> i) & 1) for (i, d) in enumerate(digits)]


def add_mask(digits, mask):
	return [d + ((mask >> i) & 1) for (i, d) in enumerate(digits)]


def to_number(digits):
	result = 0
	for d in digits:
		result = result * 10 + d
	return result


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