Повторения в массиве

Question

Выполняю задания с Проекта Эйлера, задание под номером 29.
Вопрос звучит:

Сколько различных членов имеет последовательность a**b для 2 ≤ a ≤ 100 и 2 ≤ b ≤ 100?

Я построил алгоритм с помощью цикла while, однако обнаружил повторения чисел в массиве.

Мой код:

def func():
   new_list = []
   a = 2
   b = 2
   while (2 <= a <= 100) and (2 <= b <=100):
      new_list.append(a**b)
      b += 1
      if b == 101:
         b = 2
         a += 1

   new = sorted(new_list)
   return new

print(func())

В чем заключается моя ошибка, и как устранить данные повторения чисел в массиве?

Answer 1

Ваша ошибка в том, что вы учитываете все элементы, включая дубликаты.

Например число 4096 является результатом следующих операций:

In [52]: 2**12
Out[52]: 4096

In [53]: 4**6
Out[53]: 4096

In [54]: 8**4
Out[54]: 4096

In [55]: 16**3
Out[55]: 4096

In [56]: 64**2
Out[56]: 4096

всего таких дубликатов:

In [29]: len(list(a**b for a in range(2, 101) for b in range(2, 101))) - len(set(a**b for a in range(2, 101) for b in range(2, 101)))
Out[29]: 618

---

Наивная, без попыток оптимизации, реализация (вычислительная сложность: O(n^2)):

res = len(set(a**b for a in range(2, 101) for b in range(2, 101)))
print(res)
# 9183

встроенный тип - множество (set) гарантирует уникальность элементов и сам удалит все дубликаты.