Building Primes

December 21, 2012

It is sometimes possible, starting with a prime, to add a digit to the front of the number that forms a new prime. For instance, starting from prime 7, adding 1 forms prime 17, adding 3 forms prime 317, adding 6 forms prime 6317, adding 2 forms prime 26317, and so on.

Your task is to write a program to find the largest prime that can be formed in this way. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

20 Responses to “Building Primes”

  1. Paul said

    A Python version.

    def extend(n):
        strn = str(n)
        for i in range(1,10):
            newi = int(str(i) + strn)
            if not P.is_prime(newi):
                yield n
            else:
                for p in extend(newi):
                    yield p
    
    print max(list(max(extend(i)) for i in [1,3,5,7,9]))
    
  2. [...] Question is from Programmingpraxis: [...]

  3. Johann Hibschman said

    Here’s a J version:

    nextPrimesWithScale=: 4 : '(#~ 1&p:) ,(x:(>:i.9)*10^x) +/ y'
    nextPrimes=: 3 : '(>.10^.{.y) nextPrimesWithScale y'
    nextPrimesWithMax=: 3 : 0
      max=. {.y
      primes=. }.y
      newPrimes=. nextPrimes primes
      (>./max,newPrimes),newPrimes
    )
    nextPrimesWithMax^:_ ] 1 0
    

    Running this gives 99918918997653315499663.

  4. programmingpraxis said

    Johann: Your solution is incorrect. Starting from the right, 3 is prime, but 63 is not, so your number is not prime at every step.

  5. programmingpraxis said

    Paul: Your program has an extraneous P. on line 5. After removing that and adding an is_prime function, I ran it, and it produced the correct answer. However, your starting point is wrong. You should use 2, 3, 5, 7 for starters instead of 1, 3, 5, 7, 9 because two of the starters are non-prime, and the task requires that all intermediate numbers must be prime.

  6. Paul said

    OK, I was lucky, as the chains for 1 and 9 give results, that are smalller than the result for 7. I omitted 2, because it is clear form the start, that all the next values will be non prime.

  7. You’re right. I dropped out of extended precision for the last step. Line 1 should have been

    nextPrimesWithScale=: 4 : '(#~ 1&p:) ,((>:i.9)*x:10^x) +/ y'
    

    “10^x” was returning a double, rather than an extended precision integer. Moving the “x:” in front of it forces it to be extended-precision. I’m still a little fuzzy on J’s extended precision rules.

    Also, the last (run) line should have been:

    nextPrimesWithMax^:_ ] 0 1
    

    That’s just a transcription error.

    In any case, my new answer is 96686312646216567629137.

    I can confirm that it’s right via:

    ans=.96686312646216567629137x
    digits=. ((1+<.10^.ans)#10)#:ans
    primeSequence=. (10&#.)\.digits
    isPrime=. 1 p: primeSequence
    allPrime=. *./isPrime   NB. returns 1
    
  8. programmingpraxis said

    Your answer now correctly builds primes. But your final answer 96686312646216567629137 is smaller than the one given in the suggested solution. The final 21 digits are the same, but your prefix of 96 is shorter than the correct prefix of 357.

  9. Paul said

    An improved Python version. This version starts correctly from 2,3,5 and 7

    nums = [str(i) for i in range(1,10)]
    
    def extend(n):
        strn = str(n)
        newis = filter(is_prime, [int(num + strn) for num in nums])
        if newis:
            return max(extend(newi) for newi in newis)
        else:
            return n
    
    print max(extend(i) for i in [2,3,5,7])  
    
  10. Paul said

    My very first attempt to write something in Haskell. It works, but I still feel very uneasy.

    import Primee -- from ProgrammingPraxis
    
    nums = map show [1..9]
    
    extend :: Integer -> Integer
    extend n 
        | null pn   = n
        | otherwise = maximum (map (extend) pn) 
    	where 
    	    strn = show n
    	    pn = filter isPrime $ map (\x -> read (x ++ strn) :: Integer) nums
    
    main :: IO ()
    main = print $ maximum $ map extend [2,3,5,7]
    
  11. danaj said
    #!/usr/bin/env perl
    use warnings; use strict; use bigint;
    use Math::Prime::Util 'is_prime';
    use List::Util 'max';
    
    my @results;  # Holds all results seen
    my @current = grep { is_prime($_) } (0..9);
    
    do {
      push @results, @current;
      @current = grep { is_prime($_) }
                 map { my $n = $_; map { $_ . $n } 1..9 }
                 @current;
    } while scalar @current >= 1;
    my $max = max @results;
    
    # Assert every substring from the right is prime, just in case we did something wrong.
    do { die "substring '$_' of $max isn't prime!" unless is_prime($_) }
       for map { substr($max, -$_, $_) } 1 .. length($max);
    
    print "$max\n";
    
  12. JP said

    Here’s my take in Racket:
    Nested primes

    The basic algorithm is essentially the same as others here, although there is start to code that will eventually graph all of the different branches of primes. I’m curious if there’s any sort of structure to it.

    Speaking of which, is anyone aware of either a quicker method for generating these branches or a reason why they terminate?

  13. Vlad said

    Hello.I am practically a newbie in programming.I hope C/C++ code is also ok. I am a bit confused about the suggested solution as it does follow the example given in the exercise, but as far as my understanding goes that is not also the way to get the biggest prime number. i mean from 7 u can get 97, continuing with 797 and so on(as i got in my alghorithm).
    Here is my solution: http://codepad.org/b82CoYZR . As i said, im a begginer and im only looking to improve my skills so this code may not be the most elegant or best performance. I also doubt is correct, given your suggested solution, but i cant seem to get my mistake so am I curious about how i did. Looking forward to a reply. Thank you and i beg a pardon if my C code is not ?valid? here.

  14. Haskell. I’m not sure how closely I followed your method, but it seems to work so far. The laptop I’m using is rather decrepit so I shall have to wait a while to see if I get the correct solution.

    import Control.Monad (guard)
    import Data.Numbers.Primes (isPrime)

    largestBuildable :: Integral a => a
    largestBuildable = largest [2, 3, 5, 7]
    where largest xs
    | null xs’ = maximum xs
    | otherwise = largest xs’
    where xs’ = getBuildableGen xs

    getBuildableGen :: Integral a => [a] -> [a]
    getBuildableGen xs = do
    x <- xs
    y a -> a -> a
    addFront a b = b * 10 ^ ceiling ((log (fromIntegral a))/(log 10)) + a

  15. David said

    In Ruby…

    require_relative "miller-rabin"
    
    def extend(n)
        Enumerator.new do |iter|
            ('1'..'9').each do |digit|
                n2 = (digit + n.to_s).to_i
                if n2.prime? then
                    iter.yield n2
                    extend(n2).each {|prime|  iter.yield prime}
                end
            end
        end
    end
    
    puts extend("").max
    
    
    PS C:\Users\dave\Documents\dev\ruby> ruby .\nested_primes.rb
    357686312646216567629137
    
  16. Johann Hibschman said

    This version gives the right answer. It seems like I had to use extended precision in the “10^x” expression. In retrospect, that makes sense, but it leaves me unsatisfied with J’s handling of big numbers.

    nextPrimesWithScale=: 4 : '(#~ 1&p:) ,((>:i.9)*10x^x) +/ y'
    flooredLog10=: >.@(10&^.)
    nextPrimes=: 3 : '(flooredLog10 {.y) nextPrimesWithScale y'
    nextPrimesWithMax=: 3 : 0
      max=. {.y
      primes=. }.y
      newPrimes=. nextPrimes primes
      (>./max,newPrimes),newPrimes
    )
    
  17. [...] Question is from Programmingpraxis: [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 611 other followers

%d bloggers like this: