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.