Thread: Project Euler: Truncatable Primes

So, this is going to be a hard one to follow.. I believe it requires me to post all of my code in order to get the idea.. So if you have the time (or if you love me that much), I would appreciate it if you took a look at this.. Here's the original Problem 37. I have looked over my code several times and can't seem to discover my error. Well, here we go:

import java.util.*;
public class prob37 {
	public static void main(String args[]){
		int sum = 0;
		ArrayList<String> list = new ArrayList<String>();
		for(int i = 1000000; i > 100; i--){
			for(int a = 0; a < list.size(); a++){
				if(list.get(a).contains("" + i)){
					i--;
				}
			}
			if(allPrimeLeft(i) && allPrimeRight(i)){
				System.out.println(i);
				list.add("" + i);
				sum+=i;
			}
		}
		System.out.println(sum);
	}
 
	public static boolean isPrime(int n){
		if(n%2==0)
			return false;
		for(int i = 3; i < Math.sqrt(n)+1; i+=2){
			if(n%i==0)
				return false;
		}
		return true;
	}
 
	public static boolean allPrimeLeft(int n){
		if(!isPrime(n))
			return false;
		String s = "" + n;
		for(int i = 0; i < s.length()-1;i++){
			s = s.substring(1, s.length());
			int temp = Integer.parseInt(s);
			if(!isPrime(temp))
				return false;
		}
		return true;
	}
	public static boolean allPrimeRight(int n){
		if(!isPrime(n))
			return false;
		while(n > 0){
			if(!isPrime(n))
				return false;
			n/=10;
		}
		return true;
	}
}

If you looked over this, and got to this point, YOURE AWESOME! Haha, but I'm going to keep looking it over as well... Please comment back if you have any question over my code or have a pointer for me to follow.

Output:
739397
73331
31193
19739
7331
3797
3137
1997
1373
719
317
179
173
131
113
882927 ---> This is the Sum I receive.

There are only supposed to be 11 numbers, but I return 15. Also the correct Sum is 748317. Maybe we can work this through the output.
Difference Between My Sum and The Actual Sum = 134610

How can numbers that begin or end in a non-prime (like 9) be truncatable primes?

I don't think your isPrime() method works correctly... It won't return 2 as prime. It also returns 1 or 0 as being prime (technically they are not). I'm also not so sure your two AllPrime methods are correct, but I don't understand the algorithm you're using or read them over all that carefully.

Originally Posted by KevinWorkman

How can numbers that begin or end in a non-prime (like 9) be truncatable primes?

Wow, you can tell I was late up last night My isPrime method is working fine except that it counts 1 as a prime (it doesn't count 0 or 9 as a prime). There's something wrong with my allPrimeLeft method.

I'm going to entirely restart that method.. Is there a way to remove the leftmost digit until you reach the rightmost digit? I know if you had 1234, you could do 1234%1000, then do 234%100, etc... But that doesn't seem like the best possible solution.

Using mod seems like a perfectly reasonable approach. Or you could turn it into a String and manipulate it that way. Whatever fits into your head the best.

So, after fixing all the kinks.. Corrected allPrimeLeft method and debugged to be sure... Took out ArrayList because it went against the prompt... Counted down to 10 instead of 100 when checking if the int i is a truncatable prime

So here's my new output!

739397
3797
3137
797
373
317
313
73
53
37
748294 ---> Sum

Difference between My Sum and Their Sum -> 23

However, now I have 11 numbers... And they are all truncatable left and right.. I even double checked.. So, I'm entirely stumped.

I'm only counting 10 numbers. And I bet I can guess what number is missing.

Originally Posted by KevinWorkman

I'm only counting 10 numbers. And I bet I can guess what number is missing.

Shhh don't tell me!