Prime String

January 10, 2017

Today’s exercise is easy to describe, but has some tricky edge cases that make it hard to implement:

Given a string of the prime numbers appended sequentially — 2357111317192…. — and an index n, return the string of five digits beginning at index n. For instance, the five characters starting at index n = 50 are 03107. The first 61 characters of the prime string are shown below:

0         1         2         3         4         5         6
0123456789012345678901234567890123456789012345678901234567890

2357111317192329313741434753596167717379838997101103107109113

Your task is to write a program to find the substring of the string of all primes starting at the nth character. 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.

Pages: 1 2

7 Responses to “Prime String”

  1. Paul said

    In Python. primegen is a lazy prime generator.

    def prime_str(n):
        primes = primegen()
        res = ""
        while len(res) < 5:
            strp = str(next(primes))
            L = len(strp)
            if L >= n:
                res += strp[n:n+5]
            n = max(0, n-L)
        return res[:5]
    
  2. Jussi Piitulainen said

    Decoupling digit generation from slice selection, in Python.

    from itertools import islice
    
    def prime_digits():
        for p in primegen():
            yield from str(p)
    
    def prime_str(k, n):
        return ''.join(islice(prime_digits(), k, k + n))
    
  3. Globules said

    A Haskell version.

    import Math.NumberTheory.Primes.Sieve (primes)
    
    digits :: String
    digits = concatMap show primes
    
    fiveAt :: Int -> String
    fiveAt n = take 5 $ drop n digits
    
    main :: IO ()
    main = do
      putStrLn $ fiveAt 50
      putStrLn $ fiveAt 12345678
    
    $ ./primestr 
    03107
    24126
    
  4. Jussi Piitulainen said

    This is Julia 0.5, with its new generator expressions. I didn’t find an unbounded prime generator (one could be written) so I just fake it with a sufficiently large pool of primes, which is readily available. Julia’s iteration protocol is similar to but different from that of Python, ISWIM. In particular, the value of a generator expression does not itself have state.

    module Play
    
    using Primes
    pool = primes(3000)
    
    digits(source) = (c for p in source for c in string(p))
    
    function example(gen)
        println(join(take(drop(gen, 0), 3)))
        println(join(take(drop(gen, 3), 3)))
        println(join(take(drop(gen, 3), 0)))
    end
    
    example(digits(pool))
    # prints:
    # 235
    # 711
    #
    
    before = length(join(digits((p for p in pool if p < 2017))))
    present(gen) = println(join(take(drop(gen, before), 4)))
    
    present(digits(pool))
    # prints:
    # 2017
    
    end
    
  5. Jussi Piitulainen said

    (Re my Julia above, a nicer way to count the total number of digits in primes below 2017.)

    before = sum(length(string(p)) for p in pool if p < 2017)
    
  6. matthew said

    Here’s some JS using the new ES6 generators. This one only starts building up the string once the first required prime is reached, before that it just keep a character count for the primes seen. Uses a simple incremental sieve of Eratosthenes – not the most efficient, but does the job.

    "use strict"
    function primestring(n,m) {
        let len = 1, nextlen = 10, total = 0;
        let primegen = primes(), s = null;
        for (const p of primegen) {
            if (p >= nextlen) {
                nextlen *= 10; len++;
            }
            total += len;
            if (total > n) {
                s = String(p).substring(n-total+len,len);
                break;
            }
        }
        for (const p of primegen) {
            s += String(p);
            if (s.length >= m) {
                return s.substring(0,m);
            }
        }
    }
    
    function* primes() {
        let a = []; // 3,5,7,9,...
        let b = []; // new primes to be inserted
        const add = (n,p) => {
            if (!a[n]) a[n] = [];
            a[n].push(p);
        }
        yield 2;
        for (let i = 1, j = 0; ; i++) {
            if (i == b[j]) {
                add(i,b[j+1]);
                j += 2;
            }
            if (a[i]) {
                for (const p of a[i]) add(i+p,p);
            } else {
                b.push(2*i*(i+1),2*i+1);
                yield 2*i+1;
            }
        }
    }
    
    // Naive implementation for comparison
    function primestring0(n,m) {
        let s = "";
        for (const p of primes()) {
            s += p;
            if (s.length >= n+m) break;
        }
        return s.substring(n,n+m);
    }
    
    console.log(primestring(0,55));
    console.log(primestring(50,5));
    
    for (let i = 0; i < 100; i++) {
        for (let j = 0; j < 20; j++) {
            console.assert(primestring0(i,j) == primestring(i,j));
        }
    }
    
  7. Anhy said

    package prime.string;
    import static java.lang.System.out;
    import java.util.Scanner;
    public class PrimeString {
    public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);
    out.print(“Enter the index: “);
    int index = keyboard.nextInt();
    out.println();
    int a = 2;
    String b = “”;
    while(b.length() < index+5)
    {
    if(a % 2 != 0 && a % 3 != 0 && a % 5 != 0 && a % 7 != 0 || (a == 2 || a == 3 || a == 5 || a == 7))
    {
    b += a;
    }
    a++;
    }
    System.out.println(b.substring(index,index+5));
    }
    }

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

%d bloggers like this: