Сумма-палиндром

Сумма-палиндром

Хотите готовиться со мной к ЕГЭ?
Пишите:  ydkras@mail.ru
Немного обо мне.

 

Рассмотрим следующую задачу для подготовки к ЕГЭ с сайта К.Полякова (задача 25, вариант 1):

 

(№ 4410) (Л. Шастин) Среди чисел, больших 520000, найти такие, сумма всех делителей которых, не считая единицы и самого числа, образует число-палиндром (например, число 1221: если его «перевернуть», получается то же самое число). Вывести первые пять чисел, удовлетворяющих вышеописанному условию, справа от каждого числа вывести его максимальный делитель.  

 

Получить список делителей числа можно с помощью функции divisors, описанной в статье "Разложение на множители и простые числа".

Как определить, является ли число палиндромом? Наверно, самый короткий способ - преобразовать число в символьную строку и проверить строку "на палиндромность". Самое простое - сравнить исходную строку с "перевернутой задом наперед". В Питоне получить из некой строки s перевернутую строку очень просто: s[::-1]. (Если в операции получения подстроки записаны три параметра, то третий параметр - это шаг. С его помощью можно получить, например, каждый второй или каждый третий символ, а можно и перевернуть строку.)

Для пишущих на других языках приведу функцию, которая проверяет, является ли строка палиндромом (эта функция легоко реализуется на паскале или С++). Создадим пустую строку и будем присоединять к её началу поочередно символы исходной строки. Мы получим строку "задом наперед". Если она равна исходной строке, то наша строка - палиндром.

Вот текст функции

def palindrom(s):
    t=''
    for i in range(len(s)): t=s[i]+t  
    return s==t 

Основная программа очень проста. По очереди раскладываем числа 520001, 520002 и т.д. на множители, вычисляем их сумму. Если сумма - палиндром, то печатаем число и его наибольший множитель. В переменной k мы подсчитываем количество найденных чисел. Когда будет найдено пять чисел, цикл завершается.

Для преобразования числа в символьную строку используем функцию Питона str, для суммирования элементов массива - функцию sum и для поиска максимального элемента массива - функцию max.

Приведем полный текст программы:

def divisors(n):
    d=[]
    k=2
    while k*k <= n:
        if n%k == 0:
            d.append(k)
            k2 = n//k
            if k2 > k: d.append(k2)
        k += 1
    return d

n=520001
k=0
while k < 5:
    d = divisors(n)
    if len(d) > 0 and str(sum(d)) == str(sum(d))[::-1]:
        print(n,max(d))
        k += 1
    n += 1

Условие len(d) > 0 нужно для того, чтобы убедиться, что массив делителей не пустой. (Если массив пустой, то функция sum выдаст 0, он будет преобразован в строку "0", которая, очевидно, является палиндромом, а при попытке найти в пустом массиве наибольший элемент возникнет ошибка выполнения. Проверка len(d)> 0 исключает подобные неприятности.)

Результат выполнения программы следующий:

520211 16781
520993 47363
521653 47423
521947 16837
522077 22699

Он совпадает с приведенным на сайте ответом.

Программа выполняется очень быстро (десятые доли секунды).

(c) Ю.Д.Красильников, 2021-2022 г.