problem29.py

# How many distinct terms are in the sequence generated by ab for 2 ? a ? 100 and 2 ? b ? 100?

if __name__ == "__main__":
    max = 100
    table = [[0 for x in range(max-1)] for x in range(max-1)]
    row = 0
    while row < max-1:
        if table[row][0] != 0:
            row += 1
            continue
        else:
            value = row + 2
            for i, x in enumerate(table[row]):
                table[row][i] = (value, i+2)
            next_pow = 2
            next_row = value * value - 2
            # populate rows of powers of value
            while next_row <= max-2:
                for i, x in enumerate(table[next_row]):
                    table[next_row][i] = (value, (i+2) * next_pow)
                next_pow += 1
                next_row = (next_row+2) * value - 2
            row += 1

    distinct = set()
    for r in table:
        for v in r:
            distinct.add(v)
    #for r in table:
    #    print(r)
    #print(distinct)
    print(len(distinct))