Pchełki Python: liczby N-wskaźnikowe

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:

  1. 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.
  2. 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…
  3. 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 😉

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

Bądź pierwszy!

Powiadom o
avatar
wpDiscuz