def prime_factorization(n):
    if n == 1:
        return []
    factors = []
    divisor = 2
    while n > 1:
        while n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        divisor += 1 if divisor == 2 else 2
        if divisor * divisor > n:
            if n > 1:
                factors.append(n)
            break
    return factors

def find_identical_sequence(sequence1, sequence2):
    numbers1 = [x for x in sequence1 if x != '-']
    numbers2 = [x for x in sequence2 if x != '-']
    sequence = []
    for n1, n2 in zip(numbers1, numbers2):
        if n1 == n2:
            sequence.append(n1)
        else:
            return len(sequence), sequence, n1, n2
    return len(sequence), sequence, None, None

def generate_complete_sequences(k):
    n = 2 ** k
    sequences_summary = {}
    all_sequences = {}
    
    # Generate sequences 1;k
    for position in range(k):
        current_sequence = []
        for num in range(1, n + 1):
            factors = prime_factorization(num)
            current_sequence.append(str(factors[position]) if position < len(factors) else '-')
        all_sequences[f"1;{position+1}"] = current_sequence
        if position == 0:
            sequences_summary["1;1"] = current_sequence
    
    # Generate other sequences
    for i in range(1, k):
        # First generate all sequences A;i;k for level i
        for j in range(i+1, k + 1):
            shifted_sequence = ['-'] * n
            source_sequence = sequences_summary[f"{i};{i}"] if i > 1 else all_sequences["1;1"]
            for pos in range(n):
                if source_sequence[pos] != '-':
                    new_pos = (pos + 1) * (2 ** (j-i))
                    if new_pos <= n:
                        shifted_sequence[new_pos - 1] = source_sequence[pos]
            all_sequences[f"A;{i};{j}"] = shifted_sequence
        
        # Then generate sequences i+1;k by comparison
        for j in range(i+1, k + 1):
            compared_sequence = ['-'] * n
            base_sequence = all_sequences[f"1;{j}"] if i == 1 else all_sequences[f"{i};{j}"]
            sequence_a = all_sequences[f"A;{i};{j}"]
            for m in range(n):
                if base_sequence[m] != sequence_a[m] and base_sequence[m] != '-':
                    compared_sequence[m] = base_sequence[m]
            all_sequences[f"{i+1};{j}"] = compared_sequence
            if j == i+1:
                sequences_summary[f"{i+1};{i+1}"] = compared_sequence
    
    print(f"\nSummary of sequences i;i for k = {k} (n = 2^{k} = {n}):")
    for i in range(1, k + 1):
        key = f"{i};{i}"
        if key in sequences_summary:
            numbers = [x for x in sequences_summary[key] if x != '-']
            print(f"Sequence {key}: {', '.join(numbers)}")
    
    # Analyze similarities
    longest_sequence = 0
    longest_sequences = None
    longest_sequence_terms = None
    longest_difference = None
    
    keys = sorted([k for k in sequences_summary.keys() if k.split(';')[0] not in ('A')])
    for i in range(len(keys)-1):
        key1 = keys[i]
        key2 = keys[i+1]
        length, sequence, val1, val2 = find_identical_sequence(
            sequences_summary[key1],
            sequences_summary[key2]
        )
        if length > longest_sequence:
            longest_sequence = length
            longest_sequences = (key1, key2)
            longest_sequence_terms = sequence
            longest_difference = (val1, val2)
    
    if longest_sequences:
        print("\n" + "="*50)
        print("LONGEST IDENTICAL SEQUENCE FOUND:")
        print(f"Between Sequence {longest_sequences[0]} and Sequence {longest_sequences[1]}")
        print(f"Length: {longest_sequence} terms")
        print(f"Sequence: {', '.join(longest_sequence_terms)}")
        if longest_difference[0] and longest_difference[1]:
            print(f"First difference: {longest_difference[0]} ≠ {longest_difference[1]}")
        print("="*50)

def main():
    while True:
        try:
            k = int(input("Enter the value of k (n will be equal to 2^k): "))
            if k <= 0:
                print("Please enter a positive number.")
                continue
            break
        except ValueError:
            print("Please enter a valid number.")
    
    generate_complete_sequences(k)

if __name__ == "__main__":
    main()