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

}