# Euler Problem 50

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

﻿This took a while to solve partly because I went on vacation and partly because I was being a stubborn bonehead.

I initially tried to solve for all possible starting positions. It worked but I soon discovered it would take days to solve. Wanting to avoid using brute force, I instead went about being a smart ass and used a complicated sifter technique. Needless to say it didn’t work very well.

So, I went back to my original algorithm (which works — see below) dropped the starting position to the first 10 rather than the first 500K. Voila: solved in 12 seconds.

import java.util.*;

public class Euler50
{
public static void main(String[] args)
{
Euler50 e = new Euler50();
System.out.format(“Problem: %s\n”, e.getClass().getName());
System.out.format(“Answer = %s\n”, e.Problem());
}
public String Problem ()
{
ArrayList<Integer> P = new ArrayList<Integer>();
P = makePrimes(1000000);
int maxTerms = 0, maxSum = 0, sum = 0, count = 0;
for (int p: P)
{
for (int i = 0; i < 10 ; i++)
{
count = 0;
sum = 0;
for (int n = i; P.get(n) < p/2; n++)
{
sum += P.get(n);
count++;
if (sum > p)
break;
if (sum == p)
{
if (count > maxTerms)
{
maxTerms = count;
maxSum = sum;
System.out.format(“sum:%d, terms:%d\n”, sum, count);
}
}
}
}
}
return String.valueOf(maxSum);
}
public ArrayList<Integer> makePrimes (int lim)
{
ArrayList<Integer> P = new ArrayList<Integer>();
boolean [] isPrime = new boolean [lim+1];
for (int i = 2; i < lim; i++)
isPrime[i] = true;
for (int p = 2; p*p < lim; p++)
if (isPrime[p] == true)
for (int m = p*p; m < lim; m = m+p)
if (m % p == 0)
isPrime[m] = false;
for (int i = 2; i < lim; i++)
if (isPrime[i])
return P;
}
}

# Euler Problem 49

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

﻿Nothing extrordinary here. I could have made the code tighter, but it still ran in 7 seconds.

import java.util.*;

public class Euler49
{
public static void main(String[] args)
{
Euler49 e = new Euler49();
System.out.format(“Problem: %s\n”, e.getClass().getName());
System.out.format(“Answer = %s\n”, e.Problem());
}
public String Problem ()
{
ArrayList<Integer> allP = new ArrayList<Integer>();
ArrayList<Integer> P4 = new ArrayList<Integer>();
allP = makePrimes (10000);
String S = “”;
for (int p: allP)
if (p > 1487 && Integer.toString(p).length() == 4)
A:for (int i: P4)
{
for (int n = 1000; n < (9999-i)/2; n++)
{
if (P4.contains(i+n))
if (isPerm(i,i+n))
if (P4.contains(i+n+n))
if (isPerm(i, i+n+n))
{
S += Integer.toString(i) + Integer.toString(i+n) + Integer.toString(i+n+n);
break A;
}
}
}
return String.valueOf(S);
}
public ArrayList<Integer> makePrimes (int lim)
{
ArrayList<Integer> P = new ArrayList<Integer>();
boolean [] isPrime = new boolean [lim+1];
for (int i = 2; i < lim; i++)
isPrime[i] = true;
for (int p = 2; p*p < lim; p++)
if (isPrime[p] == true)
for (int m = p*p; m < lim; m = m+p)
if (m % p == 0)
isPrime[m] = false;
for (int i = 2; i < lim; i++)
if (isPrime[i])
return P;
}
public boolean isPerm (int i1, int i2)
{
String S1 = Integer.toString(i1);
String S2 = Integer.toString(i2);
for (int n = 0; n <= 3; n++)
S2 = S2.replaceFirst(String.valueOf(S1.charAt(n)), “”);
if (S2.equals(“”))
return true;
else
return false;
}
}

# Euler Problem 48

The series, 1 1 + 2 2 + 3 3 + … + 10 10 = 10405071317.

Find the last ten digits of the series, 1 1 + 2 2 + 3 3 + … + 1000 1000 .

The ﻿BigInteger class makes this one a joke. I’m sure its gets harder going forward. So I won’t act too smug.

import java.math.*;

public class Euler48
{
public static void main(String[] args)
{
Euler48 e = new Euler48();
System.out.format(“Problem: %s\n”, e.getClass().getName());
System.out.format(“Answer = %s\n”, e.Problem());
}
public String Problem ()
{
BigInteger big = BigInteger.valueOf(0);
for (int i = 1; i <= 1000; i++)
return String.valueOf(big.toString().substring(big.toString().length()-10));
}
}

# Euler Problem 47

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 7
15 = 3 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2&sup2; 7 23
645 = 3 5 43
646 = 2 17 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

I liked this one because it uses two very important routines developed so far. Prime Number generation and Number Factorization. The trick for this one is after factoring a number, filter the set for Prime numbers BEFORE counting the residual factors.

This routine is also getting more complex. In the interest of speeding up the calculation, I moved the Prime ArrayList definition outside of the method so that its a class variable now. This way its only defined once, rather than hundreds of thousands of times.

import java.util.*;

public class Euler47
{
ArrayList<Integer> P = new ArrayList<Integer>();
public static void main(String[] args)
{
Euler47 e = new Euler47();
System.out.format(“Problem: %s\n”, e.getClass().getName());
System.out.format(“Answer = %s\n”, e.Problem());
}
public String Problem ()
{
ArrayList<Integer> F = new ArrayList<Integer>();
int start = 130000, limit = 140000;
int answer = 0, flag = 0, count = 4;
for (int i = start; i < limit; i++)
{
flag = 0;
for (int n = 0; n <= count-1; n++)
{
F = makeOnlyPrime(Factor(i+n), i+n);
if (F.size() == count)
flag++;
}
if (flag == count)
{
break;
}
}
}
public ArrayList<Integer> Factor (int num)
{
ArrayList<Integer> F = new ArrayList<Integer>();
for (int n = 2; n <= Math.ceil(Math.sqrt(num)); n++)
if (num % n == 0 && F.contains(n) == false)
{
if (F.contains(num/n) == false)
}
return F;
}
public ArrayList<Integer> Prime (int lim)
{
P.clear();
boolean [] isPrime = new boolean [lim+1];
for (int i = 2; i < lim; i++)
isPrime[i] = true;
for (int p = 2; p*p < lim; p++)
if (isPrime[p] == true)
for (int m = p*p; m < lim; m = m+p)
if (m % p == 0)
isPrime[m] = false;
for (int i = 2; i < lim; i++)
if (isPrime[i])
return P;
}
public ArrayList<Integer> makeOnlyPrime (ArrayList<Integer> F, int i)
{
ArrayList<Integer> N = new ArrayList<Integer>();
for (int f = 0; f <= F.size()-1; f++)
if (Prime ((int)(i/2)+1).contains(F.get(f)))
return N;
}
}

# Euler Problem 46

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2 1 2 15 = 7 + 2 2 2 21 = 3 + 2 3 2 25 = 7 + 2 3 2 27 = 19 + 2 2 2 33 = 31 + 2 1 2 It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Not too tricky. Need to notice that the prime number and the number squared are always less than the composite.

import java.util.*;

public class Euler46
{
public static void main(String[] args)
{
Euler46 e = new Euler46();
System.out.format(“Problem: %s\n”, e.getClass().getName());
System.out.format(“Answer = %s\n”, e.Problem());
}
public String Problem ()
{
ArrayList<Integer> C = new ArrayList<Integer>();
ArrayList<Integer> P = new ArrayList<Integer>();
ArrayList<Integer> T = new ArrayList<Integer>();
int n = 10000;
boolean [] isPrime = new boolean [n+1];
for (int i = 2; i < n; i++)
isPrime[i] = true;
for (int p = 2; p*p < n; p++)
if (isPrime[p] == true)
for (int m = p*p; m < n; m = m+p)
if (m % p == 0)
isPrime[m] = false;
for (int i = 2; i < n; i++)
if (isPrime[i])
else
if (i % 2 != 0)
boolean flag = true;
for (int i = 0; i <= C.size()-1; i++)
{
flag = true;
A: for (int p = 0; P.get(p) < C.get(i); p++)
for (int m = 1; m < Math.sqrt(C.get(i)); m++)
if ((P.get(p) + 2*m*m) == C.get(i))
{
flag = false;
System.out.format(“%d: %d + 2*%d^2\n”, C.get(i), P.get(p), m);
break A;
}
if (flag)
}
return String.valueOf(T.get(0));
}
}

According to Wiki, every integer greater than one is either a prime number or a composite number.

﻿

# Euler Problem 45

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

 Triangle T n =n(n+1)/2 1, 3, 6, 10, 15, … Pentagonal P n =n(3n 1)/2 1, 5, 12, 22, 35, … Hexagonal H n =n(2n 1) 1, 6, 15, 28, 45, …

It can be verified that T 285 = P 165 = H 143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

Flip each formula using the quadratic equation. Double check your calculations. Iterate over a few billion. Done.

public class Euler45
{
public static void main(String[] args)
{
Euler45 e = new Euler45();
System.out.format(“Problem: %s\n”, e.getClass().getName());
System.out.format(“Answer = %s\n”, e.Problem());
}
public String Problem ()
{
long next = 0;
for (long i = 1000000000L; i <= 2000000000L; i++)
if ((Math.sqrt(1+8*i)-1) % 2 == 0)
if ((Math.sqrt(1+24*i)+1) % 6 == 0)
if ((Math.sqrt(1+8*i)+1) % 4 == 0)
{
next = i;
break;
}
return String.valueOf(next);
}
}

﻿

# Euler Problem 44

Pentagonal numbers are generated by the formula, P n =n(3n 1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

It can be seen that P 4 + P 7 = 22 + 70 = 92 = P 8 . However, their difference, 70 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P j and P k , for which their sum and difference is pentagonal and D = |P k  P j | is minimised; what is the value of D?

It seems simple … and it is, providing you do two things.

1. Use the standard quadratic equation on P n =n(3n 1)/2 to flip it. This way you can go both ways when needed. Check out Pentagonal Numbers on Wiki.
2. ALWAYS CHECK YOUR FORMULAS! I spent days and many wrong submissions because one of my formulas was wrong..
public class Euler44
{
public static void main(String[] args)
{
Euler44 e = new Euler44();
System.out.format(“Problem: %s\n”, e.getClass().getName());
System.out.format(“Answer = %s\n”, e.Problem());
}
public String Problem ()
{
long max = Long.MAX_VALUE;
for (long j = 1; j <= 10000; j++)
for (long k = 1; k <= j; k++)
if (isPent(P(j)+P(k)) && isPent(P(j)-P(k)))
if (P(j)-P(k) < max)
max = P(j)-P(k);
return String.valueOf(max);
}
public boolean isPent (long n)
{
if ((Math.sqrt(1+24*n)+1) % 6 == 0)
return true;
return false;
}
public long P (long n)
{
return n*(3*n-1)/2;
}
}