Как посчитать количество чисел-палиндромов в большом промежутке?

Question

Нужно посчитать количество палиндромов в промежутке от a до b. Решается легко, если промежуток - до 10000 Но, как решить задачу, где нужно найти количество палиндромов в промежутке от 1.026.376 до 10**15 (квадриллиона)? И желательно за быстрое время. Перебором слишком долго, может есть какие-то формулы, где можно просто числа брать, не проверяя каждое на палиндромность?

Answer 1

Я предлагаю от 1.026.376 до следующего разряда 10 000 000 проверить перебором, а далее поразрядно 10^7 .. 10^8 ..10^n по формуле: если n четное, то количество палиндромов 10^(n//2)-10^(n//2-1), если n не четное, то количество палиндромов 10^((n+1)//2)-10^((n+1)//2-1)

например:
10^2 количество палиндромов 9
10^3 количество палиндромов 90
10^4 количество палиндромов 90
10^5 количество палиндромов 900
10^6 количество палиндромов 900
 

s=0
for i in range(1026376,10**7):
    sss=str(i)
    if sss==sss[::-1]:
        s+=1
print('->',s)
for n in range(8,15+1): # Ошибочно начинал с 10^7
    if n%2==0:
        s+=10**(n//2)-10**(n//2-1)
    else:
        s+=10**((n+1)//2)-10**((n+1)//2-1)

print(s)

-> 8973
109997973

Answer 2

f(k) - число чисел-палиндромов из k разрядов. Тогда

f(2k) = 9·10^k-1;
f(2k + 1) = 9·10^k.

Девятка отвечает за цифры старшего разряда - от единицы до девяти. Степень десятки - за остальные разряды из старшей половины числа.

g(k) - число чисел-палиндромов из не более чем k разрядов. Тогда

g(2k) = 2·10^k - 2;
g(2k + 1) = 11·10^k - 2.

Доказывается по индукции (g(n + 1) = g(n) + f(n + 1)).

h(n) - число чисел-палиндромов не более n. Я покажу на примере как его можно сосчитать быстро. Пусть n = 345678. Разобъём все палиндромы не более n на группы:

     ? - палиндромы длины один. Их f(1)
    ?? - палиндромы длины два. Их f(2)
   ??? - палиндромы длины три. Их f(3)
  ???? - палиндромы длины четыре. Их f(4)
 ????? - палиндромы длины пять. Их f(5)

1????1 - таких палиндромов 100 (все палиндромные цифровые строки длины 4)
2????2 - тоже самое (первые цифры от единицы до 3 - 1)

30??03 - таких палиндромов 10 (все палиндромные цифровые строки длины 2)
31??13 - тоже самое
32??23 - тоже самое
33??33 - тоже самое (вторые цифры от нуля до 4 - 1)

340043 - такой палиндром один (все палиндромные цифровые строки длины 0)
341143 - тоже самое
342243 - тоже самое
343343 - тоже самое
344443 - тоже самое (третьи цифры от нуля до 5 - 1)

345543 - такой палиндром один, но надо отдельно проверить
         что он не больше n

Получается такая программа:

def ps_count(k):
    """ число палиндромных строк длины k """
    return 10 ** ((k + 1) // 2)


def p_count_10p(k):
    """ число чисел-палиндромов не более k разрядов """
    return 10 ** ((k + 1) // 2) + 10 ** (k // 2) - 2


def p_count(n):
    """ число чисел-палиндромов не более n """

    if n == 0:
        return 0

    digits = tuple(map(int, str(n)))
    m = len(digits)

    # короткие палиндромы
    c = p_count_10p(m - 1)

    for i in range((m + 1) // 2):
        # палиндромы вида ABC????CBA
        c += (digits[i] - (0 if i > 0 else 1)) * ps_count(m - 2 * (i + 1))

    if digits[:m // 2 - 1::-1] <= digits[(m + 1) // 2:]:
        # палиндром вида ABCDEEDCBA
        c += 1

    return c


def main():
    n1, n2 = map(int, input().split())
    # число чисел-палиндромов диапазоне [n1, n2]
    print(p_count(n2) - p_count(n1 - 1))


main()

echo 1026376 1_000_000_000_000_000  | python pcount.py
109997973

Программа работает за логарифмическое время. Её можно переделать для расчёта суммы палиндромов. Первоначально так и было, но вопрос изменился и ответ упростился.

БЛОГ НА HUSL

Как посчитать количество чисел-палиндромов в большом промежутке?

Ответы (2 шт):