Раз-два простые

Все эти десятичные числа из единиц и двоек просты:

   1: 2
   2: 11
   3: 211
   4: 2111
   5: 12211
   6: 111121
   7: 1111211
   8: 11221211
   9: 111112121
  10: 1111111121
  11: 11111121121
  12: 111111211111
  13: 1111111121221
  14: 11111111112221
  15: 111111112111121
  16: 1111111112122111
  17: 11111111111112121
  18: 111111111111112111
  19: 1111111111111111111
  20: 11111111111111212121

До сих пор не доказано, что для любого количества цифр n ≥ 1 существует n-значное простое число, состоящее только из единиц и двоек, но, видимо, это так. Более того, на странице соответствующей последовательности A036229 тов. Чай Ва Ву напейсал соответствующую функцию для поиска минимального из таких чисел, в которую нам осталось только добавить ещё один цикл.

Можно было бы работать и с библиотекой gmpy2

from gmpy2 import is_prime

, но непонятно, где это сделать онлайн. Показанный ниже код выполнял вот здесь, до границы поиска 400-500 разрядов вместо 100 он, в принципе, должен дотянуть.

from sympy import isprime

def show_oeis36229(wanted):
    for ndig in list(range(1, wanted)):
        k, i, j = (10**ndig - 1) // 9, 2**ndig - 1, 0
        while j <= i:
            candidate = k + int(bin(j)[2:])
            if isprime(candidate):
                pstr = str(candidate)
                print(f'{ndig:4}: {pstr}')
                break
            j += 1

show_oeis36229(101)

Это задача из списка задач на простые числа

21.05.2023, 02:06 [163 просмотра]