[Problem Solving #1] Deletable Primes

[Ciccioo]

Adding lines 82 and 83 gives me these errors :

well... you know the line, you know the error, and you know that adding that line created the error

so yeah, know what needs to be changed

think about the condition, maybe later, with a fresh mind

[wolfsinner]

I actually meant it to be as I put it (digit-1). I didn't test the code at the time, but I did now and it works. It seemed to me like you were going for this digit indexing format:

654321 -> n

123456 -> digit index

 

So removeOneDigitAt(654321, 2) would remove 5, and result in 64321. Running this results in the expected output:

int n = 654321;for(int i = 1 ; i <= String.valueOf(n).length() ; i++)   System.out.println(removeOneDigitAt(n, i));

EDIT: This forum is wacky today for me. I meant to say this as well:

 

But it seemed like you wanted the following:

654321 -> n

012345 -> digit indexing

 

Either way it works. An easy (but somewhat more expensive) way to check if it removed more digits is to check if n.length() - String.valueOf(Integer.parseInt(result)).length() > 1.

 

The stack overflow is not the fault of the removeOneDigitAt function, but of what you're feeding it, or how your recursion is being done. Stack overflow is usually the product of too deep recursive calls, or too large an amount of memory used for local method data.

[Nuluvius]

@Maximation it may benifit you more to move to something like Eclipse or the community edition of IntelliJ. That way you can walk through your code and get more of a handle as to what is going on and where.

[Nuluvius]

Ok I yield, here's the relevant parts of my (broken) code. As I mentioned previously I used TDD (with NUnit) implementing in C# using TPL and a MVVM/WPF architecture. I swapped implementation from C++ AMP early on.

 

 

MainViewModel - Relevant Tests (all fail)

MainViewModel - Relevant Methods

This function is what I am most unsure about. Hence the sparse testing; a little direction less.

ULongExtensionMethods - Tests (all pass)

ULongExtensionMethods

SieveOfAtkin - Tests (limited but all pass)

I feel these tests are very limited, I would ideally test the upper ranges but alas my affliction has gotten the better of me.

SieveOfAtkin

With removed parallel for loops... (suspect that maybe a http://msdn.microsoft.com/en-us/library/dd267312(v=vs.110).aspx might solve the race condition).

    [TestFixture]    class WhenProcessingNumbers    {        private MainViewModel _vm;        [SetUp]        public void SetUp()        {            _vm = new MainViewModel();        }        [Test]        public void TheResultMatchesTheExampleOutput()        {            _vm.LowerInput = 0;            _vm.UpperInput = 10000;            _vm.ProcessNumbers();            Assert.That(_vm.Result, Is.EqualTo(string.Format("{0}{1}{2}", 699, Environment.NewLine, 3168960)));        }        [TestCase(410256793ul, TestName = "410256793")]        public void DeletablePrimesAreRecognised(ulong number)        {            Assert.That(MainViewModel.IsDeletablePrime(number.ToString(CultureInfo.InvariantCulture), 0));        }    }

        internal static bool IsDeletablePrime(string number, int iteration)        {            if (number.StartsWith("0"))            {                number = number.Remove(0, 1);            }            if (iteration <= 0)            {                number = number.Remove(0, 1);            }            var isValid = Convert.ToUInt64(number).IsPrime();            if (!isValid || number.Length <= 1)            {                return isValid;            }            number = number.Remove(0, 1);            iteration++;            // Will swap recursion for iteration shortly (faster in C#)            return IsDeletablePrime(number, iteration);        }

        internal void ProcessNumbers()        {            IsBusy = true;            _uiContext.Invoke(Clear);            var primes = new SieveOfAtkin(UpperInput).ToList();            _uiContext.Invoke(() => Primes = new ObservableCollection<ulong>(primes));            NotifyPropertyChanged("Primes");            _cs.Token.ThrowIfCancellationRequested();            var count = 0ul;            // For is faster than foreach in C#, will swap            foreach (var p in Primes)            {                _cs.Token.ThrowIfCancellationRequested();                var add = p < 10;                if (!add)                {                    add = IsDeletablePrime(p.ToString(CultureInfo.InvariantCulture), 0);                }                if (!add)                {                    continue;                }                count += p;                _uiContext.Invoke(() => DeletablePrimes.Add(p));            }            _cs.Token.ThrowIfCancellationRequested();            _result[0] = (ulong)DeletablePrimes.Count;            _result[1] = count;        }

    [TestFixture]    class WhenCheckingIsPrime    {        [TestCase(2ul, TestName = "2")]        [TestCase(3ul, TestName = "3")]        [TestCase(5ul, TestName = "5")]        [TestCase(7ul, TestName = "7")]        [TestCase(11ul, TestName = "11")]        public void ForPrimeNumbers_ThenTheResultIsTrue(ulong number)        {            Assert.That(number.IsPrime());        }        [TestCase(0ul, TestName = "0")]        [TestCase(1ul, TestName = "1")]        [TestCase(4ul, TestName = "4")]        [TestCase(6ul, TestName = "6")]        [TestCase(8ul, TestName = "8")]        public void ForNonPrimeNumbers_ThenTheResultIsFalse(ulong number)        {            Assert.That(!number.IsPrime());        }    }

    public static class ULongExtensionMethods    {        public static bool IsPrime(this ulong value)        {            if (value < 2)            {                return false;            }            if (value % 2 == 0)            {                return value == 2;            }            var root = (ulong)Math.Sqrt(value);            for (ulong i = 3; i <= root; i += 2)            {                if (value % i == 0)                {                    return false;                }            }            return true;        }    }

    [TestFixture]    class WhenApplyingSieveOfAtkin    {        [TestCase(10ul, new ulong[] { 2, 3, 5, 7 }, TestName = "Single Digits")]        [TestCase(20ul, new ulong[] { 2, 3, 5, 7, 11, 13, 17, 19 }, TestName = "Double Digits")]        public void ToALimitContainingPrimeNumbers_ThenThePrimeNumberAreFound(ulong limit, ulong[] primeRange)        {            Assert.That(new SieveOfAtkin(limit).ToArray().SequenceEqual(primeRange));        }        [Test]        public void ToALimitContainingNoPrimeNumbers_ThenNoPrimeNumbersAreFound()        {            Assert.That(new SieveOfAtkin(1).Count(), Is.EqualTo(0));        }        [Test]        public void ToAZeroLimit_ThenNoPrimeNumbersAreFound()        {            Assert.That(new SieveOfAtkin(0).Count(), Is.EqualTo(0));        }        [Test]        public void ToAnEdgeCaseLimit_ThenTheCorrectPrimeNumbersAreFound()        {            Assert.That(new SieveOfAtkin(3).ToArray().SequenceEqual(new ulong[] { 2, 3 }));        }    } 

    class SieveOfAtkin : IEnumerable<ulong>    {        private readonly List<ulong> _primes;        private readonly ulong _limit;        public SieveOfAtkin(ulong limit)        {            _limit = limit;            _primes = new List<ulong>();        }        public IEnumerator<ulong> GetEnumerator()        {            if (!_primes.Any())            {                FindPrimes();            }            return ((IEnumerable<ulong>)_primes).GetEnumerator();        }        IEnumerator IEnumerable.GetEnumerator()        {            return GetEnumerator();        }        private void FindPrimes()        {            var isPrime = new bool[_limit + 1];            var sqrt = Math.Sqrt(_limit);            for (ulong x = 1; x <= sqrt; x++)            {                for (ulong y = 1; y <= sqrt; y++)                {                    var n = 4 * x * x + y * y;                    if (n <= _limit && (n % 12 == 1 || n % 12 == 5))                    {                        isPrime[n] ^= true;                    }                    n = 3 * x * x + y * y;                    if (n <= _limit && n % 12 == 7)                    {                        isPrime[n] ^= true;                    }                    n = 3 * x * x - y * y;                    if (x > y && n <= _limit && n % 12 == 11)                    {                        isPrime[n] ^= true;                    }                }            }            for (ulong n = 5; n <= sqrt; n++)            {                if (!isPrime[n])                {                    continue;                }                var s = n * n;                for (var k = s; k <= _limit; k += s)                {                    isPrime[k] = false;                }            }            if (_limit >= 2)            {                _primes.Add(2);                            }            if (_limit >= 3)            {                _primes.Add(3);            }            for (ulong n = 5; n <= _limit; n += 2)            {                if (isPrime[n])                {                    _primes.Add(n);                }            }        }    }

[wolfsinner]

Ok I yield, here's the relevant parts of my (broken) code. As I mentioned previously I used TDD (with NUnit) implementing in C# using TPL and a MVVM/WPF architecture. I swapped implementation from C++ AMP early on.

 

The main thing I notice (unless I'm looking at it wrong), is that you're only removing the most significant digits of each number. So in the case of, for example, 410256793, you'll never reach a point where you've removed only digit 0, which is the first step to finding this Deletable Number in particular. You'll only test 410256793, then 10256793, then 256793, then 56793, etc.

Again, I could be looking at it wrong, I've been working all day! So please correct me if I'm wrong.

By the way, I wouldn't worry about parallelism here, since this is being done for the fun of it. My solution solves this problem in way less than 1 second (and I mean way less), and it's single-threaded.

[Nuluvius]

The main thing I notice (unless I'm looking at it wrong), is that you're only removing the most significant digits of each number. So in the case of, for example, 410256793, you'll never reach a point where you've removed only digit 0, which is the first step to finding this Deletable Number in particular. You'll only test 410256793, then 10256793, then 256793, then 56793, etc.

Again, I could be looking at it wrong, I've been working all day! So please correct me if I'm wrong.

By the way, I wouldn't worry about parallelism here, since this is being done for the fun of it. My solution solves this problem in way less than 1 second (and I mean way less), and it's single-threaded.

 

Firstly on the topic of threads, yes I agree and it's done this way in respect of 'just for fun'. Incidentally mine crunches through in under a second also; perhaps the next stage could be benchmark comparisons (complicated a little due to differing hardware - perhaps if we elected a neutral party)?

 

Secondly yes you are correct I think. That function is going to remove every single digit from left to right. I'm afraid I simply don't understand the other process to which you elude  

[wolfsinner]

Firstly on the topic of threads, yes I agree and it's done this way in respect of 'just for fun'. Incidentally mine crunches through in under a second also; perhaps the next stage could be benchmark comparisons (complicated a little due to differing hardware - perhaps if we elected a neutral party)?

 

Secondly yes you are correct I think. That function is going to remove every single digit from left to right. I'm afraid I simply don't understand the other process to which you elude  

 

Good multi-threaded code is undoubtedly faster than single-threaded code, and if it gives you pleasure to write it multi-threaded then you're more than welcome! It's very simple to split this particular problem into several threads.

On the topic of problem solving, it is mostly about solving the problem itself (and ideally do it in less than 1 second). But if people want to share their execution times, it's a cool experience (albeit innacurately compared). Personally I find the discussion of time complexity more interesting.

 

If you'll notice in the first example, we first remove the 0 in 410256793, producing 41256793. This removed a single digit in the middle of the integer. You have to try all of these possibilities at least once.

A simple way to do this digit removal is the following (in pseudo-code):

int removeDigit(int digit, int n){   int p1 = 10^digit //the ^ symbol is the power function   int p2 = 10^(digit-1)     int result = (n/p1)*p2 + (n mod p2);    if digits_in(n) - digits_in(result) > 1 then //can be easily checked with p2/10 > result      //the removal is invalid (example of 10859, removing digit 1 actually removes two digits, producing 859)      //do whatever you want about it (I'd simply return n)   else return result;}

Keep in mind though, that the power function is usually expensive, and there are faster ways of doing this instead of constantly calling this function (namely avoiding calculation repetition).

[Ciccioo]

alright, i tried to cut all the fat i could off my code

the result is this thing, slightly faster and much less readable

(the mod method for removing a digit is shamelessly copied from this post, and the sieve took a great... inspiration from this thread. i didn't feel like implementing a different sieve was worth it though, reading the numbers on the web)

#include <stdio.h>#include <stdlib.h>#include <math.h>#define N 10000000#define BASE 10typedef enum{    true,    false}bool;int main(){    bool* isDelPrime = calloc(N, sizeof *isDelPrime);    isDelPrime[0] = isDelPrime[1] = false;    size_t nDigits = 1, nDelPrimes = 0;    long long sumDelPrimes = 0;    int lowerBound = 0, upperBound = BASE;    int sqrtn = (int)sqrt(N);    size_t i, j;    for(i = 2; i < N; i++)        if(isDelPrime[i] == true){            // erastothenes sieve            if(i <= sqrtn)                for(j = i * i; j <= N; j += i)                    isDelPrime[j] = false;            // deletable prime check            if(i < BASE){                nDelPrimes++;                sumDelPrimes += i;                continue;            }            isDelPrime[i] = false;            if(i >= upperBound){                lowerBound = upperBound / BASE;                upperBound *= BASE;                nDigits++;            }            int factorA = 1;            for(j = 0; j < nDigits; j++){                int factorB = factorA * BASE;                int trunkB = (i / factorB) * factorB;                int newPrime = trunkB / BASE + (i % factorA);                if(isDelPrime[newPrime] == true && newPrime >= lowerBound){                    nDelPrimes++;                    sumDelPrimes += i;                    isDelPrime[i] = true;                    break;                }                factorA *= BASE;            }        }    free(isDelPrime);    printf("%zu\n%lld\n", nDelPrimes, sumDelPrimes);    return 0;}

i didn't test it really, but i think that if i took my old code, and just swapped the recursive implementation of countDigits for an iterative one, the performance would be pretty much the same as this atrocity

 

i'm done with this, i'll try another approach if i can think of, but this is as much as i can stretch this code

[Maximation]

Good multi-threaded code is undoubtedly faster than single-threaded code, and if it gives you pleasure to write it multi-threaded then you're more than welcome! It's very simple to split this particular problem into several threads.

On the topic of problem solving, it is mostly about solving the problem itself (and ideally do it in less than 1 second). But if people want to share their execution times, it's a cool experience (albeit innacurately compared). Personally I find the discussion of time complexity more interesting.

 

If you'll notice in the first example, we first remove the 0 in 410256793, producing 41256793. This removed a single digit in the middle of the integer. You have to try all of these possibilities at least once.

A simple way to do this digit removal is the following (in pseudo-code):

Keep in mind though, that the power function is usually expensive, and there are faster ways of doing this instead of constantly calling this function (namely avoiding calculation repetition).

Mh, I do not really understand what you are doing in that method. Could you explain it?

[Nuluvius]

Good multi-threaded code is undoubtedly faster than single-threaded code, and if it gives you pleasure to write it multi-threaded then you're more than welcome! It's very simple to split this particular problem into several threads.

On the topic of problem solving, it is mostly about solving the problem itself (and ideally do it in less than 1 second). But if people want to share their execution times, it's a cool experience (albeit innacurately compared). Personally I find the discussion of time complexity more interesting.

 

If you'll notice in the first example, we first remove the 0 in 410256793, producing 41256793. This removed a single digit in the middle of the integer. You have to try all of these possibilities at least once.

A simple way to do this digit removal is the following (in pseudo-code):

int removeDigit(int digit, int n){   int p1 = 10^digit //the ^ symbol is the power function   int p2 = 10^(digit-1)     int result = (n/p1)*p2 + (n mod p2);    if digits_in(n) - digits_in(result) > 1 then //can be easily checked with p2/10 > result      //the removal is invalid (example of 10859, removing digit 1 actually removes two digits, producing 859)      //do whatever you want about it (I'd simply return n)   else return result;}

Keep in mind though, that the power function is usually expensive, and there are faster ways of doing this instead of constantly calling this function (namely avoiding calculation repetition).

 

 

Doesn't matter. You want to determine whether a number is a deletable prime or not. The sequence through which you determine that is irrelevant! 

 

I'm confused as well, I was acting under the premise that the ordering and permutations were irrelevant (I was concerned about that).

[wolfsinner]

Mh, I do not really understand what you are doing in that method. Could you explain it?

 

It's simple math, you could try it on a bit of paper. As an example, let's see removeDigit(3, 123456):

n = 123456

digit = 3

p1 = 10³ = 1000

p2 = 10² = 100

 

           123456

n/p1= ----------- = 123; 123 x p2 = 123 x 100 = 12300 (part to the left of the digit, we add the zeros because we want that part intact)

              1000

 

n mod p2 = 123456 % 100 = 56 (part to the right of the digit)

 

12300 + 56 = 12356, which is the desired number (indexing the digit from right to left).

 

The idea is that if you want to remove the 3rd digit, you'll have to truncate to the left of the 3rd digit by dividing it by the 3rd power of 10. Then you need to get what's to the right of the digit, but not the digit itself, thus you want to get the remainder of the division by the 2nd (digit-1) power of 10.

This is math, its principles are very basic so it's hard to explain. But you should understand it by trying it out yourself! 

 

 

I'm confused as well, I was acting under the premise that the ordering and permutations were irrelevant (I was concerned about that).

 

Maybe I wasn't clear about that, sorry!

What I meant by the sequence being irrelevant can be illustrated by the example of 47. There are 7 three-digit primes from which you can produce 47 by digit removal. They are: 347, 457, 479, 487, 547, 647 and 947.

You can deduce that 47 is a deletable prime from any of them. Similarly, you can deduce 7 is a deletable prime from 47, or 17, 37, 67, 71, 73, 79 and 97.

So, it is irrelevant from which sequence you deduce a number's deletable primality, but you absolutely need to check a lot of different digit removals.

Edited July 2, 2014 by wolfsinner

[Maximation]

Good. I believe I am almost at the solution. There is another weird problem though.

Let me give you the method it is occuring in :

 

This method counts 11 as a deletable prime (it is not a deletable prime, right? Because 1 != a prime) even though I set as one condition :

This checks if the number after the removal of 1 digit is a prime and only then returns true for the whole number (11 in this case) --> meaning it is a deletable prime.

 

Why does it do this?

 

EDIT: oh wait, it doesn't

/*	*	argument will always be a prime number	*/	private static boolean isDelPrime(int prime){		System.out.println(prime);		String number = String.valueOf(prime);		int size = number.length();		if(size == 1)			return true;		int numberWorkingWith = prime;		for(int i = 0; i < size; i++){			int n = removeDigitAt(numberWorkingWith, i);			if(isPrime[n] && n != numberWorkingWith)				if(isDelPrime(removeDigitAt(numberWorkingWith, i))) return true;		}		return false;	}

isPrime[n]

[Maximation]

Well. I tried it. It is incorrect.

I tried the 10 000 aswell, for some reason my program counts 5 deletable primes less (699 - 694). How..?

I do not know which ones it does not count though, that makes debugging a lot harder..

public class Main {	private static final int NUMBER = 10000;	private static boolean[] isPrime = new boolean[NUMBER];	private static int numOfDelPrimes = 0;	private static long sumofDelPrimes = 0;	public static void main(String[] args){		sieve();		sieveDeletablePrimes();		System.out.println();		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)){					System.out.println(i);					numOfDelPrimes++;					sumofDelPrimes += i;				}			}		}	}	/*	*	argument will always be a prime number	*/	private static boolean isDelPrime(int prime){//		System.out.println(prime);		String number = String.valueOf(prime);		int size = number.length();		if(size == 1)			return true;		int numberWorkingWith = prime;		for(int i = 0; i < size; i++){			int n = removeDigitAt(numberWorkingWith, i);			if(isPrime[n] && n != numberWorkingWith)				if(isDelPrime(removeDigitAt(numberWorkingWith, i))) return true;		}		return false;	}	private static int removeDigitAt(int prime , int index){		String numb = String.valueOf(prime);		int length = numb.length();				if(length > index + 1 && numb.charAt(index + 1) == '0')			return prime;		String result = numb.substring(0, index) + numb.substring(index + 1);		return Integer.parseInt(result);	}}

[Ciccioo]

Well. I tried it. It is incorrect.

I tried the 10 000 aswell, for some reason my program counts 5 deletable primes less (699 - 694). How..?

I do not know which ones it does not count though, that makes debugging a lot harder..

print them

at my second try i went crazy because i was missing 4 primes: 2, 3, 5, 7

[wolfsinner]

Can I see your full code? I think it might be the primes under 10 (which are only 4 though). 

 

EDIT: Oh wait, it's there. 

 

Your code is missing 1303, 5209, 5303, 5309, and 7901.

[fizzlesticks]

Your problem is in the line

if(length > index + 1 && numb.charAt(index + 1) == '0')

Having a 0 at the next position only matters if index == 0

[Maximation]

Your problem is in the line

if(length > index + 1 && numb.charAt(index + 1) == '0')

Having a 0 at the next position only matters if index == 0

 

Of course. Thank you!

[wolfsinner]

Well. I tried it. It is incorrect.

I tried the 10 000 aswell, for some reason my program counts 5 deletable primes less (699 - 694). How..?

I do not know which ones it does not count though, that makes debugging a lot harder..

 

A quick look at your code reveals it is as fizzlesticks says. A simpler check is:

private static int removeDigitAt(int prime , int index){    String numb = String.valueOf(prime);   int length = numb.length();    String result = numb.substring(0, index) + numb.substring(index + 1);    if(result.charAt(0) == '0') return prime;   return Integer.parseInt(result); }

[Maximation]

 

A quick look at your code reveals it is as fizzlesticks says. A simpler check is:

-snip-

 

The output of my code at NUMBER = 10 000 is the same as the output you wrote as an example in the original problem description.

When I try to submit my code at NUMBER = 10 000 000 it says it is incorrect..

Am I missing something? It should be correct now, right?

[wolfsinner]

The output of my code at NUMBER = 10 000 is the same as the output you wrote as an example in the original problem description.

When I try to submit my code at NUMBER = 10 000 000 it says it is incorrect..

Am I missing something? It should be correct now, right?

 

With the code change I provided, it is producing the correct result (I just tested it). Are you putting a line break at the end of every line?

[Maximation]

With the code change I provided, it is producing the correct result (I just tested it). Are you putting a line break at the end of every line?

Should I write "\n" after each line? I mean, an enter is not registered?

EDIT: Tried it, but it still says it is incorrect.

[wolfsinner]

Should I write "\n" after each line? I mean, an enter is not registered?

 

println does that for you. Are you copying the line breaks as well? The output format is:

x

y

 

With x being the count, and y the sum. There must be a line break after y as well (essentially you should press the return key after y, if you didn't copy it with a line break from the output).

I sent you a PM.

[Ciccioo]

Should I write "\n" after each line? I mean, an enter is not registered?

EDIT: Tried it, but it still says it is incorrect.

it does this because you're using a different username than the one you have on this forum: it's punishing you

[Maximation]

it does this because you're using a different username than the one you have on this forum: it's punishing you

 

Ahh Haha. Interesting.

[Maximation]

It is still incorrect. Even with \n after each line (I still don't know if I am supposed to type \n after the line)