Forum matematyczne: miliony postów, setki tysięcy tematów, dziesiątki tysięcy użytkowników - pomożemy rozwiązać każde zadanie z matematyki https://matematyka.pl/
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
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ą
Ukryta treść:
n to potęga, k to liczba nieparzystych współczynników
n = 1 k = 3
n = 2 k = 3
n = 3 k = 5
n = 4 k = 3
n = 5 k = 9
n = 6 k = 5
n = 7 k = 11
n = 8 k = 3
n = 9 k = 9
n = 10 k = 9
n = 11 k = 15
n = 12 k = 5
n = 13 k = 15
n = 14 k = 11
n = 15 k = 21
n = 16 k = 3
n = 17 k = 9
n = 18 k = 9
n = 19 k = 15
n = 20 k = 9
n = 21 k = 27
n = 22 k = 15
n = 23 k = 33
n = 24 k = 5
n = 25 k = 15
n = 26 k = 15
n = 27 k = 25
n = 28 k = 11
n = 29 k = 33
n = 30 k = 21
n = 31 k = 43
n = 32 k = 3
n = 33 k = 9
n = 34 k = 9
n = 35 k = 15
n = 36 k = 9
n = 37 k = 27
n = 38 k = 15
n = 39 k = 33
n = 40 k = 9
n = 41 k = 27
n = 42 k = 27
n = 43 k = 45
n = 44 k = 15
n = 45 k = 45
n = 46 k = 33
n = 47 k = 63
n = 48 k = 5
n = 49 k = 15
n = 50 k = 15
n = 51 k = 25
n = 52 k = 15
n = 53 k = 45
n = 54 k = 25
n = 55 k = 55
n = 56 k = 11
n = 57 k = 33
n = 58 k = 33
n = 59 k = 55
n = 60 k = 21
n = 61 k = 63
n = 62 k = 43
n = 63 k = 85
n = 64 k = 3
def bits(n):
r = 7
i = 1
while i < n:
i += 1
r = r ^ (r*2) ^ (r*4)
k = 0
while r > 0:
if r % 2 == 0:
#print("0",end="")
r //= 2
else:
k += 1
#print("1",end="")
r = (r-1) // 2
return k
for i in range(1, 65):
print("n =", i, " k =", bits(i))
Re: Współczynniki
: 27 gru 2023, o 13:34
autor: Wojciech_Domin
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: