Matematyka.pl

Ile nieparzystych współczynników ma wielomian \(\displaystyle{ (x^2+x+1)^n}\) /po podniesięniu do potęgi i uporządkowaniu składników

Na start warto rozwinąć kilka pierwszych przypadków:
\(\displaystyle{ \left( n^2 + n + 1 \right) ^2 = n^4 + 2n^3 + 3n^2 + 2n + 1\\
\left( n^2 + n + 1 \right) ^3 = n^6 + 3n^5 + 6n^4 + 7n^3 + 6n^2 + 3n +1\\
\left( n^2 + n + 1 \right) ^4 = n^8 + 4n^7 + 10n^6 + 16n^5 + 19n^4 + 16n^3 + 10n^2 + 4n +1}\)

Zauważamy, że:
-pierwszy wyraz zawsze ma współczynnik \(\displaystyle{ 1}\)
-drugi wyraz zawsze ma współczynnik równy \(\displaystyle{ n}\)
-wyraz z \(\displaystyle{ x^n}\) ma najwyższy współczynnik a pozostałe są rozłożone symetrycznie względem niego
-współczynnik najwyższy przy \(\displaystyle{ x^n}\) zawsze musi być nieparzysty, bo będzie w kolejnej iteracji sumą obecnego najwyższego i dwóch swoich sąsiadów, a skoro są symetrycznie, to ich suma jest parzysta, więc razem z nim nieparzystym nowy środkowy będzie nieparzysty
-wystarczy nam analizować jedną połowę współczynników

Przepiszmy więc pierwszych kilka rzędów jako same sekwencje liczb do środkowej włącznie (same lewe połowy):
\(\displaystyle{ 1,2,3\\
1,3,6,7\\
1,4,10,16,19\\
1,5,15,30,45,51}\)
ponieważ w zasadzie nie interesują nas liczby tylko ich parzystość przepiszmy to na nią:
\(\displaystyle{ NPN\\
NNPN\\
NPPPN\\
NNNPNN}\)
łatwo możemy generować kolejne, początek to na zmianę \(\displaystyle{ NN}\) i \(\displaystyle{ NP}\), kolejne patrzymy trójkami na powyższe, jeśli jest jedno lub trzy \(\displaystyle{ P}\) wpisujemy \(\displaystyle{ P}\), w przeciwnym wypadku \(\displaystyle{ N}\), na koniec zawsze dopisujemy jedno \(\displaystyle{ N}\) (nowy najwyższy)
\(\displaystyle{
NPNPPPN\\
NNPNNPNN\\
NPPPPPPPN\\
NNNPPPPPNN\\
NPNPNPPPNPN\\
NNPNPNNPNNPN
}\)

możemy dotychczasowe wyniki wpisać do tabeli dla czytelności
\(\displaystyle{
\begin{array}{r|l}
n & licz. nieparzystych\\
\hline
1 & 3\\
2 & 3\\
3 & 5\\
4 & 3\\
5 & 9\\
6 & 5\\
7 & 11\\
8 & 3\\
9 & 9\\
10 & 9\\
11 & 15
\end{array}
}\)

Alternatywny sposób ich zliczania jest taki, że sekwencję współczynników (całe, nie połówki) zamieniamy na sekwencję jedynek i zer i każda kolejna to suma siebie samej i swoich kopii przesuniętych o 1 i o 2 miejsca, więc dla współczynników \(\displaystyle{ 1,2,3,2,1}\) zamieniamy to na \(\displaystyle{ 10101}\) i traktując to jako liczbę binarną mnożymy ją przez 2 i przez 4 dla przesunięć i wykonujemy XOR na wszystkich trzech, czyli tutaj \(\displaystyle{ (10101)_2 = 21_{10}}\), \(\displaystyle{ 21\cdot 2 = 42, 21\cdot 4 = 84}\) i \(\displaystyle{ 21 \oplus 42 \oplus 84 = (1101011)_2}\)

Korzystając z dobrodziejstw programowania policzyłem trochę dalej do przodu i jest kilka wniosków które widać:
-dla n równego potęgom dwójki liczba nieparzystych współczynników wynosi 3
-dla parzystych n liczba ta jest taka sama jak dla \(\displaystyle{ n/2}\)
-dla nieparzystych liczb, które nie są pierwsze wynik wychodzi mniejszy niż dla liczb pierwszych
-dla pozostałych nieparzystych nie widzę za bardzo schematu, poza tym, że dla wartości o 1 ponad potęgą dwójki wynik to 9 ale tylko dla tych kilku, które policzyłem
zostawiam obliczone wyniki dla nieparzystych wartości, może ktoś wpadnie na rozwiązanie

\(\displaystyle{
\begin{array}{r|l}
n & licz. nieparzystych\\
\hline
3 & 5\\
5 & 9\\
7 & 11\\
9 & 9\\
11 & 15\\
13 & 15\\
15 & 21\\
17 & 9\\
19 & 15\\
21 & 27\\
23 & 33\\
25 & 15\\
27 & 25\\
29 & 33\\
31 & 43
\end{array}
}\)

Spędziłem nad tym dobrych parę godzin ale utknąłem, niestety

Dodano po 23 godzinach 41 minutach 10 sekundach:
Przerzuciłem się z C na Pythona żeby mieć większe liczby, jeszcze zostawię tu wyniki, może się przydadzą
zostawiam też kod Pythona, którym to generowałem

Niech \(f(n)\) to liczba zapalonych bitów w \(n\)-tym wierszu piramidki (każdy kolejny wiersz piramidki to XOR poprzedniego przesuniętego bitowo o 1 w lewo oraz poprzedniego oraz poprzedniego przesuniętego bitowo o 1 w prawo). Wtedy \(f(n)=3\) dla \(n\) będącego potęgą dwójki. Dla \(n\) parzystego \(f(n)=f(\frac{n}{2})\). Dla \(n\) będącego postaci \(2^a-1\), \(f(n)=\frac{2^{a+2} \pm 1}{3}\). Dla pozostałych \(n\) nieparzystych znajdujemy największą liczbę postaci \(r = 2^a-2^b\) mniejszą od \(n\). Wtedy \(f(n)=f(n-r)f(r)\).
Czemu tak jest?
Zacznijmy od tego, że \(2n\)-ty wiersz to "rozstrzelony" wiersz \(n\)-ty. Jest tak, bo \((x^2+x+1)^2\equiv x^4+x^2+1\). Potem od każdego zapalonego bitu zaczyna się tworzyć mini-piramidka. Stąd \(f(n)=f(n-r)f(r)\). Niestety z czasem te piramidki zaczynają nachodzić na siebie nawzajem, więc wzór działa tylko wtedy gdy \(2(n-r) < d\), gdzie \(d\) to największa potęga dwójki dzieląca \(r\). Dlatego potrzebujemy osobnego wzoru dla \(n\) będącego potęgą dwójki pomniejszoną o 1. Wiemy, że w następnym wierszu znajdą się tylko trzy jedynki - po jednej na każdym z końców wiersza i jedna na środku. To nam pozwala odtworzyć jak wygląda \(n\)-ty wiersz. Około \(\frac{2}{3}\) tego wiersza to jedynki, stąd \(f(n)=\frac{2^{a+2} \pm 1}{3}\).

Dodano po 1 godzinie 58 minutach 26 sekundach:
Teraz wpadłem na prostszy sposób opisania tego samego. Liczbę \(n\) zapisujemy binarnie np. \(45 = 101101_2\). Zera zamieniamy na przecinki. Wynik to iloczyn wartości funkcji \(f\) od tych ciągów jedynek. Np. \(f(45) = f(101101_2) = f(1_2)f(11_2)f(1_2) = f(1)f(3)f(1) = 3\cdot 5 \cdot 3 = 45\). Analogicznie np. \(f(61) = f(111101_2) = f(1111_2)f(1_2) = f(15)f(1) = 21\cdot 3 = 63\).

Dodano po 41 minutach 20 sekundach:
Krótki kod w Pythonie: