D
D
Dmitry Temnikov2019-08-25 19:29:21
Python
Dmitry Temnikov, 2019-08-25 19:29:21

Euler project. Problem #37. I don't understand the question?

In general, there is a task euler.jakumo.org/problems/view/37.html
https://projecteuler.net/problem=37

The number 3797 has an interesting property. Being a prime number in itself, you can sequentially throw out digits from it from left to right, while the number remains prime at each stage: 3797, 797, 97, 7. In exactly the same way, you can throw out digits from right to left: 3797, 379, 37, 3.
Find the sum of the only eleven prime numbers from which you can throw out numbers both from right to left and from left to right, but the numbers remain prime.
NOTE: The numbers 2, 3, 5 and 7 are not considered as such.

The Python3 solution looks like this:
n = 1000000 
a = list(range(n+1))
a[1] = 0; lst = []
i = 2
while i <= n:
    if a[i] != 0:
        lst.append(a[i])
        for j in range(i, n+1, i):
            a[j] = 0
    i += 1
    
def isSimple(num):
    if num<1 or num in [4,6,9]: return False
    for i in range(2,ceil(sqrt(num))):
        if num%i==0: return False
    return True

def trunc_combinations(s1):
    lst=[s1]
    for i in range(1,len(s1)):
        lst.append(s1[i:])
        lst.append(s1[:i])
    return lst

def isTruncSimple(num):
    combinations=trunc_combinations(str(num))
    for combination in combinations:
        if not isSimple(int(combination)):
            return False
    return True
    
lch=[]
for num in lst[4:]:
    if isTruncSimple(num):
        lch.append(num)
print(lch)
print(sum(lch))
    
print(datetime.now()-start)

The solution appears to be working. I don’t go into the description of the algorithm, those who understand Python3 will understand. Why exactly, and not like that, I also don’t specify, some of the decisions were made to speed up the algorithm. In general, it gives the following result
[11, 13, 17, 23, 31, 37, 53, 71, 73, 113, 131, 137, 173, 197, 311, 313, 317, 373, 797, 1373, 1997, 3137, 3797, 7331, 73331, 739397]
833554
Question: what 11 elements are discussed in the problem? What exactly to sum up? Naturally, the answer is not accepted. Increasing the counter above 1000000 is also probably not worth it, so it's overkill :-)

Answer the question

In order to leave comments, you need to log in

3 answer(s)
L
longclaps, 2019-08-25
@exibit777

think with your head

[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]

K
Karpion, 2019-08-28
@Karpion

According to my feelings - you consider "1" a prime number, and the authors of the problem think differently.
In general, whether to consider "1" as a prime number depends on the volitional decision. Many theorems on the topic of prime numbers - do not work on one, so it was excluded from the Komsomol from the list of prime numbers.
Upd: I opened the comment thread above - it turns out that it is already there.

K
Konstantin, 2020-02-26
@kotam

The same story was, translated "1" into "difficult" and the answer came together! But "1" is a composite, or what, or is it "1" in itself?

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question