All Articles

Largest Integer Consisting of Unique Triple Primes

If the number was 94199 the triples would be 941, 419, 199. The goal was to find the largest number where all of the triples are prime where no triple prime is repeated. This problem was posed as a challenge. I decided to use Prolog since I like to have fun with logic programming.

?- solution.
Largest value is 9419919379773971911373313179

The code:

% Largest integer where all triples are prime.
% Author: Rusty Conover

    N is Y*Y,
    N =< X,
    X mod Y =:= 0.

    Y < X,
    Y1 is Y+1,

    Y is 2, X > 1, \+divisible(X,Y).

%% If the current value is prime, store it along with the first two digits
%% and the last two digits of the value, so we can reference them later.
prime_builder(Current, End) :-
    -> Larger is truncate(Current / 10),
       Ending is Current mod 100,
       assert(is_prime(Current, Larger, Ending))
    ; true),
    Next is Current+1,
    (Next =< End
    -> prime_builder(Next, End)
    ; true).

%% Clear the database, and rebuild our list of primes.
build_primes :-
    retractall(is_prime(_, _, _)),
    prime_builder(100, 999).

%% Build the result by picking the next prime number matching the ending of the
%% current prime.
chain_primes(Number, Used, Result) :-
    Start is Number mod 1000,
    is_prime(Start, _, End),
    is_prime(New, End, _),
    \+ member(New, Used),
    NewNumber is (Number * 10) + (New mod 10),
    append([New], Used, NewUsed),
    (chain_primes(NewNumber, NewUsed, Result)
    ; Result = NewNumber).

%% For each starting prime number, attempt to chain the longest value
chain_primes(Result) :-
    is_prime(Start, _, _),
    chain_primes(Start, [Start], Result).

solution :-
    findall(Value, chain_primes(Value), AllResults),
    sort(AllResults, SortedResults),
    last(SortedResults, LargestValue),
    format('Largest value is ~w~n', [LargestValue]).