[Problem Solving #1] Deletable Primes

[MikeD]

Ok. I solved it late last night and then was too tired to post it here.

It took me a while because I was getting 5 less deletable primes than the sample output and couldn't figure out why, but then I realized the test to exclude numbers like 10859 was excluding more stuff than it should.

I did it in python because I wanted to put it together fast and that's why it isn't the most organized code ever. Then I translated to C to make it faster.

I must say the python implementation of the sieve I used was found on StackOverflow (I liked the list comprehension better than all the nested for loops!).

 

 

Compile with -lm (math library for sqrt)

def sieve(n):  np1 = n + 1  s = list(range(np1))  s[1] = 0  sqrtn = int(round(n**0.5))  for i in range(2, sqrtn + 1):    if s[i]:      s[i*i: np1: i] = [0] * len(range(i*i, np1, i))  return filter(None, s)delprimes = set([2, 3, 5, 7])for prime in sieve(10000000):  if prime < 10:    continue  mult = 1  while mult < prime:    rest = prime % mult    testing = int(prime/(mult*10))*mult + rest    if testing < int(mult/10):      break    if testing in delprimes:      delprimes.add(prime)      break    mult *= 10print(len(delprimes))print(sum(delprimes))print() 

#include <stdio.h>#include <stdlib.h>#include <math.h>int* sieve(long n) {  int i, j;  long sqrtn = (long) sqrt(n);  int* s = malloc(sizeof(int) * n);  for(i = 2; i < n; i++)    s[i] = 1;  s[0] = s[1] = 0;  for(i = 2; i < sqrtn + 1; i++)    if(s[i])      for(j = i*i; j < n; j += i)        s[j] = 0;  return s;}int main() {  int *s;  long i, n = 10000001;  long mult, rest, testing;  long count = 0, sum = 0;  s = sieve(n);  for(i = 8; i < n; i++)    if(s[i]) {      mult = 1;      s[i] = 0;      while(mult < i) {        rest = i % mult;        testing = (long) (i/(mult*10))*mult + rest;        if(testing < (long) (mult/10))          break;        if(s[testing]) {          s[i] = 1;          break;        }        mult *= 10;      }    }  for(i = 0; i < n; i++)    if(s[i]){      count++;      sum += i;    }  free(s);  printf("%ld\n%ld\n", count, sum);  return 0;} 

[Maximation]

So I have a solution, it does not work though.

For some reason the string result = "" in the removeOneDigitAt method.

I do not really understand why this happens, could someone help out?

Here is the code :

public class Main {	private static final int NUMBER = 30;	private static boolean[] isPrime = new boolean[NUMBER];	private static int numOfDelPrimes = 0;	private static long sumofDelPrimes = 0;	public static void main(String[] args){		sieve();		int numOfPrimes = 0;		long sumOfPrimes = 0;		for(int i = 0; i < isPrime.length; i++){			if(isPrime[i]){				numOfPrimes++; 				sumOfPrimes += i;			}		}		sieveDeletablePrimes();		System.out.println(numOfDelPrimes);		System.out.println(sumofDelPrimes);	}	/*	*	calculates the prime numbers	*/	private static void sieve(){		isPrime[0] = isPrime[1] = false;		for(int i = 2; i < NUMBER; i++)			isPrime[i] = true;		for(int i = 2; i < NUMBER; i++){			if(isPrime[i])				for(int j = 2 * i; j < NUMBER; j += i)					isPrime[j] = false;		}	}	private static void sieveDeletablePrimes(){		for(int i = 2; i < NUMBER; i++){			if(isPrime[i]){				if(isDelPrime(i)){					numOfDelPrimes++;					sumofDelPrimes += i;				}			}		}	}	private static boolean isDelPrime(int i){		int digits = String.valueOf(i).length();		for(int j = 0; j < digits; j++){			int oneDigitLess = removeOneDigitAt(i, j);			int digitsLeft = String.valueOf(oneDigitLess).length();			if(isPrime[oneDigitLess] && digitsLeft > 1){				if(isDelPrime(oneDigitLess))					return true;			}			else if(isPrime[oneDigitLess] && digitsLeft == 1)				return true;			else if(!isPrime[oneDigitLess])				return false;		}		return false;	}	private static int removeOneDigitAt(int prime , int digit){		String n = String.valueOf(prime);		System.out.println(n);		String result;		if(digit == 0)			result = n.substring(digit + 1);		else {			result = n.substring(0, digit - 1);			if(n.length() > digit)				result = result.concat(n.substring(digit + 1));		}		return Integer.parseInt(result);	}}

[wolfsinner]

So I have a solution, it does not work though.

For some reason the string result = "" in the removeOneDigitAt method.

I do not really understand why this happens, could someone help out?

Here is the code :

 

You're actually removing 2 digits from the string when you're not removing bounding character indexes (substring(int1, int2) goes from int1 to int2-1. And you're doing int2-1-1, which is int2-2).

A correct version of that code is this (I added an exception capture for safety):

private static int removeOneDigitAt(int prime , int digit){   String n = String.valueOf(prime);   String result;   try {      result = n.substring(0, digit - 1);      if(n.length() > digit)         result = result.concat(n.substring(digit));   } catch(StringIndexOutOfBoundsException ex){      return prime;   }    return Integer.parseInt(result);}

A quick look at your deletable primes check tells me you're on the right track, but you've got to fix a few things. I don't have much time right now, but I'll come on later and help if you still need help.

[Maximation]

      result = n.substring(0, digit - 1);      if(n.length() > digit)         result = result.concat(n.substring(digit));

 

But now it does not remove the digit at the specified index, right? It concatenates the string from the digit that needed to be removed.

Either way, thank you for helping me out! Very interesting problem.

[Maximation]

A quick look at your deletable primes check tells me you're on the right track, but you've got to fix a few things. I don't have much time right now, but I'll come on later and help if you still need help.

 

I did not implement something to keep track of the zero after a digit yet.

Btw, when I try to execute it it gives me these errors :

Exception in thread "main" java.lang.StackOverflowError        at java.lang.Exception.<init>(Unknown Source)        at java.lang.RuntimeException.<init>(Unknown Source)        at java.lang.IndexOutOfBoundsException.<init>(Unknown Source)        at java.lang.StringIndexOutOfBoundsException.<init>(Unknown Source)        at java.lang.String.substring(Unknown Source)        at Main.removeOneDigitAt(Main.java:85)        at Main.isDelPrime(Main.java:64)        at Main.isDelPrime(Main.java:67)

[Nuluvius]

 

I did not implement something to keep track of the zero after a digit yet.

Btw, when I try to execute it it gives me these errors :

Exception in thread "main" java.lang.StackOverflowError        at java.lang.Exception.<init>(Unknown Source)        at java.lang.RuntimeException.<init>(Unknown Source)        at java.lang.IndexOutOfBoundsException.<init>(Unknown Source)        at java.lang.StringIndexOutOfBoundsException.<init>(Unknown Source)        at java.lang.String.substring(Unknown Source)        at Main.removeOneDigitAt(Main.java:85)        at Main.isDelPrime(Main.java:64)        at Main.isDelPrime(Main.java:67)

 

Stick a breakpoint in that function and watch it though, pay attention to that string indexer, it's going out of bounds at some point.

[Maximation]

You're actually removing 2 digits from the string when you're not removing bounding character indexes (substring(int1, int2) goes from int1 to int2-1. And you're doing int2-1-1, which is int2-2).

A correct version of that code is this (I added an exception capture for safety):

      result = n.substring(0, digit - 1);      

 

You said the "digit - 1" is incorrect, why did you still use it in your "correct" version?

[Nuluvius]

Originally I was planning to do this using C++ AMP but for simplicities sake I changed this to TPL in C# using TDD and a MVVM/WPF architecture (design overkill perhaps, though I don't think so). C# gives me the advantage of the high level of syntactic sugar offered by Linq and string conversion; thus I am able to side step a great deal of the heavy lifting. I will post my code later, one of the problems I have come across was my implementation of the Sieve of Atkin. I was getting a race condition due to using parallel for loops. It was not immediately obvious as it only occurred towards the highest bound.

 

As far as structure and simplicity go, I think it's sound, mathematically however I am on unstable ground.

[Maximation]

Stick a breakpoint in that function and watch it though, pay attention to that string indexer, it's going out of bounds at some point.

 

What do you mean, where should I put a break statement?

[Ciccioo]

You said the "digit - 1" is incorrect, why did you still use it in your "correct" version?

the second parameter of the substring method is the end index (exclusive)

so, the version that wolfinner suggested does remove a character, but it removes the (digit - 1)th

i think it should be

      result = n.substring(0, digit);      if(n.length() > digit)         result = result.concat(n.substring(digit + 1));

this way, you stop extracting the first substring at the digith position, and you extract the second substring from the character after the digith one

 

the index out of bound was due to the fact that, when digit = 0, the first substring cutted from the index 0 to -1, which is invalid (out of the lower bound, 0)

[Maximation]

the second parameter of the substring method is the end index (exclusive)

so, the version that wolfinner suggested does remove a character, but it removes the (digit - 1)th

i think it should be

      result = n.substring(0, digit);      if(n.length() > digit)         result = result.concat(n.substring(digit + 1));

this way, you stop extracting the first substring at the digith position, and you extract the second substring from the character after the digith one

 

the index out of bound was due to the fact that, when digit = 0, the first substring cutted from the index 0 to -1, which is invalid (out of the lower bound, 0)

 

Yes, that is what I thought it should be.

But now I still have a NumberFormatException :

 

Exception in thread "main" java.lang.NumberFormatException: For input string: ""        at java.lang.NumberFormatException.forInputString(Unknown Source)        at java.lang.Integer.parseInt(Unknown Source)        at java.lang.Integer.parseInt(Unknown Source)        at Main.removeOneDigitAt(Main.java:82)        at Main.isDelPrime(Main.java:54)        at Main.sieveDeletablePrimes(Main.java:41)        at Main.main(Main.java:12)

Why is there nothing in the string result?

[Ciccioo]

Yes, that is what I thought it should be.

But now I still have a NumberFormatException :

Why is there nothing in the string result?

i tried the function itself with this sample code and it worked, maybe the problem has to be found in the code that feeds the function

     System.out.println(removeOneDigitAt(1234, 0));     System.out.println(removeOneDigitAt(1234, 1));     System.out.println(removeOneDigitAt(1234, 2));     System.out.println(removeOneDigitAt(1234, 3));

[Maximation]

 

i tried the function itself with this sample code and it worked, maybe the problem has to be found in the code that feeds the function

     -snip-

Yes, you are right. Mh, weird. Then the bug should be in one of these functions :

 

EDIT: I am pretty sure the function sieveDeletablePrimes is correct and clean of bugs. The bug should be in the other function the..

private static void sieveDeletablePrimes(){		for(int i = 2; i < NUMBER; i++){			if(isPrime[i]){				if(isDelPrime(i)){					numOfDelPrimes++;					sumofDelPrimes += i;				}			}		}	}	private static boolean isDelPrime(int i){		int digits = String.valueOf(i).length();		for(int j = 0; j < digits; j++){			int oneDigitLess = removeOneDigitAt(i, j);			int digitsLeft = String.valueOf(oneDigitLess).length();			if(isPrime[oneDigitLess] && digitsLeft > 1){				if(isDelPrime(oneDigitLess))					return true; break;			}			else if(isPrime[oneDigitLess] && digitsLeft == 1)				return true;			else if(!isPrime[oneDigitLess])				return false;		}		return false;	}

[Nuluvius]

What do you mean, where should I put a break statement?

A breakpoint so that you may walk through in debug. Not a break statement. Step through your code at runtime and you'll discover the cause of all these exceptions you keep on posting up.

[Nuluvius]

@ Maximation, you might find these of interest:

 

http://www.vogella.com/tutorials/EclipseDebugging/article.html

http://help.eclipse.org/juno/index.jsp?topic=%2Forg.eclipse.jdt.doc.user%2Ftasks%2Ftasks-debug-launch.htm

http://help.eclipse.org/juno/index.jsp?topic=%2Forg.eclipse.jdt.doc.user%2Ftasks%2Ftask-stepping.htm

[Ciccioo]

EDIT: I am pretty sure the function sieveDeletablePrimes is correct and clean of bugs. The bug should be in the other function the..

	System.out.println(removeOneDigitAt(2, 0));

doesn't work, so there's your bug

if you check your code, you'll see that there is something that doesn't work with one-digit numbers

 

anyway, the resources @Nuluvius are your friend when you debug

either those, or just put print statements everywhere in the code, which is kind of the ghetto alternative to debuggers

[Nuluvius]

either those, or just put print statements everywhere in the code, which is kind of the ghetto alternative to debuggers

 

No! don't propagate this mode of thinking lol  :lol:

 

Try breaking your code up into testable chunks; write a failing test first, write your code and then make the test pass, then refactor. Try out JUnit for this.

[Maximation]

@ Maximation, you might find these of interest:

 

http://www.vogella.com/tutorials/EclipseDebugging/article.html

http://help.eclipse.org/juno/index.jsp?topic=%2Forg.eclipse.jdt.doc.user%2Ftasks%2Ftasks-debug-launch.htm

http://help.eclipse.org/juno/index.jsp?topic=%2Forg.eclipse.jdt.doc.user%2Ftasks%2Ftask-stepping.htm

 

I do not use Eclipse though..

How can I set them up manually?

[Maximation]

	System.out.println(removeOneDigitAt(2, 0));

doesn't work, so there's your bug

if you check your code, you'll see that there is something that doesn't work with one-digit numbers

 

anyway, the resources @Nuluvius are your friend when you debug

either those, or just put print statements everywhere in the code, which is kind of the ghetto alternative to debuggers

 

 

Yes indeed, I fixed it so it will return the the one-digit number, because one-digit primes are all deletable primes, right?

[Nuluvius]

I do not use Eclipse though..

How can I set them up manually?

 

What are you using?

[Maximation]

Good. So I now almost have setup the needed methods to calculate all of the deletable primes,there just needs to be implemented something to check if the digit 0 gets removed when the digit to the left of it gets removed.

But, how should I do this? Any hints?

[Maximation]

What are you using?

 

Coding in sublime text 3, compiling it through cmd.

[Nuluvius]

Coding in sublime text 3, compiling it through cmd.

 

Print lines are going to be your friend in that case.

[Maximation]

Print lines are going to be your friend in that case.

 

Yup, already using that method of debugging

[Maximation]

Adding lines 82 and 83 gives me these errors :

Exception in thread "main" java.lang.StackOverflowErrorat java.lang.String.valueOf(Unknown Source)at Main.removeOneDigitAt(Main.java:77)at Main.isDelPrime(Main.java:58)

it prints the deletable numbers through 97, but at 103 / 107 it stops and gives these errors.

 

[spoiler=removeOneDigitAt]

private static int removeOneDigitAt(int prime , int digit){		String n = String.valueOf(prime); 		String result;		try{			if(n.length() == 1)				return prime;			if(n.charAt(digit + 1) == '0')				return Integer.parseInt(n);			result = n.substring(0, digit);			if(n.length() > digit)				result = result.concat(n.substring(digit + 1));		} catch(StringIndexOutOfBoundsException e){			return prime;		}			return Integer.parseInt(result);	}