primechain.frink

Download or view primechain.frink in plain text format


// Program to find the largest number that is made up of the concatenation of
// unique n-digit prime numbers.
// For example, for 2-digit primes, the sequence 31, 11, 17, 79 becomes
// the number 31179.

start = now[]

digits = eval[input["Enter length of chain: ", 3]]

// Find limits of range
smallest = 1

for i = 1 to digits-1
   smallest = smallest * 10 + 1

largest = smallest * 9

leading = new dict

n = smallest
// Find prime numbers in this range
while n <= largest
{
   if isPrime[n]
   {
      ns = "$n"
      lead = substringLen[ns, 0, digits-1]

      if leading@lead
         leading@lead.pushFirst[[ns, false]]
      else
         leading@lead = [[ns, false]]
   }

   n = nextPrime[n]
}

sortedList = new array
            
stack = new array

greatest = 0

for [num, list] reverse[sort[leading, byColumn[0]]]
{
   c = 0
   for c = 0 to length[list]-1
   {
      list@c@1 = true           // Mark used
      n = list@c@0
      greatest = test[n, digits, stack, leading, greatest]
      list@c@1 = false
   }
}

// Recursive function to test numbers.
test[n, digits, stack, leading, greatest] :=
{
   stack.push[n]
   if (length[stack] > greatest)
   {
      greatest = length[stack]
      println["$stack\t($greatest)"]
   }

   n = substringLen[n, 1, digits-1]

   for i = 0 to length[leading@n]-1
   {
      if leading@n@i@1 == false
      {
         leading@n@i@1 = true        // Mark used
         greatest = test[leading@n@i@0, digits, stack, leading, greatest]
         leading@n@i@1 = false
      }
   }
   stack.pop[]
   return greatest
}


Download or view primechain.frink in plain text format

This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 19966 days, 7 hours, 32 minutes ago.