Pchełki VBA, odcinek 22: Niedotykalska

Niedotykalskość jest pojęciem matematycznym. Jeżeli więc ktoś spodziewał się tutaj czegoś innego (zaprawdę nie wiem, czego), to niech lepiej idzie oglądać śmieszne koty.

Liczba niedotykalska (po naszemu: untouchable number) to taka liczba naturalna, której nie da się przedstawić w postaci sumy podzielników jakiejkolwiek liczby naturalnej (z wyłączeniem tej liczby).

Jeszcze raz: bierzemy jakąś liczbę X i chcemy sprawdzić, czy jest niedotykalska. W tym celu bierzemy po kolei każdą liczbę naturalną N (od jedynki do nieskończoności), a następnie liczymy sumę podzielników N (ale bez N). Jeżeli wśród tych wszystkich sum (których jest nieskończenie wiele) nie ma naszej liczby X, to znaczy, że X jest niedotykalska.

Proste?

Ale że niby jak – do nieskończoności? Nie da się przecież!

To prawda. Do nieskończoności to można sobie sumować tylko w teorii. W praktyce najpierw skończą się palce, potem ołówki i kartki, a na koniec pamięć elektroniczna. I tyle będzie z tego naszego sumowania. Trzeba temat ugryźć jakoś inaczej.

Weźmy sobie na ten przykład liczbę 5. Czy jest ona niedotykalska, czy nie?

Piątkę da się przedstawić w postaci sumy na kilka sposobów:

1+4
2+3
1+1+3
1+2+2
1+1+1+2
1+1+1+1+1

Z powyższej listy po pierwsze eliminujemy wszystkie pozycje, które nie zawierają jedynki (bo każda liczba dzieli się przez 1), a po drugie wszystkie pozycje, które zawierają duplikat jakiejś liczby (bo każdy podzielnik bierzemy tylko raz).

Zostaje jedna kombinacja:

1+4

Czy jakaś liczba może dzielić się wyłącznie przez jeden i przez cztery?

No raczej nie za bardzo, bo dzieliłaby się wówczas również przez dwa, a 1+2+4<>5

A więc właśnie wykazaliśmy, że piątka jest liczbą niedotykalską.

A inne przykłady?

Według Wikipedii następną po piątce liczbą niedotykalską jest 52. Nie za bardzo wiem, w jaki sposób można wyliczyć (analitycznie), że 52 jest niedotykalska, ale spróbujmy zabrać się za zagadnienie w sposób podobny do piątki.

Ponieważ jednak ilość kombinacji do sprawdzenia jest tutaj „odrobinkę” większa, ugryziemy zagadnienie w „odrobinkę” inny sposób.

Najpierw zauważmy, że szukając liczby X wśród sum podzielników liczb naturalnych nie musimy sprawdzać WSZYSTKICH liczb naturalnych (aż do nieskończoności), wystarczy sprawdzić liczby od 1 do X²+1. Wynika to z faktu, że jeżeli jakaś liczba N jest pierwsza, to suma jej podzielników wyniesie 1 (pamiętamy, że do sumowania nie wchodzi sama liczba N), a jeżeli liczba N jest złożona, to albo jest kwadratem jakiejś liczby pierwszej P (i wtedy suma podzielników wyniesie 1+P) albo nim nie jest, i wtedy suma podzielników wyniesie więcej, niż pierwiastek z N.

(jeżeli ktoś tego jeszcze nie widzi, zapraszam do analizy rozwiązania zagadki o stu przełącznikach)

A więc w przypadku 52 musimy sprawdzić sumy podzielników wszystkich liczb naturalnych od 1 do 2705 (52*52+1)

Ponieważ wkraczamy tu w obszar, gdzie palce się kończą i nawet ołówków musielibyśmy wypisać całkiem sporo, zaprzęgniemy do pracy koń-puter.

Napiszemy sobie prościutki kod w VBA, który będzie nam liczył sumę podzielników zadanej liczby naturalnej. A potem go użyjemy do sprawdzenia wszystkich liczb od 1 do 2705.

Czyli tak: Excel, nowy dokument, Alt-F11, wstawiamy nowy moduł i piszemy w nim:

Option Explicit

Public Function DivSum(n As Long) As Long
    Dim r As Long
    r = 0
    Dim i As Long
    For i = 1 To n - 1
        If n Mod i = 0 Then r = r + i
    Next
    DivSum = r
End Function

Następnie wracamy do arkusza i wypełniamy kolumnę A wartościami od 1 w dół aż do 2705.
W kolumnie B zaś wpisujemy formułę: =DivSum(A1) (i kopiujemy ją w dół aż do wiersza 2705)

Na koniec sprawdzamy, czy w kolumnie B znajdziemy liczbę 52.

Szukamy, szukamy…

… szukamy…

… różne inne liczby…

Nie, no bez sensu, tak to ja sobie mogę szukać do usranej śmierci…

Zaznaczamy wszystko, kopiuj, wklej specjalnie, wartości. Sortujemy po kolumnie B. Podziwiamy.

Czym bardziej w dół, tym rzadziej się sumy powtarzają. Mijamy 51 i widzimy zaraz za nią 53. Faktycznie, 52 nie ma.

A więc 52 jest niedotykalska. Wikipedia po raz kolejny powiedziała prawdę 😉

W jaki sposób znaleźć następną liczbę niedotykalską?

Trzeba pracowicie sprawdzać sumy podzielników kolejnych liczb naturalnych N, sortować wyniki według tych sum i sprawdzać, czy napotkane „dziury” są mniejsze, niż pierwiastek kwadratowy z N. Każda taka dziura będzie kolejną liczbą niedotykalską.

Przeprowadzenie tego eksperymentu pozostawiam już znudzonemu Czytelnikowi.