Symbol Newtona

0

Witam.
Rozwiązuje zadany problem:
Policz ilość nieparzystych wartości Symbolu Newtona dla 0<= n,k <=N. Ograniczenie N<10^9
Do czego doszedłem. Po zamienieniu w Trójkącie Pascala (który jest zbiorem interesujących mnie wyników) wartości parzystych na 0 a nieparzystych na 1 uzykuję fraktal, Trójkąt Sierpińskiego. Indeksując od zera n jako wiersza a k jako kolumny, mam napisane rozwiązanie mojego problemu. Musze tylko jeszcze policzyć ilość jedynek i najlepiej w dość szybkim czasie.
Co zauważyłem:

  1. Każdy wiersz zawiera tyle 1 ile 2^x, a x to ilość jedynek w zapisie binarnym N (wiersz). Jednak dla miliarda N trochu to zajmie, nawet jeżeli ztablicuje wszystkie potęgi 2 do 32 (miliard mieści się w 32 bitach).
  2. Jeżeli n+1=2x to liczba nieparzystych rozwiązań wynosi 3x.
    Teraz na pewno da się zrobić jakąs sprytną rekurencję (w SPACJA końcu to fraktal) do policzenia ilości jedynek między N a najbliższym 2^x. Proszęo pomoc i rady.
    Pozdrawiam i przepraszam za błędy w pisowni.
0

Narysowałem sobie trójkąt Pascala, policzyłem sobie nieparzyste w wierszach, otrzymałem 1, 2, 2, 4, 2, 4, 4, 8, 2, 4... .
Zapytałem o ten ciąg The On-Line Encyclopedia of Integer Sequences, otrzymałem odpowiedź (Sloane’s A006046)
Kolejnym ciągiem jest narastająca suma 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, ..., czyli (Sloane’s A006046).
Link który z pewnością warto mieć w swoich bookmarkach.

1 użytkowników online, w tym zalogowanych: 0, gości: 1