## Projecteuler.net – Problem 26 – Java

http://projecteuler.net/problem=26

I found this Wikipedia section to be invaluable for this problem. The algorithm forms the cyclic sequence using prime numbers.

```
public class Euler26 {

static int b = 10;		// number base

public static void main(String[] args) {

int longestLength = 0;
int longestNumber = 0;

for (int p = 7; p < 1000; p++) {

if (checkIfPrime(p)) {
StringBuilder cyclicNumber = new StringBuilder();
int r = 1;
int x, d;

// calculates the next digit of our cyclic number
// then appends it to our string
do {
x = r * b;
d = (int) Math.floor(x / p);
r = x % p;
cyclicNumber.append(d);
} while (r != 1);

// we are looking for the longest cyclic number
if (cyclicNumber.length() > longestLength) {
longestLength = cyclicNumber.length();
longestNumber = p;
}
}
}
System.out.println(longestNumber);
}

private static 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;
}

}
```

## r/dailyprogrammer – [Easy] Roll the Dies

This is my solution to a programming challenge found at reddit.com/r/dailyprogrammer. This problem can be found at Roll the Dies.

Josh

```
public class Easy {
public static void main(String[] args) {
for (int i : rollDice("4d6")) {		// example data
System.out.print(i + " ");
}
}

private static int[] rollDice(String s) {
String diceData[] = s.split("d");
int[] result = new int[Integer.parseInt(diceData[0])];
for (int i = 0; i < result.length; i++) {
result[i] = (int)(Math.random() * Integer.parseInt(diceData[1]) + 1);
}
return result;
}
}
```

## r/dailyprogrammer – [Easy] Longest Two-Character Sub-String

This is my solution to a programming challenge found at reddit.com/r/dailyprogrammer. This problem can be found at longest two character substring. My solution was to step through each position of the string and place whatever character that position holds into a temporary Set. A Set will only contain unique items so if I end up with more than two I know my substring holds more than two unique characters.

Josh

```
import java.util.HashSet;
import java.util.Set;

public class DailyProgrammer129 {

public static void main(String[] args) {
String s = args[0];
String longest = "";

for (int i = 0; i < s.length(); i++) {
Set<Character> tempSet = new HashSet<Character>();

for (int j = i; j < s.length(); j++) {

if (tempSet.size() <= 2 && s.substring(i,j+1).length() > longest.length()) {
longest = s.substring(i,j+1);
}
}
}
System.out.println(longest);
}
}
```

## Merge Sort Algorithm

A basic implementation of a merge sort algorithm.

Running a test file of 100000 randomly ordered integers through this algorithm takes about 4.54 seconds on my system. I will be using the same test file for comparison against other sorting algorithms.

Josh

```
/**
* A very basic Merge Sort class implemented from a pseudocode
* algorithm found on Wikipedia
*
* This class will only sort an int[].
*
* @author Joshua Weise
* @see http://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation
*/
public class MergeSort {

// array of numbers
private int[] data;

public MergeSort(int[] data) {
this.data = data;
}

/**
* starts the recursive mergeSort method
*/
public void sort() {
data = mergeSort(data);
}

/**
* Recursively splits the initial data array and calls
* the merge method to sort and recombine the data
* @param m		numbers to sort
* @return		new sorted array
*/
private int[] mergeSort(int[] m) {

if (m.length <= 1) { return m; }

int[] left = new int[m.length / 2];
int[] right = new int[m.length - left.length];
int middle = m.length / 2;

for (int i = 0; i < middle; i++) {
left[i] = m[i];
}

for (int i = 0; i < right.length; i++) {
right[i] = m[i + left.length];
}

left = mergeSort(left);
right = mergeSort(right);

return merge(left, right);
}

/**
* Merges two number arrays while also putting them in order
* @param left		numbers to sort and merge
* @param right		numbers to sort and merge
* @return			new sorted and merged array
*/
private int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int x = 0;

while (left.length > 0 || right.length > 0) {
if (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[x] = left[0];
x++;
left = shiftLeft(left);
} else {
result[x] = right[0];
x++;
right = shiftLeft(right);
}
} else if (left.length > 0) {
result[x] = left[0];
x++;
left = shiftLeft(left);
} else if (right.length > 0) {
result[x] = right[0];
x++;
right = shiftLeft(right);
}
}
return result;
}

/**
* removes the leftmost array item by returning a new array
* with everything but that item
* @param x		array of numbers
* @return		new array of numbers
*/
private int[] shiftLeft(int[] x) {
int[] y = new int[x.length - 1];
for (int i = 1; i < x.length; i++) {
y[i-1] = x[i];
}
return y;
}

// return data
public int[] getData() {
return data;
}

}
```

## Selection Sort Algorithm

A simple example of the selection sort algorithm.

Running a test file of 100000 randomly ordered integers through this algorithm takes about 4.72 seconds on my system. I will be using the same test file for comparison against other sorting algorithms.

Josh

```
/**
* A very basic Selection Sort class.
*
* This class will only sort an int[].
*
* @author Joshua Weise
*/
public class SelectionSort {

// array of numbers
private int[] data;

public SelectionSort(int[] data) {
this.data = data;
}

// selection sort data
public void sort() {
// move right through our array
for (int i = 0; i < data.length; i++) {
// assign the first location as our assumed smallest number
int smallest = i;
// loop through the rest of array checking for smaller numbers
for (int j = 1+i; j < data.length; j++) {
if (data[j] < data[smallest]) {
smallest = j;
}
}
// swap number locations
swap(i, smallest);
}
}

// swaps data in place at locations a and b in the array
private void swap(int a, int b) {
int z = data[a];
data[a] = data[b];
data[b] = z;
}

// return data
public int[] getData() {
return data;
}
}
```

## Insertion Sort Algorithm

A Java example of the insertion sort algorithm.

Running a test file of 100000 randomly ordered integers through this algorithm takes about 1.53 seconds on my system. I will be using the same test file for comparison against other sorting algorithms.

Josh

```
/**
* A very basic Insertion Sort class.
*
* This class will only sort an int[].
*
* @author Joshua Weise
*/
public class InsertionSort {

// array of numbers
private int[] data;

public InsertionSort(int[] data) {
this.data = data;
}

// Insertion sort data
public void sort() {
for (int i = 1; i < data.length; i++) {
// the value we are moving left
int y = data[i];
// the array location we could move our value into
int z = i;
// loop until we find the farthest left we can move our value into
// moving the other values out of the way right as we go
while (z > 0 && y < data[z-1]) {
data[z] = data[z - 1] ;
z--;
}
// put our original value into its new position
data[z] = y;
}
}

// return data
public int[] getData() {
return data;
}

}
```

## Bubble Sort Algorithm

A basic example of the bubble sort algorithm in Java.

Running a test file of 100000 randomly ordered integers through this algorithm takes about 15.8 seconds on my system. I will be using the same test file for comparison against other sorting algorithms.

Josh

```
/**
* A very basic Bubble Sort class.
*
* Sorting algorithm uses a common optimization to avoid
* resorting already sorted items at the end of the array.
*
* This class will only sort an int[].
*
* @author Joshua Weise
*/
public class BubbleSort {

// array of numbers
private int[] data;

public BubbleSort(int[] data) {
this.data = data;
}

// bubble sort data
public void sort() {
for (int i = data.length; i >= 0; i--) {
for (int j = 0; j < i-1; j++) {
if (data[j] > data[j+1]) {
swap(j, j+1);
}
}
}
}

// return data
public int[] getData() {
return data;
}

// swaps data in place at locations a and b in the array
private void swap(int a, int b) {
int z = data[a];
data[a] = data[b];
data[b] = z;
}
}
```

## Projecteuler.net – Problem 63 – Java

http://projecteuler.net/problem=63

This one seemed straight forward and doable with very little code. I like that. Simply solve the math then compare the length of the result to power value.

Josh

```
import java.math.BigInteger;

public class Euler63 {

/**
* The 5-digit number, 16807=7^5, is also a fifth power.
* Similarly, the 9-digit number, 134217728=8^9, is a ninth power.
* How many n-digit positive integers exist which are also an nth power?
*/
public static void main(String[] args) {

int numberOfSolutions = 0;

for (Integer number = 1; number <= 100; number++) {
for (int power = 1; power <= 100; power++) {

BigInteger value = new BigInteger(number.toString()).pow(power);
int length = value.toString().length();

if (power == length) {
numberOfSolutions++;
}
}
}

System.out.println(numberOfSolutions);

}

}
```

## 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
}
}

// 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) {

// reduce the range the loop searches based on the prime factor that is found
num = num / i;
i = 1;
maximum = num / 2;
}
}

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)) {
}

}

return primes;
}

}
```

## Projecteuler.net – Problem 44 – Java

http://projecteuler.net/problem=44

I populated a Set with a range of Pentagonal numbers that I thought might contain the result. Then I check if the Sums and Differences are already in the Set. This method is not optimum as it will end up checking pairs twice due to how I iterated through the Set.

Josh

```import java.util.HashSet;
import java.util.Set;

public class Euler44 {

public static void main(String[] args) {

boolean eD;		// .contains result for Set
boolean eS;		// .contains result for Set

// build and Set of Pentagonal numbers
Set<Long> p = new HashSet<Long>();

for (int i = 1; i < 5000; i++) {
Long x = new Long((i * ((3 * i) - 1) / 2));
}

for (Long element1 : p) {
for (Long element2 : p) {

Long elementSum = new Long(element1 + element2);
Long elementDifference = new Long(Math.abs(element2 - element1));

eD = p.contains(elementDifference);
eS = p.contains(elementSum);

if (eD && eS) {
System.out.println(elementDifference);

}
}
}

}

}
```