Project Euler #37 issue

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

gen(nb)

2 Answers
2

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.

gen

nb

gen

or

a

a or b

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

23
37
53
73
313
317
373
797
3137
3797
739397
sum 748317


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

check

all

or

if check(i):


with

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


10000

11

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.

gen()

2

3

5

7

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.

check

False

2

3

5

7

And the result is the expected: 748317.

748317

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.