Matematyka.pl

Witam
Autor zadał do napisania program, który wyszuka - w podanym zakresie - pierwsze tak zwane buddy pairs. Zakres zawiera się w przedziale typu long long.
Buddy pairs zostały zdefiniowane w ten sposób
załóżmy, że \(\displaystyle{ s(n)}\) jest sumą dzielników właściwych liczby \(\displaystyle{ n }\). Znajdź taką parę liczb \(\displaystyle{ (n,m)}\), że \(\displaystyle{ s(m) = n+1}\) i \(\displaystyle{ s(n) = m+1.}\)
Taką parą liczb są na przykład 48 i 75 lub 9504 20735.
Wiem, że istnieją liczby zaprzyjaźnione które wyszukuje się wzorem Eulera, ale chyba nie ma zastosowania do tego przypadku. Jeśli ktoś może pomóc to proszę o dokładne wyjaśnienie teorii jaka leży u podstaw tego zadania i jakieś linki albo książkę gdzie można to doczytać.

gawiellus pisze: 4 gru 2020, o 22:08
załóżmy, że \(\displaystyle{ s(n)}\) jest sumą dzielników właściwych liczby \(\displaystyle{ n }\). Znajdź taką parę liczb \(\displaystyle{ (n,m)}\), że \(\displaystyle{ s(m) = n+1}\) i \(\displaystyle{ s(n) = m+1.}\)
Taką parą liczb są na przykład 48 i 75 lub 9504 20735.

Powinno być raczej tak: \(\displaystyle{ s(n) =s(m)=n+ m+1}\) skoro: \(\displaystyle{ s(48) =s(75)=124=48+75+1}\) oraz \(\displaystyle{ s(9504) =s(20735)=30240=9504+20735+1}\)
Przykładowy algorytm:
Program będzie dla kolejnych n z zadanego przedziału:
1. wyliczał \(\displaystyle{ s(n) }\)
2. wyliczał \(\displaystyle{ m=s(n)-n-1 }\)
3. wyliczał \(\displaystyle{ s(m) }\)
4. sprawdzał czy \(\displaystyle{ s(n)=s(m) }\)
5. wypisywał pary \(\displaystyle{ n,m }\) gdy warunek 4. jest spełniony
Między 2 i 3 można wstawić warunek \(\displaystyle{ m>n}\)
Pozostaje kwestia wyliczania sumy dzielników. Istnienie funkcji liczącej sumę dzielników w używanym języku programowania banalizuje problem.

Próbowałem robić to według podanego algorytmu. Dla większych liczb program nie przechodzi testów z powodu przekroczenia czasu wykonania.
Co prawda sumę dzielników wyliczałem do ograniczenia \(\displaystyle{ n/2}\). Wiem, że można ograniczyć do \(\displaystyle{ \sqrt{n}}\), ale mimo wszystko nawet powyższe ograniczenie nie pomoże bo maksymalna liczba typu long long to \(\displaystyle{ 18 446 744 073 709 551 615 }\), co przy ograniczeniu do \(\displaystyle{ \sqrt{n}}\) daje \(\displaystyle{ 4 294 967 296 }\) obiegów pętli. Wydaje mi się, że musi być jakiś prostszy sposób