Spirala Ulama (spirala liczb pierwszych) – część 2 – czyli funkcja kwadratowa i zabawy z rekurencją (część 5)

W części 1 wpisu na temat Spirali Ulama zaznaczyłem, że efekt wizualnego ułożenia liczb pierwszych na diagonalach spirali kwadratowej jest konsekwencją głównie dwóch własności:

  1. Na przekątnych są albo same liczby parzyste, albo same liczby nieparzyste, zatem tylko diagonale z liczbami nieparzystymi będą agregować liczby pierwsze;
  2. Niektóre diagonale zagęszczają bardziej liczby pierwsze niż inne, co wynika z zależności pomiędzy przekątnymi i funkcją kwadratową oraz faktem, że niektóre funkcje kwadratowe generują więcej liczb pierwszych niż inne.

Dzisiejszy tekst poświęcę przybliżeniu własności nr 2.

Wielomiany i rekurencja

Funkcja kwadratowa i rekurencja

Dla wielomianów możemy zawsze podać ich postać rekurencyjną, Jest to własność mało znana, jednak dosyć prosta w uzasadnieniu. Pokażę to na przykładzie funkcji kwadratowej, jednocześnie wzbogacając cykl „Zabawy z rekurencją” 🙂

$$f(x) = ax^2+bx+c$$

Rozważmy następnie równanie

$$f(x+1)=f(x)+Bx+C$$

Podstawiając i upraszczając…

$$a(x+1)^2+b(x+1)+c=ax^2+bx+c+Bx+C$$

$$ax^2+2ax+a+bx+b+c=ax^2+bx+c+Bx+C$$

$$2ax+a+b=Bx+C$$

$2a=B$    oraz    $a+b=C$

otrzymujemy

$a=\frac{B}{2}$    oraz    $b=C-a$

Następnie analizując $f(1)$ mamy

$f(1)=a+b+c$    zatem    $c=f(1)-a-b$

$$c=f(1)-a-(C-a)=f(1)-C$$

Wniosek: jeśli znana jest relacja rekurencyjna $f(x+1)=f(x)+Bx+C$ oraz znamy wartość $f(1)$ to jesteśmy w stanie jednoznacznie wskazać równanie kwadratowe $ax^2+bx+c$ spełniające daną zależność rekurencyjna, gdzie

$a=\frac{B}{2}$,    $b=C-a$,    $c=f(1)-C$

Uogólnienia dokonujemy na bazie dwumianu Newtona

$$(x+1)^n = {n\choose 0}x^n+{n\choose 1}x^{n-1}+{n\choose 2}x^{n-2}+\ldots+{n\choose {n-1}}x+{n\choose n}$$

Funkcja kwadratowa i linie proste / przekątne na spirali Ulama

Poniżej spróbuję pokazać w jaki sposób „nawijanie prostej na kwadrat” sprawia, że parabole w efekcie otrzymują kształt linii prostych.

Przykład 1 – Pionowa prosta

Spirala Ulama - równanie prostej 1

Zapisujemy zależność rekurencyjną

$$f(1)=4$$

$$f(2)=f(1)+1+2+3+3+2$$

$$f(3)=f(2)+2+3+5+5+3$$

$$\ldots$$

$$f(n+1)=f(n)+n+2n+(2n+1)+(2n+1)+(n+1)$$

$$f(n+1)=f(n)+8n+3$$

Teraz, korzystając z wyprowadzonego wcześniej wzoru, wyznaczamy współczynniki a, b, c funkcji kwadratowej spełniającej $f(n+1)=f(n)+8n+3$.

$a=\frac{8}{2}=4$,    $b=3-4=-1$,    $c=4-3=1$

$$f(n)=4n^2-n+1$$

Dla testu czy wszystko jest ok sami podstawcie $n=1,2,3\ldots$

Przykład 2 – Przekątna (linia diagonalna)

Spirala Ulama - równanie prostej 2

Ponownie zapisujemy zależność rekurencyjną, tym razem nieco prostszą.

$$f(1)=3$$

$$f(2)=f(1)+2+2+3+3$$

$$f(3)=f(2)+4+4+5+5$$

$$\ldots$$

$$f(n+1)=f(n)+n+2n+2n+(2n+1)+(2n+1)$$

$$f(n+1)=f(n)+8n+2$$

Korzystając ze znanego wzoru wyznaczamy a, b, c dla $f(n+1)=f(n)+8n+2$.

$a=\frac{8}{2}=4$,    $b=2-4=-2$,    $c=3-2=1$

$$f(n)=4n^2-2n+1$$

Przykład: funkcja $n^2+n+41$ generująca liczby pierwsze

Wielomian $n^2+n+41$ jest funkcją „często generującą” liczby pierwsze. W tym przypadku dla każdego $n=0,1,\ldots,39$ wynik jest zawsze liczbą pierwszą. Poniżej tabela prezentująca zestawienie dla $n$ z zakresu od $0$ do $100$.

n n^2+n+41 Czy liczba pierwsza?
0 41 1
1 43 1
2 47 1
3 53 1
4 61 1
5 71 1
6 83 1
7 97 1
8 113 1
9 131 1
10 151 1
11 173 1
12 197 1
13 223 1
14 251 1
15 281 1
16 313 1
17 347 1
18 383 1
19 421 1
20 461 1
21 503 1
22 547 1
23 593 1
24 641 1
25 691 1
26 743 1
27 797 1
28 853 1
29 911 1
30 971 1
31 1033 1
32 1097 1
33 1163 1
34 1231 1
35 1301 1
36 1373 1
37 1447 1
38 1523 1
39 1601 1
40 1681 0
41 1763 0
42 1847 1
43 1933 1
44 2021 0
45 2111 1
46 2203 1
47 2297 1
48 2393 1
49 2491 0
50 2591 1
51 2693 1
52 2797 1
53 2903 1
54 3011 1
55 3121 1
56 3233 0
57 3347 1
58 3463 1
59 3581 1
60 3701 1
61 3823 1
62 3947 1
63 4073 1
64 4201 1
65 4331 0
66 4463 1
67 4597 1
68 4733 1
69 4871 1
70 5011 1
71 5153 1
72 5297 1
73 5443 1
74 5591 1
75 5741 1
76 5893 0
77 6047 1
78 6203 1
79 6361 1
80 6521 1
81 6683 0
82 6847 0
83 7013 1
84 7181 0
85 7351 1
86 7523 1
87 7697 0
88 7873 1
89 8051 0
90 8231 1
91 8413 0
92 8597 1
93 8783 1
94 8971 1
95 9161 1
96 9353 0
97 9547 1
98 9743 1
99 9941 1
100 10141 1

Po więcej przykładów odsyłam do artykułu „Prime-Generating Polynomial”.

Pozdrowienia,

Mariusz Gromada

Views All Time
Views All Time
7748
Views Today
Views Today
1

1 myśl w temacie “Spirala Ulama (spirala liczb pierwszych) – część 2 – czyli funkcja kwadratowa i zabawy z rekurencją (część 5)

  1. Witam!
    Jestem właśnie świeżo po filmie poświęconym „funkcji generującej liczby pierwsze” i tylko pragnę zwrócić uwagę na fakt że funkcja ta ma postać f(x) = (x^2) – x + 41.
    Błędny jest zapis funkcji we wpisie poświęconym spiralom Ulama. Brak jest „minusa”. Jako, że jestem właśnie „świeżo” po dawce ciekawych informacji na temat tej funkcji od razu błąd rzucił mi się w oczy.
    Pozdrawiam serdecznie,
    Damian Brzeziński

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *