Left Truncatable Primes Java Program

IamtheWalrus

Hi all,

I have a Java problem I need to solve regarding Left Truncatable Primes. I was wondering if any of you had a solution to this or even how it would be done.

Any help would be appreciated.

Thanks,
Walrus

Left Truncatable Primes

Background

A Left-Truncatable Prime (LTP) is a prime number which (a) contains no 0 digits and (b) remains prime when any contiguous sequence of left-most digits is removed.
For example:

• 5167 is an LTP, since 5167, 167, 67 and 7 are all prime;
• 2179 is not an LTP, even though 2179, 179 and 79 are prime, since 9 is not prime.

There are 2166 LTPs under 1,000,000,000.
Task

Write a command-line program in Java that:

• takes a single integer, n (1 ≤ n ≤ 2166) as a command-line argument
• calculates the nth Left-Truncatable Prime
• writes the output to the console (ie System.out)

For example:

• input 10 should give output 47
• input 100 should give output 5167
• input 1000 should give output 8391283

Performance is a consideration in your solution to the problem (though not the only one). Your program should be able to produce a correct answer (for any valid input) within about 0.5 seconds on a normal PC.
Notes

Bear in mind that:

• There is no time limit, but, as a guide, we wouldn’t envisage the task taking longer than an hour or so
• We are not looking for a “trick” answer (eg one that doesn’t involve doing any computation!)
• This is an opportunity to show how you write “production quality” code

seamus

Do you have any idea on how to do it yourself?

We generally won't give you the answer to a problem, we'll usually only help steer you in the right direction, so letting us know what you're having difficulty with is the best way to get started.

IamtheWalrus

seamus wrote: »

Do you have any idea on how to do it yourself?

We generally won't give you the answer to a problem, we'll usually only help steer you in the right direction, so letting us know what you're having difficulty with is the best way to get started.

I have no idea. None. I was hoping the problem would been a known problem and a widely available solution would be circulating the web. A long shot, I acknowldge. I am very busy and not clever enough to solve it.

seamus

The easiest way is to try and figure out how you would solve it using a pen and paper - what steps would you use, and so forth.

I'll give you a few tips on how the process works:

1. Find the first LTP (tip: it's 2).
2. Find the next n - 1 LTPs
3. Output the last one that you find.

In order to determine if a number is an LTP, first you figure out if it's a prime number, then you take each "sub-number" and determine if each of them is a prime number.

There are tonnes of algorithms online for determining if a given number is a prime number.

I'll also give you a quick tip:
Although it appears that you need to "check" 1,000,000 numbers, in reality all prime numbers after 5, end in 1, 3, 7 or 9. This means that you only have a total of 40,000 possible numbers to check.

There will also be a whole host of other tricks you can use too. (Thankfully) Google won't give you the answer, but it will tell you exactly how to write the code.

IamtheWalrus

seamus wrote: »

The easiest way is to try and figure out how you would solve it using a pen and paper - what steps would you use, and so forth.

I'll give you a few tips on how the process works:

1. Find the first LTP (tip: it's 2).
2. Find the next n - 1 LTPs
3. Output the last one that you find.

In order to determine if a number is an LTP, first you figure out if it's a prime number, then you take each "sub-number" and determine if each of them is a prime number.

There are tonnes of algorithms online for determining if a given number is a prime number.

I'll also give you a quick tip:
Although it appears that you need to "check" 1,000,000 numbers, in reality all prime numbers after 5, end in 1, 3, 7 or 9. This means that you only have a total of 40,000 possible numbers to check.

There will also be a whole host of other tricks you can use too. (Thankfully) Google won't give you the answer, but it will tell you exactly how to write the code.

Much appreciated Seamus. I will have a good look at this this afternoon and make a start.

murphaph

seamus wrote: »

1. Find the first LTP (tip: it's 2).
2. Find the next n - 1 LTPs
3. Output the last one that you find.

if I've understood what an LTP is then 2 isn't one. If you remove the leftmost digit from 2, 5, or 7 you have nothing left, certainly not another prime number, so how can they be classified as Left truncatable?

Or is it the result of the truncation that is called an LTP?

seamus

murphaph wrote: »

if I've understood what an LTP is then 2 isn't one. If you remove the leftmost digit from 2, 5, or 7 you have nothing left, certainly not another prime number, so how can they be classified as Left truncatable?

Or is it the result of the truncation that is called an LTP?

I have no idea. What I gathered was that any number, x, is an LTP if for every value of 0 <= n < length(x), the result of left-truncating x by n digits, results in a prime.

So in the first iteration, you truncate x by 0 digits, and if you get a prime number, then the test is true for n = 0.

Wiki agreed with me: http://en.wikipedia.org/wiki/Truncatable_prime

Point of technicality really, I'd never heard of an LTP before this morning, so I have no authority here.

There's an obvious implication assuming that 2, 3, 5 & 7 are LTPs - that since every single LTP is a product of the concatenation of LTPs, then I have a much easier base for looking for longer LTPs.

That is, if I know all of of the two-digits LTPs, (let's say there are fifty of them), then I know that there are at most 450 (9 x 50) 3-digit LTPs.

I'm years out of any kind of serious mathematics, so I don't know how to express that more scientifically

murphaph

lol, I'm none the wser after reading the wiki. Years out of maths at college as well and don't recall ever hearing about these things (sounds like they were only dreamt up to give computer science students something to do lol).