A Very Special Prime Number

Computer Science Level 3

There exists some prime numbers with a special property that is if we keep removing digits from the right-hand end of the number, it still remains a prime number. For example, 239 is a prime number, 23 is prime and 2 is also prime.

Find the largest possible number with this special property.

The answer is 73939133.

2 solutions

Brian Charlesworth
Feb 21, 2017

Such primes are known as right- truncatable primes . Surprisingly there are only a finite number of them (in base 10), 83 of them to be exact, with the largest being $73939133$ .

Is this solvable by hand? If no, this problem should be converted into Computer Science.

Pi Han Goh - 4 years, 3 months ago

No, it's not. It took a Google search to come up with an answer, and I was quite surprised to find that there was a finite maximum. The paper by Angell and Godwin that identifies this maximum is published in the "Mathematics of Computation" journal, so I agree that this problem should probably be in the Computer Science section. In the abstract of the paper it is stated that "The sizes of the largest truncatable primes in a given number base are estimated by a probabilistic argument and compared with computed values", so there is a lot of heavy-duty math going on here, but I think the only way this question will work on Brilliant is for it to be in Computer Science.

@Nashita Rahman Would it be o.k. if this problem were put in the Computer Science section? I think it will work better there for the reasons I've outlined above.

Brian Charlesworth - 4 years, 3 months ago

Even I did solve it using a computer program but I thought that there might be a possibility to solve it by hand so I kept it under Number Theory but I now see that it should be there in Computer Science because there's only one solver till now. I have put it under Computer Science. Thanks.

Nashita Rahman - 4 years, 3 months ago

@Nashita Rahman – O.k., great. It will be interesting to see how many more people will solve it now. :)

Brian Charlesworth - 4 years, 3 months ago

@Brian Charlesworth – I still see that there is only one solver(you) till now , I don't know why is it so?

Nashita Rahman - 4 years, 3 months ago

@Nashita Rahman – Since your comment there has been one more solver. :) This is a difficult problem so I wouldn't expect that many solvers, or even attempts. Also, the problem has been up a few days now but was initially in the Number Theory section, so it might not have got much attention from people who prefer Computer Science problems when the question was new.

Some questions I've posted in the past have been less "popular" than I initially thought they would be, and some others have been more popular than I expected. If it doesn't get many views early on, an otherwise good problem might never get the attention it deserves. However, with one such problem I waited a couple of weeks and reposted it, (I didn't delete the original), and the repost, which was exactly the same question, did become popular, so sometimes its just a matter of timing.

Brian Charlesworth - 4 years, 3 months ago

@Brian Charlesworth – But I see that at the moment this problem has 32 views so I think it's fine and it has only 3 attempts so it's really a tough Problem! Thanks.

Nashita Rahman - 4 years, 3 months ago

Andrew Lamoureux
Aug 29, 2017

Here's some python to find the answer: 73939133

from math import ceil, sqrt

def isprime(n):
    return []==filter(lambda x: n%x==0, range(2,int(sqrt(n)+1)))

def search(n):
    tries = filter(isprime, map(lambda x: n*10+x, range(10)))
    return max([n] + map(search, tries))

print max(map(search, [2,3,5,7]))

You can modify the code a bit to show the search in progress - it would have been tedious to do by hand!

A Very Special Prime Number

The answer is 73939133.

2 solutions

0 pending reports