## Problem:

In a triangular array of positive and negative integers, we wish to find a sub-triangle such that the sum of the numbers it contains is the smallest possible.

In the example below, it can be easily verified that the marked triangle satisfies this condition having a sum of [−]42.

We wish to make such a triangular array with one thousand rows, so we generate 500500 pseudo-random numbers sk in the range [±]219, using a type of random number generator (known as a Linear Congruential Generator) as follows:

t := 0
for k = 1 up to k = 500500:
t := (615949*t + 797807) modulo 220
sk := t[−]219

Thus: s1 = 273519, s2 = [−]153582, s3 = 450905 etc

Our triangular array is then formed using the pseudo-random numbers thus:

s1
s2 s3
s4 s5 s6
s7 s8 s9 s10
...

Sub-triangles can start at any element of the array and extend down as far as we like (taking-in the two elements directly below it from the next row, the three elements directly below from the row after that, and so on).
The "sum of a sub-triangle" is defined as the sum of all the elements it contains.
Find the smallest possible sub-triangle sum.

997651

## Code:The solution may include methods that will be found here: Library.java .

public interface EulerSolution{public String run();}
/*  * Solution to Project Euler problem 50 * By Nayuki Minase *  * http://nayuki.eigenstate.org/page/project-euler-solutions * https://github.com/nayuki/Project-Euler-solutions */public final class p050 implements EulerSolution {		public static void main(String[] args) {		System.out.println(new p050().run());	}			private static final int LIMIT = Library.pow(10, 6);			public String run() {		boolean[] isPrime = Library.listPrimality(LIMIT);		int[] primes = Library.listPrimes(LIMIT);				long maxSum = 0;		int maxRun = -1;		for (int i = 0; i < primes.length; i++) {  // For each index of a starting prime number			int sum = 0;			for (int j = i; j < primes.length; j++) {  // For each end index (inclusive)				sum += primes[j];				if (sum > LIMIT)					break;				else if (j - i > maxRun && sum > maxSum && isPrime[sum]) {					maxSum = sum;					maxRun = j - i;				}			}		}		return Long.toString(maxSum);	}	}

## Follow Me

If you like our content, feel free to follow me to stay updated.

## Subscribe

Enter your email address:

We hate spam as much as you do.

## Upload Material

Got an exam, project, tutorial video, exercise, solutions, unsolved problem, question, solution manual? We are open to any coding material. Why not upload?
Copyright © 2012 - 2014 Java Problems  --  About  --  Attribution  --  Privacy Policy  --  Terms of Use  --  Contact