Niech oznacza wartość największej liczby w ciągu zaś niech oznacza największy iloczyn pary liczb w ciągu

Rozwiązanie
Zacznijmy od rozwiązania, w którym obliczamy iloczyn każdej z par elementów ciągu Następnie zliczamy te iloczyny, które są kwadratami liczb naturalnych. Załóżmy, że chcemy sprawdzić, czy jest kwadratem. W tym celu przeglądamy kwadraty kolejnych liczb naturalnych: Jeśli trafimy na to odpowiedź jest pozytywna. Jeśli trafimy na liczbę większą niż wtedy przerywamy działanie i odpowiedź jest negatywna. Tym sposobem rozważymy kwadratów. Zatem rozwiązanie działa w czasie

Rozwiązanie
Przyspieszmy sprawdzanie, czy jest kwadratem. Zaaplikujmy algorytm wyszukiwania binarnego na ciągu kwadratów: Algorytmy wykona operacji. Całe rozwiązanie działa w czasie

Szkic rozwiązania optymalnego
Zauważmy, że w rozkładzie na czynniki pierwsze kwadratu liczby naturalnej każdy czynnik pierwszy występuje parzyście wiele razy. Zatem iloczyn dwóch liczb jest kwadratem, jeśli zbiory czynników pierwszych występujących nieparzyście wiele razy w rozkładzie obu liczb są takie same. Niech więc gdzie oznacza iloczyn czynników pierwszych, które występują nieparzyście wiele razy w rozkładzie Innymi słowy, to podzielone przez swój największy dzielnik będący kwadratem. Wówczas jest kwadratem, jeśli Zatem wynikiem jest liczba par takich samych elementów w ciągu

Zliczanie par
Załóżmy przez chwilę, że znamy ciąg i chcemy policzyć liczbę par elementów o takich samych wartościach. W tym celu wystarczy posortować ciąg niemalejąco. Wówczas elementy o tych samych wartościach znajdą się obok siebie (będą tworzyły bloki). Następnie przeglądamy kolejne bloki elementów i zliczamy pary. W -elementowym bloku można wybrać par. Sortowanie realizujemy w czasie podział na bloki odbywa się w czasie Zatem zliczanie par tych samych elementów w ciągu odbywa się w czasie

Wyznaczenie ciągu w
Wartość dla każdego od do liczymy niezależnie. Początkowo niech dla każdego Następnie przeglądamy kolejne kwadraty jako kandydatów na dzielniki Jeśli rozpatrywany kwadrat jest dzielnikiem to dzielimy przez ten kwadrat. W ten sposób z rozkładu na czynniki pierwsze usuniemy kwadraty.

Wyznaczenie ciągu w
Zauważmy, że nie ma potrzeby przeglądania wszystkich kwadratów. Wystarczy rozważać kwadraty liczb pierwszych Pamiętajmy o tym, że kwadrat może wielokrotnie występować w rozkładzie na czynniki pierwsze. Wtedy musimy usunąć wszystkie jego wystąpienia. Przykładowo: liczbę musimy dwukrotnie podzielić przez Każda liczba zostanie podzielona co najwyżej razy. Liczbę liczb pierwszych w przedziale szacujemy jako Stąd całkowita złożoność wynosi

Wyznaczenie ciągu w
Na początku zliczmy wystąpienia liczb w ciągu Niech (zbiór indeksów elementów ciągu o wartości ). Następnie przeglądamy kwadraty liczb pierwszych z przedziału jako potencjalne dzielniki. Załóżmy, że rozpatrujemy kwadrat Wiemy, że jest on dzielnikiem: Dla każdej z tych wartości, korzystając z tablicy zliczającej odwołujemy się bezpośrednio do elementów, które są podzielne przez i te elementy dzielimy przez Po zakończeniu otrzymane wartości tworzą ciąg Do każdego elementu ciągu odwołamy się co najwyżej razy. Liczba rozpatrywanych wielokrotności wynosi: co w sumie wynosi Zatem otrzymaliśmy rozwiązanie działające w czasie

Wyznaczenie ciągu w
Połączmy dwa poprzednie rozwiązania i Najpierw, podobnie jak w dla każdego elementu ciągu rozważmy jego potencjalne dzielniki (kwadraty liczb pierwszych), nie większe niż Takich dzielników jest Następnie zaaplikujmy rozwiązanie z drobną zmianą. Rozpatrujmy tylko wielokrotności kwadratów liczb pierwszych większych od Niestety, tak opisane rozwiązanie nadal wymaga utworzenia tablicy zliczającej rozmiaru Do implementacji tablicy zliczającej wystarczy użyć tablicy mieszającej (tablicy z haszowaniem) i problem zostaje rozwiązany. Otrzymujemy algorytm, który działa w czasie Dowód tego oszacowania pozostawiam Czytelnikowi. Jednocześnie zachęcam do pomyślenia nad lepszym oszacowaniem.