Pytania otagowane jako number-theory

teoria liczb to dział matematyki dotyczący matematycznych właściwości liczb i związków między różnymi typami liczb. Tego znacznika należy używać w przypadku pytań dotyczących zagadnień informatycznych, które są przedstawiane z perspektywy teorii liczb lub mogą obejmować teorię liczb lub których odpowiedź mogłaby lub powinna być sformułowana w terminach teorii liczb.

1
Problem sumy podzbiorów z wieloma warunkami podzielności
Niech SS.S będzie zbiorem liczb naturalnych. Rozważamy SS.S w częściowej kolejności podzielności, tj. . Pozwolićs1≤s2⟺s1∣s2s1≤s2)⟺s1∣s2)s_1 \leq s_2 \iff s_1 \mid s_2 α(S)=max{|V|∣V⊆S,Vα(S.)=max{|V.|∣V.⊆S.,V.\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, V an antichain .}}\} Jeśli weźmiemy pod uwagę problem sumy podzbioru, w którym wieloseksem liczb jest , to co możemy …
1
Złożoność przyjmowania mod
To wydaje się pytaniem, które powinno mieć łatwą odpowiedź, ale nie mam ostatecznego: nnna,pa,pa, pamodpamodpa\bmod p Jedynie podzielenie przez będzie wymagać czasu , gdzie jest złożoność mnożenia. Ale czy można wykonać nieco szybciej?aaappp O(M(n))O(M(n))O(M(n))M(n)M(n)M(n)modmod\bmod
2
Jak skutecznie znaleźć element sekwencji Sumy cyfr?
Właśnie poza zainteresowaniem próbowałem rozwiązać problem z kategorii „Ostatnie” projektu Euler ( sekwencja sumy cyfr ). Ale nie jestem w stanie wymyślić sposobu skutecznego rozwiązania problemu. Problem jest następujący (w oryginalnej sekwencji pytań ma dwie na początku, ale nie zmienia sekwencji): Sekwencja sumy cyfr wynosi 1, 2, 4, 8, 1, …
5
Numery hipotez Goldbacha i Busy Beaver?
Tło: Jestem kompletnym laikiem w dziedzinie informatyki. Czytałam o numerach Busy Beaver tutaj i znalazłem następujący fragment: Ludzkość może nigdy nie poznać wartości BB (6) na pewno, nie mówiąc już o wartości BB (7) lub jakiejkolwiek większej liczbie w sekwencji. Rzeczywiście, wymyka się nam już pierwsza piątka i szóstka rządzących: …
3
Jak szybko możemy znaleźć wszystkie kombinacje czterech kwadratów, które sumują się do N?
Pytanie zostało zadane w Stack Overflow ( tutaj ): Biorąc pod uwagę całkowitą wydrukować wszystkie możliwe kombinacje wartości całkowitych z i dzięki którym rozwiązuje się równanie .N.N.NA , B , C.ZA,b,doA,B,CrereDZA2)+ B2)+ C.2)+ D2)= NZA2)+b2)+do2)+re2)=N.A^2+B^2+C^2+D^2 = N To pytanie jest oczywiście związane z hipotezą Bacheta w teorii liczb (czasami nazywaną …
2
Najmniej powszechny niepodzielnik
SSSdddSSS∀x∈S, d∤x∀x∈S, d∤x\forall x \in S,\ d \nmid x Oznacz n=|S|n=|S|n = |S|i C=max(S)C=max(S)C = \max(S) . Rozważ funkcję F(x)=F(x)=F(x) = najmniejsza liczba pierwsza niepodzieląca xxx . Łatwo zauważyć, że F(x)≤logxF(x)≤log⁡xF(x) \leq \log x . I przez zestaw SSS , niech F(S)=F(S)=F(S) = najmniej Prime że nie dzieli każdy z …
4
Znalezienie rozmiaru najmniejszego podzbioru z GCD = 1
Jest to problem z sesji treningowej Polskiego Konkursu Programowania Uczelnianego 2012 . Chociaż mogłem znaleźć rozwiązania dla głównego konkursu, nie mogę nigdzie znaleźć rozwiązania tego problemu. Problem polega na tym: biorąc pod uwagę zbiór NNN wyraźnych liczb całkowitych dodatnich nie większych niż , znajdź rozmiar najmniejszego podzbioru, który nie ma …
2
Wydajne obliczanie najmniejszej liczby całkowitej za pomocą n dzielników
Aby rozwiązać ten problem, po raz pierwszy to zauważyłem ϕ(pe11 pe22⋯ pekk)=(e1+1)(e2+1)⋯(ek+1)ϕ(p1e1 p2e2⋯ pkek)=(e1+1)(e2+1)⋯(ek+1)\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1) Gdzie to liczba (niekoniecznie pierwsza) dzielników . Jeśli jest najmniejszą liczbą całkowitą taką, że , toϕ(m)ϕ(m)\phi(m)mmmmmmϕ(m)=nϕ(m)=n\phi(m) = n ϕ(m)=nϕ(m)=n\phi(m) = n (e1+1)(e2+1)⋯(ek+1)=n(e1+1)(e2+1)⋯(ek+1)=n(e_1 + 1)(e_2 …
1
Skutecznie znajdując maksymalny GCD parami zestawu liczb naturalnych
Rozważ następujący problem: Niech będzie skończonym podzbiorem liczb naturalnych.S={s1,s2,...sn}S={s1,s2,...sn}S = \{ s_1, s_2, ... s_n \} Niech | gdzie jest największy wspólny dzielnik z iG={G={G = \{ gcd(si,sj)gcd(si,sj)gcd(s_i, s_j)si,sj∈S,si,sj∈S,s_i, s_j \in S, si≠sj}si≠sj} s_i \neq s_j \}gcd(x,y)gcd(x,y)gcd(x,y)xxxyyy Znajdź element maksymalny w .GGG Problem ten można rozwiązać, biorąc największy wspólny dzielnik …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.