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 - Przęką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