Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there any way by which one can check if an integer has a prime number as a subsequence (may be non-contiguous)?

We can check if they contain the digits 2,3,5 or 7 by going through the digits, but how to check if they contain 11, 13,... ?

One way would be to convert each number to a string and then call contains function, but that may be too expensive for a large range of numbers.

Any other efficient way?

share|improve this question

migrated from stackoverflow.com Aug 18 '11 at 13:01

This question came from our site for professional and enthusiast programmers.

    
Well, 13 composed of 1 and 3 therefore you don't need to worry about that (Or 17). –  anon Aug 18 '11 at 4:21
    
The sequence of digits in the prime can only follow the sequence of digits in the integer right? For instance 312 will contain 2 and 3 but not 13? –  arunkumar Aug 18 '11 at 4:25
    
Somehow I don't think you'll be able to do better than O(n!) with this problem. In general, you'd need to check that all digits are even, and then check all subsequences for primeness. You could speed this up with memoization, perhaps, but it would still need to compare (n) single digits, (n-1)/2 pairs, (n-2)/3 triplets, etc. –  tjarratt Aug 18 '11 at 4:26
1  
what about numbers containing 11 , 19.. eg. 110, 190 –  pranay Aug 18 '11 at 4:38
    
Are you looking for a specific prime number, or are you asking whether the exists a prime number in it? –  Robert Israel Aug 18 '11 at 17:01
show 1 more comment

3 Answers 3

up vote 6 down vote accepted

This can be tested efficiently due to a theorem of Shallit, which builds on a classical result on combinatorics on words:

Every prime has one of 2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, and 66600049 (Sloane's A071062) as a subsequence of its decimal digits.

To implement efficiently, I would suggest making an array of permissible 3-digit sequences and reducing mod 1000 (perhaps repeatedly, if testing shows it to be efficient). If you get a hit, you can short-circuit and return "true". Otherwise, convert the number to a string and use a standard regular expression library to efficiently test if

[2357]|1.*[19]|(?:8.*8|9.*(?:0.*0|9)|[46]).*1|(?:4.*[049]|(?:6.*4|9.*4(?:.*6){2}).*6|(?:9.*[069]|6.*(?:(?:0.*0|6.*[06])(?:.*0){3}|(?:6.*6|0).*6|9)).*4|8).*9

matches your number. This should take time linear in the length of the input number, both for conversion (if using an efficient algorithm) and regex testing (if using an efficient algorithm with regex preprocessing).

If you check the whole number in 1000-digit increments you can leave off the testing of the one-digit numbers.

share|improve this answer
add comment

This looks like a homework problem. A hint (hint #1): one way to answer this is to find methods for generating sequences that do not have prime subsequences. You see how to eliminate numbers with 2, 3, 5, 7. That leaves the numbers 0, 1, 4, 6, 8, and 9. Since the prime subsequences may be non-contiguous, then a 1 preceded by a 1, 4, or 6 will nix that number. If there is a 9, then any preceding 1 or 8 will nix the number.

The trivial sequences are any resamplings solely of 4, 6, 8, and 0.

So, look at what sequences you can generate with a 1 or 9 preceded by some of these #s. Assume that the following (trailing #s) are composite (e.g. a sequence of even #s), so you're looking for the longest sequence of composite #s ending in 1 or 9 and preceded by 4, 6, 8, and 0.

Hint #2: in a sense you're looking to create a variation on the Sieve of Eratosthenes.

Hint #3: 6 is nice because it's divisible by 3. 4 and 8 in a pair also guarantee divisibility by 3. So, 9 will be a little harder to kill off than the 1. (Update / side note: 6 is almost ideal among the 10 digits for a default value a "trivial" sequence - it is composite & it does nothing to affect divisibility mod 3.)

Hint #4: I'll kill 1 for you: if it is preceded by a 4, then you get a prime. Preceded by a 6: you get a prime. Preceded by 1 8: not a prime. Preceded by 2 8s: 881 is prime. So, the number 1 is killed.

Okay, now try to kill the # 9.

Hint #5: If you can't kill off a # (i.e. the # 9), then it implies there is a trivial sequence that precedes it.

These 5 hints plus a short table of primes (e.g. http://primes.utm.edu/lists/small/1000.txt) should be adequate to solve the problem entirely.

share|improve this answer
    
+1 yeah awesome. I gotta think a little more laterally that seems clearly a much better way to do than my suggestions, since now you shortcut tons of cases. –  shelleybutterfly Aug 18 '11 at 4:37
    
I killed all but one integer. :) Hint #3 should be something already familiar, but, if not, it's worth understanding. –  Iterator Aug 18 '11 at 4:41
add comment

Well, I think you'd need to set some sort of limitations on the size of the integer and the size of the prime, but one thought would be to break up the digits into an array of powers of 10, then you could take each of your primes, and do a search by taking each n-digit prime, comparing it to the low order n-digits and, if no match is found, shifting one digit (e.g. power of 10) to the left.

Another thought would be to generate a list of all primes up to n digits (where n is the number of digits in the the largest prime you will be checking against), then, after breaking up the integer into powers of 10, for each number of digits between 1 and n generate a list of permutations of n-digit-integers and compare by searching your list of all primes up to n digits.

The efficiency I am probably not the best to speak to, but I think there will be a lot of dependencies even on the limitations (or not) we can set on it ahead of time: e.g. are the primes pre-generated, what is the maximum number of digits in the integer or max prime to be searched. (I think the problem becomes intractable more quickly as the ratio of prime digits to integer digits approaches 1.) I also think that the most efficient algorithm in any of those cases may radically differ from one another. If this is for a general algorithm with no particular limitations, then it's very possible that the most efficient algorithm differs from the particular cases.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.