Projecteuler.net – Problem 46 – Java

http://projecteuler.net/problem=46

Lots of code follows. Not as slim as it might have been if I did it in a procedural way. But I’m trying to make and reuse as much code as possible for later problems.

What I’ve done is generate composite numbers, get all the primes that are in that number, then solve the equation with those numbers and check is my result is a whole number. If there are no whole numbers for a particular odd composite number, then I’ve found an instance where Goldbach’s conjecture no longer holds true.

One thing to keep in mind. When I solved the equation in the way I wanted, I ended up have to divide by square roots. Precision becomes an issue if you don’t simplify the equation. Just remember that sqrt(18) / sqrt(2) simplies to sqrt(18 / 2), or sqrt(9). If you do the former, no matter how precise you try to be, (think BigDecimal with a massive number of precision digits) you will not get 3 as a result.

Josh

This is my main class.

import java.util.ArrayList;

public class Euler46 {

	public static void main(String[] args) {
		
		ArrayList<Long> primes;
		Prime p = new Prime();
		Composite c = new Composite();		
	
		for (int i = 3; i < 10000; i=i+2) {
			c.setNumber(i);
			p.setNumber(i);
			primes = p.getPrimes();
					
			if (c.isComposite()) {
				
				ArrayList<Double> x = new ArrayList<Double>();
				for (long factor : primes) {

					double n = Math.sqrt(((p.getNumber() - factor) / 2));
					//System.out.println(n);
					if (n%1 == 0) {				
						// add found values to list
						x.add(n);
					}
				}
				
				// if our list is empty, we found a value that Goldbach's
				// conjecture fails at.
				boolean y = x.isEmpty();
				if (y) {
					System.out.println(c.getNumber());
					// break out once we find the first result
					break;
				}
			}
				
		}

	}

}

This class contains a method that checks if a number is composite. It didn’t need to be a class object, but I’m looking for future flexibility.

import java.util.ArrayList;

/*
 * A composite number is a positive integer that has at least one positive 
 * divisor other than one or itself. In other words a composite number is 
 * any positive integer greater than one that is not a prime number.
 */

public class Composite {

	private long number;
	
	public void setNumber(long number) {
		this.number = number;
	}
	
	public long getNumber() {
		return number;
	}
	
	public boolean isComposite() {
		
		// composite numbers must be positive and greater than one
		if (number <= 1) {
			return false;
		}
		
		// check if number can be factorized
		// if true, number is composite and not prime
		Prime p = new Prime(number);
		ArrayList<Long> factors = new ArrayList<Long>();
		factors = p.getPrimeFactors();
		
		if (factors.isEmpty()) {
			return false;
		}
		
		return true;
	}
	
}

And this contains some Prime related stuff I’ve used before. There may be some unused stuff in here for this particular problem. I didn’t look too closely.

import java.util.ArrayList;

public class Prime {

	private long number;
	
	public Prime() { }
	
	public Prime(long number) {
		this.number = number;
	}
	
	// set number
	public void setNumber(long number) {
		this.number = number;
	}
	
	// get number
	public long getNumber() {
		return number;
	}

	/***
	 * Prime Factorization of positive long int greater than 1.
	 * Ex: The Prime Factorization of 8 returns [2, 2, 2]. (2 * 2 * 2 = 8 )
	 * @return  ArrayList<Long>
	 */
	public ArrayList<Long> getPrimeFactors() {
		long num = number;
		ArrayList<Long> prime_factors = new ArrayList<Long>();
 
		// define a maximum search range, result is truncated
		long maximum = (num / 2);

		if (checkIfPrime(num)) { return prime_factors; }
		
		for (long i = 2; i <= maximum; ++i) {
			if (num%i == 0) {
				prime_factors.add(i);
 
				// reduce the range the loop searches based on the prime factor that is found
				num = num / i;
				i = 1;
				maximum = num / 2;
			}
		}
		
		prime_factors.add(num);
		
		return prime_factors;
	}
	
	private boolean checkIfPrime(Long num) {
		
		if (num == 1) { return false; }

		for (long i = 2; i <= Math.sqrt(num); i++) {
			if (num % i == 0) {
				return false;
			}
		}
		
		return true;
	}
	
	
	public ArrayList<Long> getPrimes() {
		ArrayList<Long> primes = new ArrayList<Long>();
		
		// define a maximum search range, result is truncated				
		for (long i = 2; i < number; i++) {
			
			if (checkIfPrime(i)) {
				primes.add(i);
			}
						
		}
		
		return primes;
	}

}
This entry was posted in Java, Project Euler. Bookmark the permalink.

Leave a Reply