Find largest number with all contiguous triples being unique primes

Question

Find largest number with all contiguous triples being unique primes

If the digits of the answer are

pqrstu...xyz

then pqr, qrs, rst ... etc are all unique primes.

As expected, extra points for speed, conciseness, and other good things.

I can run Python/C/C++/Java on my comp and will try to update the answers with the running time of a provided solution on my computer.

This is not a question I need answered - this is a question you might enjoy answering as it is not an obviously easy problem.

ps : For the skeptics, this is not my homework. I enjoyed solving it, and thought people here like solving problems.

This was a pre-interview question (one needed to solve this to get a real interview) similar to the google question - find first 10 digit prime in expansion of e - the answer is the email address.

---

Solution times on my machine... (~ avg of 5 runs)

• Skizz : ~0.01s (A86 Assembly)
• John Kugelman : 1.886s (Python - new longest function)
• Mark : 0.351s (Java)
• cfern : 0.11s (F#)
• VinyleEm : 0.03s (C++)

Answer 1

I believe the best answer is 9419919379773971911373313179.

Edit: slightly more concise -- appropriate sorting returns the largest number first. Note the reversal shouldn't count against the computation time, if I were less lazy I'd just store the list in that format to begin with...

edit: slightly faster (now <800ms on my thinkpad edge)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class primefinder {

    public static void getNextPrime(Integer p, Set<Integer> list,
            List<Integer> best) {
        for (Integer pr : links.get(p)) {
            if (list.contains(pr)) {
                continue;
            }
            list.add(pr);
            getNextPrime(pr, list, best);
            list.remove(pr);
        }
        if (list.size() > best.size()) {
            best.clear();
            best.addAll(list);
        }
    }

    public static void main(String[] args) {
        Collections.reverse(primes);

        long start = System.currentTimeMillis();
        links = new LinkedHashMap<Integer,List<Integer>>();
        for(Integer p : primes){
            int last2 = p % 100;
            List<Integer> valid = new ArrayList<Integer>();
            links.put(p, valid);
            for(Integer q : primes){
                if (q / 10 == last2) {
                    valid.add(q);
                }
            }
        }

        List<Integer> best = new ArrayList<Integer>();
        Set<Integer> temp = new LinkedHashSet<Integer>();
        for (Integer p : primes) {
            temp.add(p);
            getNextPrime(p, temp, best);
            temp.clear();
        }
        System.out.println("Time: " + (System.currentTimeMillis() - start));

        // print stuff
        System.out.printf("%03d", best.get(0));
        for (int i = 1; i < best.size(); i++) {
            System.out.print((best.get(i) % 10));
        }
        System.out.print("\n");
    }

    static Map<Integer,List<Integer>> links;
    static List<Integer> primes = Arrays.asList(11, 13, 17, 19, 23, 29, 31, 37,
            41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
            109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
            181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
            257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331,
            337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
            419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487,
            491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
            587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653,
            659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
            751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
            839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929,
            937, 941, 947, 953, 967, 971, 977, 983, 991, 997);

}

Answer 2

Nice problem!

Apparently my approach is the same as already seen in here except for one handy observation. Since each triple has to be prime, each triple can only end in 1,3,7 or 9. Using this observation, I first generate the tail of the number within a reduced search space of prime triples containing only 1,3,7 or 9.

When I get the longest (and numerically highest) possible 1379-only tail, I look for the two highest digits that can be legally added to the front of the tail.

I coded it in F#, execution time on a 2.33Ghz Core2Duo around 0.39 seconds.

let isprime n = [2..(int (sqrt (float n)))] |> List.forall (fun d -> n%d > 0)

//seeds: all prime triples containing only 1,3,7 or 9
let seeds = 
    [for a in [1;3;7;9] do
        for b in [1;3;7;9] do
            let ab = 10*a+b
            for c in [1;3;7;9] do
                let p = 10*ab+c
                if isprime p then yield p]
    |> Set.ofList                

//find the longest prime chain starting with a 3-digit seed
let longestchain seed =
    let remaining = Set.remove seed seeds

    let rec aux remaining str n =
        seq {
            let cands = remaining |> Set.filter (fun rm -> n%100 = rm/10)
            if cands.IsEmpty then 
                yield str
            else
                for c in cands do 
                    yield! aux (remaining.Remove c) (str + (string (c%10))) c
        }

    aux remaining (string seed) seed
    |> Seq.groupBy (fun s -> s.Length)
    |> Seq.maxBy fst
    |> snd
    |> Seq.max

//a chain is valid if all consecutive 3-tuples inside a string are distinct
let valid (s:string) = 
    (Seq.windowed 3 s 
     |> Seq.distinct 
     |> Seq.length) = (s.Length - 2)    

//All expansions of a string s (xyz....) with a 3-digit prime p (abx)
//such that abx and bxy are prime
let augment (s:string) =
    let x = int (s.Substring(0,1))
    let y = int (s.Substring(1,1))

    {997 .. -2 .. 2}
    |> Seq.filter isprime
    |> Seq.filter (fun p -> p%10 = x)
    |> Seq.filter (fun p -> isprime (10 * (p%100) + y))
    |> Seq.map (fun p -> (string (p/10)) + s)
    |> Seq.filter valid //only valid chains allowed
    |> Seq.head //return highest legal augmentation

// Find the largest number where each consecutive triplet is a prime number
let find() =
    seeds 
    |> Seq.map longestchain //expand each seed to the longest chain possible
    |> Seq.groupBy (fun s -> s.Length) 
    |> Seq.maxBy fst //find the chains of longest length possible
    |> snd 
    |> Seq.map augment //add two valid numbers in front of the each max-chain
    |> Seq.max

let test() = find() = "9419919379773971911373313179" //should return true

Answer 3

Golfscript - 28 chars

9419919379773971911373313179

Maybe the code-golf tag should not be on this question :)

Answer 4

16 Bit Assembler

Source: ~1500

Executable: 313

Time: ~0s (I haven't got any way to time it)

    mov ax,ds
    add ax,1000h
    mov es,ax
    mov ds,ax
    mov dx,640ah
    xor di,di
    xor ax,ax
    mov bx,ax
 l1:stosw
    inc ax
    cmp ax,1000
    jb l1
    mov ax,4
 l2:mov di,ax
    cmp w[di],bx
    je l4
    add di,ax
 l3:mov w[di],bx
    add di,ax
    cmp di,2000
    jb l3
 l4:add ax,2
    cmp ax,2000
    jb l2
    mov si,200
    mov di,2000
    xor cx,cx
    mov bx,100
 l5:mov [di+4],bx
    inc bx
    lodsw
    or ax,ax
    jz l6
    mov [si-2],di
    div dl
    add ah,30h
    mov [di+2],ah
    aam
    or al,al
    jz l6
    or ah,ah
    jz l6
    add ax,3030h
    mov [di],ah
    mov [di+1],al
    mov b [di+3],0
    add di,32
    inc cx
 l6:cmp si,2000
    jb l5
    mov bp,cx
    mov di,2000
 l7:mov ax,[di+4]
    div dh
    mov al,ah
    mul dl
    mov ch,1
 l8:push ax
    add al,ch
    adc ah,0
    mov si,ax
    shl si,1
    mov ax,[si]
    or ax,ax
    jz l9
    mov bl,[di+3]
    mov bh,0
    add bx,bx
    mov [di+bx+6],ax
    mov w [di+bx+8],0
    inc b [di+3]
 l9:pop ax
    add ch,2
    cmp ch,10
    jl l8
    add di,32
    mov ch,0
    loop l7
    mov si,2000
    mov cx,bp
    mov b[100],0
l10:cmp b[si+3],0
    je l11
    mov di,0
    mov ax,5
    stosw
    mov ax,[si]
    stosw
    mov al,[si+2]
    stosb
    or b[si+3],128
    push cx
    call l12
    pop cx
    and b[si+3],127
l11:add si,32
    loop l10
    mov dx,102
    mov ah,9
    int 21h    
    ret
l12:lea di,[si+6]
l14:mov bx,[di]
    or bx,bx
    jz ret
    test b[bx+3],128
    jnz l13
    pusha
    xor di,di
    add di,[di]
    mov al,[bx+2]
    stosb
    inc w[0]
    xor si,si
    mov di,100
    mov cx,[si]
    repz cmpsb
    jle l15
    xor si,si
    mov di,100
    mov cx,[si]
    rep movsb
    mov al,'$'
    stosb
l15:mov si,bx
    or b[si+3],128
    call l12
    and b[si+3],127
    dec w [0]
    popa
l13:add di,2
    jmp l14

Note: Assembled using the A86 assembler, tested with WinXP command prompt.

Answer 5

My first post here. Kind of looks like a typical Project Euler question. Same answer as Kugelman. In C++ in 0.101 sec. I guess C++ is much faster.

bool ps[1024];

int seen[1024],maxLen=0;

#define SET(x,a) memset(x,a,sizeof x)

char bf[10035];
string res;

void recurse(int x){
int find = false,prv = 10*(bf[x-2]-'0')+(bf[x-1]-'0');
for(int i=9;i>=1;i-=2)if(ps[prv*10+i] && !seen[prv*10+i]){
    seen[prv*10+i] = true;
    bf[x] = '0'+i;
    find = true;
    recurse(x+1);
    seen[prv*10+i] = false;
}
if(!find){
    if(x > maxLen){
        res = string(bf,bf+x);
        maxLen = x;
    }
    return;
}
return;
}

int main(){
res = "";
SET(ps,true);
ps[0] = ps[1] = false;
for(int i=2;i*i <= 1024;i++)
    if(ps[i])
        for(int j=i*i;j<1024;j+=i)
            ps[j]=false;
for(int i=999;i>100;i-=2)
    if(ps[i]){
        sprintf(bf,"%d",i);
        SET(seen,false);
        recurse(3);
    }
cout << res << endl;
return 0;
}

Answer 6

@Rajan - nice question.

Here is a perl solution to the problem. It isn't optimal, but it is easy to understand (hopefully).

#!/usr/bin/perl

use Data::Dumper;

sub test {
        my $x = shift;

        my $s0 = substr($x, 0, 3);
        my $sn = substr($x, 1);

        return ($sn =~ m/$s0/) ? 0 : 1;
}

sub isPrime {
        my $x = shift;

        for (my $p = 3; $p < $x; $p += 2) {
                if (($x % $p) == 0) {
                        return 0;
                }
        }

        return 1;
}

sub genPrimes {
        my %bad = ( 0 => 1,
                    2 => 1,
                    4 => 1,
                    5 => 1,
                    6 => 1,
                    8 => 1 );

        for (my $x = 101; $x < 1000; $x += 2) {
                if (isPrime($x)) {
                        my $d2 = int($x / 100);
                        my $d1 = int($x / 10) % 10;
                        my $d0 = ($x % 10);

                        if ((!exists $bad{$d2}) && (!exists $bad{$d1}) && (!exists $bad{$d0})) {
                                push @primes, $x;
                        }
                }
        }
}

my %prefix = ();

sub genPrefixes {

        for (my $i = 0; $i < scalar @primes; $i++) {
                my $x = $primes[$i];
                my $y = substr($x, 0, 1);
                my $z = substr($x, 1, 2);

                if (!exists $prefix{$z}) {
                        $prefix{$z} = "";
                }

                $prefix{$z} = $prefix{$z} . $y;
        }

        return 0;
}

#
# Step 1: generate the 3 digit primes and the prefixes for the leading 2 digits.
#
genPrimes();
genPrefixes();

#
# Step 2: loop over the current set of primes to see if we can prepend a digit and keep it prime.
#
my $lo_bound = -1;
my $hi_bound = -1;
my $count = 1;
my $best = 0;

while ($count != 0) {
        $count = 0;
        $lo_bound = $hi_bound + 1;
        $hi_bound = (scalar @primes) - 1;
        $best     = $primes[$lo_bound];

        for (my $i = $lo_bound; $i <= $hi_bound; $i++) {
                my $base = $primes[$i];
                my $x = substr($base, 0, 2);
                my $y = $prefix{$x};

                for (my $j = 0; $j < length($y); $j++) {
                        my $digit = substr($y, $j, 1);
                        my $guess = $digit . $base;
                        if (test($guess) != 0) {
                                $count++;
                                push @primes, $guess;
                                if ($guess gt $best) {
                                        $best = $guess;
                                }
                        }
                }
        }
}

#
# Step 3: loop over the current set of primes to see if we can prepend a digit
#         and an even digit and keep it prime.  If we find one, then check to
#         see if it is the best one.
#
for (my $i = $lo_bound; $i <= $hi_bound; $i++) {
        my $base = $primes[$i];

        for (my $j = 9; $j > 0; $j--) {
                for (my $k = 9; $k >= 0; $k--) {
                        if ((($k%2) == 0) || ($k == 5)) {
                                my $guess = $j . $k . $base;
                                my $try1 = substr($guess, 0, 3);
                                my $try2 = substr($guess, 1, 3);
                                if (isPrime($try1) && isPrime($try2) && test($guess)) {
                                        if ((length($guess) > length($best)) || ($guess gt $best)) {
                                                $best = $guess;
                                        }
                                }
                        }
                }
        }
}

#
# Step 4: Print out the answer.
#
printf "%s\n", $best;