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

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

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)

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

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa