Concatenated 2-digit primes

First, note that the last digit of a prime number greater than 5 must be one of 1, 3, 7, or 9. (If it's 0, 2, 4, 6, or 8, then it's divisible by 2; if it's 0 or 5, then it's divisible by 5. Since the number is greater than 5, they can't be 2 or 5 themselves, so they have a nontrivial divisor and thus not prime.) This means, except for the first digit, all the digits are 1, 3, 7, or 9.

Construct a directed graph with vertices 1, 3, 7, 9, and arcs from $i$ to $j$ indicating that the two-digit number $\overline{ij}$ is a prime number. (That is, the arcs are $(1, 1), (1, 3), (1, 7), (1, 9), (3, 1), (3, 7), (7, 1), (7, 3), (7, 9), (9, 7)$ .) Now we can interpret our number as a trail (walk that doesn't repeat an arc) on this graph: if the number is $\overline{d_0 d_1 d_2 \ldots d_k}$ , then $d_1, d_2, \ldots, d_k$ is a trail, because we need each of $(d_1, d_2), (d_2, d_3), \ldots, (d_{k-1}, d_k)$ to be arcs on the graph, and none of them may repeat.

There are 10 arcs in the graph, so $k-1 \le 10$ , or $k \le 11$ , giving a 12-digit number (the first digit $d_0$ has index 0). Can this be achieved?

It turns out that we can. To arrive at this result, we can first notice that if we want $k-1 = 10$ , then we need a path that traverses all the arcs; that is, an Eulerian trail. Luckily, this is possible: the in-degree and the out-degree of all vertices are equal, except 1 where the out-degree is larger by 1, and 9 where the in-degree is larger by 1, thus there is an Eulerian trail. All such trails will start from 1 (the one with larger out-degree) and end at 9 (the one with larger in-degree). One such example that can be found by hand is 1-1-3-1-7-1-9-7-3-7-9. This will give $d_1 = 1$ , so we can pick $d_0 = 4$ (6 also works), giving the number 411317197379, proving that $k-1 = 10$ is achievable. There are other trails and other choices of $d_0$ ; any of them works, because we only need to show existence.

We know Eulerian trails exist on this graph, and that they start at 1 and end at 9. Thus $d_1 = 1, d_{11} = 9$ . To obtain the largest possible number, we need to maximize $d_0$ ; among those with largest $d_0$ , we need to maximize $d_2$ ; among those with largest $d_2$ , we need to maximize $d_3$ , and so on. In other words, we greedily select the largest possible digit, but making sure that we can still complete the trail.

• $d_0$ is maximized by choosing 6. 9 and 8 don't work because 91 and 81 are not primes. 7 doesn't work because that would mean we use the arc $(7, 1)$ for $(d_0, d_1)$ , but we need to save it for later.
• $d_1$ is already set as 1.
• $d_2$ is maximized by choosing 9.
• $d_3$ is maximized by choosing 7; the only arc going out from 9 is to 7, so this is actually forced.
• $d_4$ is maximized by choosing 3. 9 doesn't work, since we'll be stuck; among the other outgoing arcs of 7, the next largest choice is to 3.
• $d_5$ is maximized by choosing 7, the largest available arc.
• $d_6$ is maximized by choosing 1. Again, 9 doesn't work, and 3 has been used.
• $d_7$ is maximized by choosing 3. 9 is already used, and 7 will leave the arcs $(1,1), (1,3), (3,1)$ unused.
• $d_8$ is maximized by choosing 1, because it's forced.
• $d_9$ is maximized by choosing 1; we still can't go to 7 yet (otherwise $(1,1)$ is unused).
• $d_{10}$ is maximized by choosing 7, because it's forced.
• $d_{11}$ is already set as 9.

That gives the number 619737131179 , which is our answer.

Each digit of the number after the first is $1, 3, 7, 9$ that means that the list of 2-digit primes after the first one is $11, 13,17,19,31,37,71,73,79,97$ . The number can be at most $12$ digits long. Making the list of the mentioned above $10$ prime numbers and comparing the number of occurrences of digits $1, 3, 7, 9$ one can conclude that the largest number is $619737131179$ , which is also a prime number.

Note: This question is taken from University of Waterloo Mathematics Contest.

Just a plain bash method in Objective-C :

Seeing that the primes must be in order, we create an array with 9 arrays inside holding all primes sorted by starting digit. Using recurrence the program sorts through these and generates every unique combination then just picks the largest. Because arrays are pointer, bear in mind that when copying arrays of arrays, making a deep copy is the only way to avoid pointing to the same memory location from the "copy".

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

NSMutableArray *firstNumber ;    //arrays storing arrays of primes by tens digit
NSMutableArray *overallStorage ;    //all possible combos of primes

int main(...{
    //initiate + allocate global var
    overallStorage = [NSMutableArray new] ;
    firstNumber = [NSMutableArray new] ;

    NSMutableArray *primes = [[NSMutableArray alloc] initWithObjects:@(11), ... , nil] ;
    for(int i = 0 ; i < 9 ; i += 1) [firstNumber addObject:[NSMutableArray new]] ;

    //sort primes by 10s digit
    for(NSNumber *prime in primes) [[firstNumber objectAtIndex:[prime integerValue]/10 - 1] addObject:prime] ;
    for(NSNumber *prime in primes){
        NSMutableArray *copyOfPrimes = [NSKeyedUnarchiver unarchiveObjectWithData: [NSKeyedArchiver archivedDataWithRootObject:firstNumber]];
        copyOfPrimes = removeNumber(copyOfPrimes, [prime integerValue]) ;
        reccurence(copyOfPrimes, [prime unsignedLongLongValue]) ;
    }
    NSNumber *largest = [[NSNumber alloc] initWithUnsignedLongLong:0] ;
    for(NSNumber *number in overallStorage) if([number isGreaterThan:largest]) largest = number ;
    NSLog(@"%llu",[largest unsignedLongLongValue]) ;
return 0 ;
}

void reccurence(NSMutableArray* array, unsigned long long number){
    int end = (int)(number - 10*(number/10)) ;
    end -= 1 ;  //to accomodate arrays starting at 0
    NSUInteger value ;
    for(NSNumber *junk in [array objectAtIndex:end]){
        value = [junk integerValue] ;
        NSMutableArray *arrayCopy = [NSKeyedUnarchiver unarchiveObjectWithData: [NSKeyedArchiver archivedDataWithRootObject:array]] ;    //deep copy
        reccurence(removeNumber(arrayCopy, value), 10*number + (value - 10*(value/10))) ;
    }
    if([[array objectAtIndex:end] count] == 0) [overallStorage addObject:[NSNumber numberWithUnsignedLongLong:number]] ;
}

NSMutableArray *removeNumber(NSMutableArray *array, NSUInteger number){
    for(NSMutableArray* junk in array) [junk removeObject:[NSNumber numberWithInteger:number]] ;
    return array ; 
} 

Solution in python 3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

"Concatenated 2-digit primes"
primes = [11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
graphs = {}
ariane = []
maxpath = 0
def initgraph():
    for p in primes:
            graphs[p] = [q for q in primes if p%10 == q//10]

def godeep(x):
    global maxpath, graphs
    ariane.append(x)
    maxpath = max(maxpath, val(ariane))
    for y in graphs[x]:
        if not y in ariane:
            godeep(y)

    x = ariane.pop()

def val(a):
    res = a[0]//10
    for p in a:
        res = res*10 + p%10
    return res

def solve():
    global maxpath
    initgraph()
    for p in primes:
        godeep(p)
    return maxpath

print(solve())

Output

1

619737131179