import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; /** * Class for generating a chain of Collatz sequences. * <p> * 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). * <p> * 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<Long> getChainOfCollatzSequences( long numberOfCollatzSequences ) { long startOfCollatzSequence = 1L; Set<Long> chainAsSet = new HashSet<Long>(); List<Long> chainAsList = new ArrayList<Long>(); for ( int collatzSequenceNumber = 1; collatzSequenceNumber <= numberOfCollatzSequences ; collatzSequenceNumber++ ) { List<Long> collatzSeq = getCollatzSequence( startOfCollatzSequence ); chainAsSet.addAll(collatzSeq); chainAsList.addAll(collatzSeq); startOfCollatzSequence = getNextMinimumLongNotInSet( chainAsSet, startOfCollatzSequence ); } return chainAsList; } private List<Long> getCollatzSequence( long startOfCollatzSequence ) { List<Long> collatzSequence = new ArrayList<Long>(); 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<Long> 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<Long> chainOfCollatzSequences = chainOfCollatzSequencesGenerator.getChainOfCollatzSequences( numberOfCollatzSequences ); System.out.println("Chain of Collatz Sequences (number of sequences is "+numberOfCollatzSequences+"): "+ chainOfCollatzSequences ); } }