Prime String

January 10, 2017

My first version of the program prebuilt the prime string to some large length and simply indexed into that string. That worked, but I was dissatisfied because it required a large amount of storage, and inevitably fails when a too-large n is requested. But it did make a nice way to check results of my finished algorithm, so it wasn’t a total loss.

My second version of the program tried to calculate the lengths of the primes and work out where exactly the index occurred within the sequence of prime numbers, but that didn’t work; more precisely, I never convinced myself that I had found the last bug in the program. The problem is that there are lots of edge cases where the requested index doesn’t point to the beginning of a prime, and there are other edge cases where the next five characters spill across a boundary from one prime length to another, and my code kept getting more and more complicated to handle those edge cases, so eventually I threw away that version.

The third version of the program keeps a sliding window on the string, generating primes as necessary. If the window is too small, it is extended. If the index of the first character in the window is less than the target index, the window slides one character to the right. When the window finally reaches the target index, there are guaranteed to be enough characters to form a result, so the function returns. There are no special edge cases at the beginning of the prime string, or when the number of digits in the current prime is greater than its predecessor, or when the target index points to the middle of a prime, or anything else:

(define (prime-substring n)
  (let ((ps (primegen)))
    (let loop ((i 0) (str ""))
      (cond ((string (ps)))))
            ((< i n)
              (loop (+ i 1) (substring str 1 (string-length str))))
            (else (substring str 0 5))))))

Here are some examples:

> (prime-substring 50)
"03107"
> (prime-substring 1000)
"98719"
> (prime-substring 10000)
"02192"

We used the prime generator primegen from a previous exercise. You can run the program at http://ideone.com/DaU4pX.

Advertisements

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: