import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* Class for generating a chain of Collatz sequences.
*
* The first Collatz sequence in the chain starts with 1.
* Each Collatz sequence after the first sequence starts with the minimum positive integer that does not appear in the previous Collatz sequences.
* Each Collatz sequence in the chain ends with 1 (assuming the Collatz conjecture is true).
*
* The following are the first 20 elements of the chain of Collatz sequences; note that each Collatz sequence in the chain is terminated with a semicolon:
* 1; 2, 1; 3, 10, 5, 16, 8, 4, 2, 1, 6, 3, 10, 5, 16, 8, 4, 2, 1;
*
* @author Robert C. Lyons
*/
public class ChainOfCollatzSequencesGenerator {
private static final boolean DEBUG = false;
/**
* Return a chain of Collatz sequences.
*
* @param numberOfCollatzSequences the number of Collatz sequences in the chain.
* @return a chain of Collatz sequences.
*/
public List getChainOfCollatzSequences( long numberOfCollatzSequences ) {
long startOfCollatzSequence = 1L;
Set chainAsSet = new HashSet();
List chainAsList = new ArrayList();
for ( int collatzSequenceNumber = 1; collatzSequenceNumber <= numberOfCollatzSequences ; collatzSequenceNumber++ ) {
List collatzSeq = getCollatzSequence( startOfCollatzSequence );
chainAsSet.addAll(collatzSeq);
chainAsList.addAll(collatzSeq);
startOfCollatzSequence = getNextMinimumLongNotInSet( chainAsSet, startOfCollatzSequence );
}
return chainAsList;
}
private List getCollatzSequence( long startOfCollatzSequence ) {
List collatzSequence = new ArrayList();
long nextElement = startOfCollatzSequence;
collatzSequence.add( nextElement );
while ( nextElement != 1L ) {
if ( nextElement % 2L == 0L ) {
nextElement = nextElement / 2L;
} else {
nextElement = nextElement * 3L + 1L;
}
collatzSequence.add( nextElement );
}
if ( DEBUG ) System.out.println("collatzSequence="+collatzSequence);
return collatzSequence;
}
private long getNextMinimumLongNotInSet( Set setOfLongs, long previousMinLongNotInSet ) {
long nextMinimumLongNotInSet = previousMinLongNotInSet + 1L;
while ( setOfLongs.contains( nextMinimumLongNotInSet ) ) {
nextMinimumLongNotInSet++;
}
if ( DEBUG ) System.out.println("nextMinimumLongNotInSet="+nextMinimumLongNotInSet);
return nextMinimumLongNotInSet;
}
public static final void main(String[] args) {
long numberOfCollatzSequences = Long.parseLong( args[0] );
ChainOfCollatzSequencesGenerator chainOfCollatzSequencesGenerator = new ChainOfCollatzSequencesGenerator();
List chainOfCollatzSequences = chainOfCollatzSequencesGenerator.getChainOfCollatzSequences( numberOfCollatzSequences );
System.out.println("Chain of Collatz Sequences (number of sequences is "+numberOfCollatzSequences+"): "+ chainOfCollatzSequences );
}
}