Project Euler #37 issue

Question

I tried to solve Project Euler #37:

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3. Find the sum of the only eleven primes that are both truncatable from left to right and right to left. NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

I wrote my code in Python but I am facing weird issues. Here's my code:

def isPrime(n):
    if n == 2 or n == 3 or n == 5: return True
    if n < 2 or n%2 == 0: return False
    if n < 9: return True
    if n%3 == 0: return False
    if n%5 == 0: return False
    r = int(n**0.5)
    f = 5
    while f <= r:
      if n%f == 0: return False
      if n%(f+2) == 0: return False
      f +=6
    return True

def gen(nb):
    results = []
    nb_str = str(nb)
    for k in range(0, len(nb_str) - 1):
        results.append(nb_str[k:])
        results.append(nb_str[-k:])
    return results

def check(nb):
    for t in gen(nb):
        if not isPrime(int(t)):
            return False
    return True

c = 0
s = 0
i = 2
while c != 11:
    if check(i):
        c += 1
        s += i
    i += 1
print(s)

Where does the error come from? (The expected result is 748317)

I suspect the errors coming from the results list

You've broken down your code into small, independently-usable functions, which is great—that means you can test those functions independently. Call `gen(nb)` on some numbers and see if you get the right results. If not, you've only got 6 lines of code to debug (and ask about on SO, if you get stuck) instead of the whole program. — abarnert, Aug 25 '18 at 20:48

Joe Iddon · Answer 1 · 2018-08-25T20:41:27.673

Yes, the gen() function is not working correctly as your slicing is off, also, you count 2, 3, 5 and 7 as truncatable primes which the question denies.

The second slice should be the other way around:

>>> s = 'abcd'
>>> for i in range(1,len(s)-1):
...     print(s[i:])
...     print(s[:-i])
... 
bcd
abc
cd
ab

which we can see produces the right strings.

Altogether then, the function should be:

def gen(nb):
    results = [nb]
    nb_str = str(nb)
    for k in range(1, len(nb_str)):
        results.append(int(nb_str[k:]))
        results.append(int(nb_str[:-k]))
    return results

note I also added a string to int conversion - not sure how Python didn't make that obvious for you :/

And before get the full solution, Project Euler nearly always gives you an example which you can use to check your code:

>>> check(3797)
True

You must also add a condition in the check function to return False if the number is 2, 3, 5 or 7 as this is stated clearly in the question.

And the result is the expected: 748317.

PM 2Ring · Accepted Answer · 2018-08-25T21:49:22.110

1

Joe Iddon has explained the error in your code, but you can speed it up a little by turning gen into an actual generator. That way, you can stop checking the results for a given nb as soon as you detect a composite number (and gen will stop generating them). I've also made a few minor tweaks to your primality tester. Remember, the or operator short-circuits, so if a is True-ish in a or b then it doesn't bother evaluating b.

def isPrime(n):
    if n in {2, 3, 5, 7}:
        return True
    if n < 2 or n%2 == 0:
        return False
    if n%3 == 0 or n%5 == 0:
        return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        if n%f == 0 or n%(f+2) == 0:
            return False
        f += 6
    return True

def gen(nb):
    yield nb
    nb_str = str(nb)
    for k in range(1, len(nb_str)):
        yield int(nb_str[k:])
        yield int(nb_str[:-k])

def check(nb):
    for t in gen(nb):
        if not isPrime(t):
            return False
    return True

c = s = 0
# Don't check single digit primes
i = 11
while c < 11:
    if check(i):
        c += 1
        s += i
        print(i)
    i += 2

print('sum', s)

output

In fact, you can get rid of the check function, and replace it with all, which also short-circuits, like or does. So you can replace the

if check(i):

with

if all(map(isPrime, gen(i))):

edited Aug 25 '18 at 21:49

answered Aug 25 '18 at 20:58

PM 2Ring

54,345
6
82
182

If your talking about optimising the solution, then the most drastic improvement would be to use a prime sieve and memoize. – Joe Iddon Aug 26 '18 at 11:46
@JoeIddon Using my best prime sieve, sieving the odd numbers under 1000000 in a bytearray, is about 10 times faster than this solution. But I didn't post that version, since it deviates so much from the OP's. And using a fixed sieve is cheating a little, since you need to specify the sieve size. I guess I could use a progressive sieve in a dict, but that would chew up a lot more RAM. – PM 2Ring Aug 26 '18 at 16:23
Why would you have to use the progressive sieve in a dict? Just increase the size by like `10000` if you haven't found `11` yet. – Joe Iddon Aug 26 '18 at 18:12
@JoeIddon You could do that, but I don't like it because you have to copy the old array to the new one. Or maintain multiple arrays. I mentioned using dict because there's an interesting prime generator that does that in [this answer](https://stackoverflow.com/a/10733621/4014959). (However, it's about twice as slow as my segmented sieve that uses bytearrays). But I guess a generator isn't so useful when you need random access to an indefinite sized set of primes. ;) – PM 2Ring Aug 26 '18 at 18:28
@JoeIddon Sorry if there's anything vague or confusing in my previous comment. It's 4:35AM here, and I may not be thinking straight. ;) – PM 2Ring Aug 26 '18 at 18:35
Thanks for the link, really cool algorithm! I don't see your point about copying the lists though, you can just concat `[False] * 10000` to the old boolean list and then start crossing them off again. – Joe Iddon Aug 26 '18 at 18:48

Project Euler #37 issue

2 Answers2