Tym razem na najbardziej bezużytecznym w tej części galaktyki blogu zaprezentujemy jakże fascynujące zagadnienie liczb pierwszych wskaźnikowych.
Zapewniam, że ci z Czytelników, którzy dotychczas o owych tajemniczych liczbach nie słyszeli, zostaną za chwil parę Oświeceni.
Spłynie na Was łaska Wiedzy, dzięki czemu Wasze życia będą pełniejsze, samice Waszych jaków będą dawać więcej mleka, a sandały Wasze będą lepiej trzymać się Waszych stóp.
Liczbą pierwszą wskaźnikową nazywamy taką liczbę pierwszą, która różni się od kolejnej liczby pierwszej o sumę własnych cyfr.
Czyli tak: bierzemy liczbę pierwszą pi, sumujemy jej cyfry, wynik dodajemy do pi - jeżeli na końcu wyszła nam liczba pierwsza pi+1 to znaczy, że pi jest liczbą pierwszą wskaźnikową.
Przykłady takich liczb:
1409: 1409 + 1 + 4 + 9 = 1423 (między 1423 a 1409 nie ma innych liczb pierwszych)
36353: 36353 + 3 + 6 + 3 + 5 + 3 = 36373 (między 36353 a 36373 nie ma liczb pierwszych)
285317: 285317 + 2 + 8 + 5 + 3 + 1 + 7 = 285343
I tak dalej...
Liczby pierwsze wskaźnikowe nie są jakąś rzadkością - wśród liczb pierwszych mniejszych od dziesięciu miliardów znajduje się ich prawie cztery i pół miliona.
Zastanawiam się teraz, czy istnieją liczby dwuwskaźnikowe, a więc takie, że zarówno ni jak też ni+1 są liczbami wskaźnikowymi. Spróbujmy napisać małą pchełkę w Pythonie:
Aha, proszę się nie martwić pozornie dużą ilością kodu w poniższej Pchełce; większa jego część pochodzi z jednej z niedawnych pchełek o teście Millera - Rabina.
def try_composite(a, d, n, s):
if pow(a, d, n) == 1:
return False
for i in range(s):
if pow(a, 2 ** i * d, n) == n - 1:
return False
return True # n is definitely composite
def is_prime(n, precision_for_huge_n=16):
if n in known_primes or n in (0, 1):
return True
if any((n % p) == 0 for p in known_primes):
return False
d, s = n - 1, 0
while not d % 2:
d, s = d >> 1, s + 1
if n < 1373653:
return not any(try_composite(a, d, n, s) for a in (2, 3))
if n < 25326001:
return not any(try_composite(a, d, n, s) for a in (2, 3, 5))
if n < 118670087467:
if n == 3215031751:
return False
return not any(try_composite(a, d, n, s) for a in (2, 3, 5, 7))
if n < 2152302898747:
return not any(try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11))
if n < 3474749660383:
return not any(try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13))
if n < 341550071728321:
return not any(try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17))
if n < 3825123056546413051:
return not any(try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17, 19, 23))
if n < pow(2, 64):
return not any(try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37))
# otherwise
return not any(try_composite(a, d, n, s) for a in known_primes[:precision_for_huge_n])
def sum_digits(n):
r = 0
while n:
r, n = r + n % 10, n // 10
return r
def is_a_2_pointer(n):
n2 = n + sum_digits(n)
n3 = n2 + sum_digits(n2)
return is_prime(n) and is_prime(n2) and is_prime(n3) and known_primes.index(n) == known_primes.index(n3) - 2
known_primes = [2, 3]
known_primes += [x for x in range(5, 1000000, 2) if is_prime(x)]
for x in known_primes:
if is_a_2_pointer(x):
print(x)
Powyższy kod po kilku minutach zwrócił mi całkiem pokaźną, kompletną listę liczb pierwszych dwuwskaźnikowych mniejszych od miliona:
11, 101, 2039, 15107, 41117, 43207, 50599, 53507, 104597, 110237, 120209, 135979, 141107, 155027, 157061, 175573, 218171, 260893, 307969, 360007, 391553, 400093, 401179, 411127, 426583, 474241, 482051, 613673, 701741, 753197, 937511, 968971
Spróbujmy teraz znaleźć liczby 3-wskaźnikowe mniejsze od miliona:
def is_a_3_pointer(n):
n2 = n + sum_digits(n)
n3 = n2 + sum_digits(n2)
n4 = n3 + sum_digits(n3)
return is_prime(n) and is_prime(n2) and is_prime(n3) and is_prime(n4) and known_primes.index(
n) == known_primes.index(n4) - 3
known_primes = [2, 3]
known_primes += [x for x in range(5, 1000000, 2) if is_prime(x)]
for x in known_primes:
if is_a_3_pointer(x):
print(x)
Nie udało się - zwiększmy więc zakres do pięciu milionów...
def is_a_3_pointer(n):
n2 = n + sum_digits(n)
n3 = n2 + sum_digits(n2)
n4 = n3 + sum_digits(n3)
return is_prime(n) and is_prime(n2) and is_prime(n3) and is_prime(n4) and known_primes.index(
n) == known_primes.index(n4) - 3
known_primes = [2, 3]
known_primes += [x for x in range(5, 5000000, 2) if is_prime(x)]
for x in known_primes:
if is_a_3_pointer(x):
print(x)
Tu już mamy jakieś rezultaty:
1427411, 2222741, 2635121, 4040921
Wyższych krotności szukać już nie będę, bom leniwy, ale zachęcam wnikliwego Czytelnika do eksperymentowania.
Na koniec dzisiejszego wpisu trzy uwagi:
- Nazwa "liczby wskaźnikowe" (jak również dwuwskaźnikowe, 3-wskaźnikowe itd) została przeze mnie wymyślona na potrzeby niniejszego wpisu. Na próżno więc szukać tego określenia gdzie indziej. Po angielsku nazywają się one a-pointer prime numbers, jednak nie udało mi się nigdzie namierzyć wersji polskojęzycznej.
- Przydatność tych liczb w życiu codziennym jest taka sama, jak przydatność kwazarów do optymalizowania grafów nieskierowanych. Czyli żadna. Ale nic nie szkodzi, znam o wiele gorsze metody marnowania czasu...
- Przedstawiony tu sposób szukania liczb N-wskaźnikowych jest prawdopodobnie jednym z najgorszych możliwych sposobów jeśli chodzi o szybkość działania. O wiele prościej byłoby najpierw wyszukać wszystkie liczby wskaźnikowe, potem wśród nich poszukać 2-wskaźnikowych i tak dalej. W ten sposób dla rosnących N mielibyśmy malejący czas wyszukiwania. Ale, jak już wiele razy mówiłem, jestem za leniwy, żeby to napisać lepiej. No i pozostawiam pole do popisu dla dociekliwych Czytelników 😉
Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]
Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.