Подсчитайте количество пар из двух чисел, меньших или равных N, так чтобы сумма цифр чисел пары была простой

Question

Учитывая число N, подсчитайте все пары (X, Y) так, чтобы сумма из цифр X и Y была простой. Условия следующие.

• 1 <= N <= 10 ^ 50 </li>
• 0 <= X, Y <= N </li>
• (X, Y) и (Y, X) - одна и та же пара.

Я мог бы подумать о приближении грубой силы. В котором мне нужно поставить два цикла в диапазоне от 1 до N и вычислить сумму цифр для каждой пары x и y и проверить, является ли ее простым или нет. Но это не оптимальное решение, так как N имеет диапазон 10 ^ 50.

Answer 1

Я попробовал это сделать - мне понадобилось несколько попыток, чтобы понять проблему. Я хочу написать то, что я узнал, прежде чем сдаться и перейти к чему-то более простому!

Во-первых, я переделал решение @ shiva, которое дает правильный результат быстрее:

import sys
from functools import lru_cache

def sum_of_digits(number):
    summation = 0

    while number > 0:
        summation += number % 10
        number //= 10

    return summation

@lru_cache()
def is_prime(number):
    if number < 2:
        return False

    if number % 2 == 0:
        return number == 2

    divisor = 3

    while divisor * divisor <= number:
        if number % divisor == 0:
            return False
        divisor += 2

    return True

maximum = int(sys.argv[1])

count = 0

for i in range(maximum + 1):
    sum_i = sum_of_digits(i)

    for j in range(i, maximum + 1):
        if is_prime(sum_i + sum_of_digits(j)):
            count += 1

print(count)

Я использую это в качестве эталона ниже по скорости и точности.

Число необходимых простых чисел тривиально, даже для 10 ^ 50, и может / должно быть вычислено заранее. Количество генерируемых цифр также относительно невелико и может быть сохранено / хешировано. Мое решение хэширует все возможные суммы цифр от 0 до 10 ^ N, сохраняя количество раз, когда каждая сумма генерируется как значение. Затем он выполняет пару вложенных циклов над цифровыми суммами (ключами), и если сумма этих сумм является простым числом, он добавляет к количеству произведение количества способов, которыми может быть вычислена каждая сумма (т.е. умножает значения).

import sys
from math import ceil
from collections import defaultdict

VERBOSE = False

def sum_of_digits(number):
    summation = 0

    while number:
        summation += number % 10
        number //= 10

    return summation

def sieve_primes(n): 
    sieve = [False, False] + [True] * (n - 1)

    divisor = 2

    while divisor * divisor <= n: 
        if sieve[divisor]: 
            for i in range(divisor * divisor, n + 1, divisor): 
                sieve[i] = False
        divisor += 1

    return [number for number in range(2, n + 1) if sieve[number]]

power = int(sys.argv[1])  # testing up to 10 ** power

maximum_sum_of_digits = 18 * power
primes_subset = sieve_primes(maximum_sum_of_digits)

sums_of_digits = defaultdict(int)
for i in range(10 ** power + 1):
    sums_of_digits[sum_of_digits(i)] += 1

if VERBOSE:
    print('maximum sum of digits:', maximum_sum_of_digits)
    print('maximum prime:', primes_subset[-1])
    print('number of primes:', len(primes_subset))
    print('digit sums cached', len(sums_of_digits))

primes_subset = set(primes_subset)

count = 0

for i in sums_of_digits:
    sum_i = sums_of_digits[i]

    for j in sums_of_digits:
        if i + j in primes_subset:
            count += sum_i * sums_of_digits[j]

print(ceil((count + 2) / 2))  # hack to help adjust between duples and no duples count; sigh

(Включите флаг VERBOSE, чтобы увидеть больше информации о проблеме.)

К сожалению, это учитывает как (X, Y), так и (Y, X), вопреки спецификации проблемы, поэтому в конце кода есть приблизительный хак для исправления, чтобы исправить это. (Пожалуйста, предложите точное исправление!) Я называю свой результат приблизительным, но обычно он недооценивает только на 1 или 2. В отличие от кода @ shiva, этот аргумент принимает степень 10 в качестве аргумента, поскольку его цель - увидеть, насколько близко к 10 ^ 50 можно получить.

Был бы рад увидеть результат для N = 10 ^ 50 (или хотя бы 10 ^ 8) - MBo

        @Shiva reworked            My Attempt
          exact    secs        approx    secs
10^1         24    0.03            24    0.03
10^2       1544    0.04          1544    0.04
10^3     125030    0.49        125029    0.04
10^4   12396120   51.98      12396119    0.05
10^5 1186605815 6223.28    1186605813    0.14
10^6                     113305753201    1.15
10^7                   11465095351914   12.36
10^8                 1120740901676507  137.37
10^9               105887235290733264 1626.87

@ Обновленное решение Шивы бесполезно выше 10 ^ 4, а мои болота ниже 10 ^ 8. Таким образом, достижение 10 ^ 50 займет другой подход. Я надеюсь, что часть этого кода и анализа помогут в этих усилиях.

Answer 2

Попробуйте этот код Python и отладки:

def sumofdigits(num):
  sum=0
  while num>0:
    sum+=num%10
    num=num//10
  return sum
def isprime(num):
  if num==0:
    return False
  i = 2
  while i<num:
    if num%i==0:
      return False
    i+=1
  return True
number = int(input("Enter number:"))
for i in range(0,number+1):
  for j in range(i,number+1):
    if isprime(sumofdigits(i)+sumofdigits(j)):
      print(i,j);

Пример вывода: