Biorąc pod uwagę liczbę nieujemną n
, wypisz liczbę sposobów wyrażenia n
jako sumę dwóch kwadratów liczb całkowitych n == a^2 + b^2
( OEIS A004018 ). Zauważ, że a
i b
mogą być dodatnie, ujemne lub zero, a ich kolejność ma znaczenie. Wygrywa najmniej bajtów.
Na przykład n=25
daje, 12
ponieważ 25
można wyrazić jako
(5)^2 + (0)^2
(4)^2 + (3)^2
(3)^2 + (4)^2
(0)^2 + (5)^2
(-3)^2 + (4)^2
(-4)^2 + (3)^2
(-5)^2 + (0)^2
(-4)^2 + (-3)^2
(-3)^2 + (-4)^2
(0)^2 + (-5)^2
(3)^2 + (-4)^2
(4)^2 + (-3)^2
Oto wartości do n=25
. Uważaj, aby Twój kod działał n=0
.
0 1
1 4
2 4
3 0
4 4
5 8
6 0
7 0
8 4
9 4
10 8
11 0
12 0
13 8
14 0
15 0
16 4
17 8
18 4
19 0
20 8
21 0
22 0
23 0
24 0
25 12
Oto wartości do n=100
listy.
[1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0, 12, 8, 0, 0, 8, 0, 0, 4, 0, 8, 0, 4, 8, 0, 0, 8, 8, 0, 0, 0, 8, 0, 0, 0, 4, 12, 0, 8, 8, 0, 0, 0, 0, 8, 0, 0, 8, 0, 0, 4, 16, 0, 0, 8, 0, 0, 0, 4, 8, 8, 0, 0, 0, 0, 0, 8, 4, 8, 0, 0, 16, 0, 0, 0, 8, 8, 0, 0, 0, 0, 0, 0, 8, 4, 0, 12]
Zabawne fakty: Sekwencja zawiera terminy, które są dowolnie wysokie, a limit jej średniej ruchomej wynosi π.
Tabela liderów:
var QUESTION_ID=64812,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/64812/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
1,0,2,0,0,3,0,0,0,4,0,0,0,0,5,...
. Odcinając sekwencję po dowolnej niezerowej liczbie, średnia jak dotąd wynosi 1. I biegi zer mają coraz mniejszy wpływ na później w sekwencji.Odpowiedzi:
Python (
59 5756 bajtów)Demo online
Podobnie jak w przypadku mojej odpowiedzi CJam, wykorzystuje to inwersję Möbiusa i działa w czasie pseudo-kwazilinearnym.
Dzięki Sp3000 za 2 bajty oszczędności i feersum za 1.
źródło
-1**x
to, że zawsze-1
. Spodziewałem się, że-1
będzie to pojedynczy dosłowny całkowity token, a nie jednorzędny minus o niskim priorytecie, po którym następuje jeden.**x
.Mathematica, 13 bajtów
Jeśli dozwolone są wbudowane, tak to zrobić w Mathematica.
Dla 0 <= n <= 100
źródło
Python 2, 44 bajty
Jest to prawie to samo co rozwiązanie xsot (oparte na rozwiązaniu Petera Taylora ), ale oszczędza 8 bajtów, upraszczając sposób obsługi znaków.
Pamiętaj, że w przypadku pełnego programu możemy zapisać 2 bajty w funkcji bez ponoszenia kosztów poza funkcją:
Dwa dodatkowe bajty dla pełnego programu w ten sposób:
Dla
n > 0
tam jest bardzo czytelne rozwiązanie 40-bajtowy:źródło
Pyth, 13 bajtów
Zestaw testowy
źródło
Q
.J, 16 bajtów
Jest to czasownik monadyczny (innymi słowy, jednoargumentowa funkcja). Wypróbuj online lub sprawdź, czy pomyślnie przeszedł wszystkie przypadki testowe .
Wyjaśnienie
źródło
Python 2,
69555352 bajtyJest to funkcja rekurencyjna oparta na doskonałym rozwiązaniu Petera Taylora .
źródło
f=lambda n,x=1:+(x>n)or(n%x<1)-f(n,x+2)/4<<2
. Sądzę też, że nie obchodzi nas przekroczenie domyślnej maksymalnej głębokości rekurencji?/4<<2
sztuczka xsot czyni go krótszym niż to, co miałem.Julia, 40 bajtów
Nie golfowany:
Zauważ, że pętla nie obejmuje
i==0
, ponieważ gdyn
jest kwadratem, jest już uwzględniona przezi=sqrt(n)
, i są tylko cztery, a nie osiem, dla tej formy (0^2+k^2, 0^2+(-k)^2, k^2+0^2, (-k)^2+0^2
).źródło
CJam,
2523 bajtówJest to rozwiązanie teoretyczne, które wymaga O (9 n ) czasu i pamięci na wejście n .
Kosztem jednego dodatkowego bajtu - w sumie 24 bajtów - możemy zredukować złożoność do O (n 2 ) :
Wypróbuj online!
Jak to działa
Zarówno
lub
Następnie
źródło
CJam (
25 24 2221 bajtów)Demo online
Działa to w czasie pseudo-quasi-liniowym * i wykorzystuje stwierdzenie OEIS, że
Wkład
0
jest oczywiście szczególnym przypadkiem (transformacje Möbiusa i anihilatory nie idą w parze), ale ostatecznie kosztuje tylko jeden znak.* Pseudo - ponieważ jest quasilinearny w wartości wejściowej, a nie w wielkości wejściowej; quasi, ponieważ wykonuje
Theta(n)
operacje na liczbach całkowitych wielkości w kolejnościn
;b
operacja -bitowa mod powinien wziąćb lg b
czas, więc ogólnie rzecz biorąc to bierzeTheta(n lg n lg lg n)
czas.źródło
Japt ,
423733 bajtówJapt to skrócona wersja Ja vaScri pt . Interpretator
Jak to działa
Być może istnieje lepsza technika; sugestie są mile widziane.
źródło
Python 3,
686160 bajtówKorzystanie z dwóch zestawień zagnieżdżonych list jest zbyt drogie. Zamiast tego sprawdza, czy obie współrzędne na okręgu o promieniu sqrt (n) są liczbami całkowitymi.
Peter Taylor pokonał to dzięki podejściu opartemu na inwersji Moebiusa .
źródło
n=0
elegancko rozwiązać .Oktawa, 28 bajtów
źródło
Haskell, 42 bajty
Przykład użycia:
źródło
q
w straży jest sprytne, zapamiętam tę sztuczkę.Julia,
897963 bajtówJest to nazwana funkcja,
a
która przyjmuje liczbę całkowitą i zwraca liczbę zmiennoprzecinkową. Wywołuje funkcję pomocnikag
.Nie golfowany:
Podejście to wykorzystuje uproszczenie wzoru Wesleya Ivana Hurta wymienionego w OEIS. Uproszczenie zostało znalezione przez Glen O, tę samą osobę, która straciła 26 bajtów tej odpowiedzi!
źródło
x^.5
zamiast,sqrt(x)
aby zapisać 3 bajty. I(n==0)
oszczędza 2 bajty1÷(n+1)
. I możesz zapisać 4 dodatkowe znaki, używająccos(π*sqrt(x))^2÷1
zamiastfloor(cos(π*sqrt(x))^2)
. Używaj1:n/2
raczej niż1:n÷2
, ponieważ nie ma żadnej szkody przy użyciu pływaka wg(x)
i tak czy inaczej zostanie on zablokowany na liczbach całkowitychi
. Isum(i->g(i)g(n-i),1:n/2)
ogolą jeszcze kilka postaci.sum
Sztuczka nie powiedzie sięn=0
jednak, więc trzymałem tablicę ze zrozumieniem.i=0
sprawa zdarzyła się łącznie, możesz włączyć znak4g(n)
. Tak więc(n==0)-4g(n)-4g(n/2)+8sum(i->g(i)g(n-i),0:n/2)
, który nie popełni błędu. Ale możesz zrobić jeszcze lepiej, odnotowując symetrie -(n==0)+4sum([g(i)g(n-i)for i=1:n])
Pyth,
1615 bajtówWypróbuj online w kompilatorze Pyth .
Jak to działa
źródło
TI-BASIC, 23 bajty
Całkiem proste.
Σ(
to sumowanie.O dziwo
sum(seq(sum(seq(
rzucaERR:ILLEGAL NEST
i tak samoΣ(Σ(
, alesum(seq(Σ(
jest w porządku. Zdecydowałem się umieścićΣ(
wnętrze, aby uratować bliskie miąższ.źródło
sum
iΣ
?X²+Y²=Ans
wartości X między-Ans
iAns
. suma (jest sumą listy , więc musimy najpierw utworzyć listę za pomocą seq (..., Y, -Ans, AnsJavaScript (ES6),
6660 bajtów6 bajtów zapisanych dzięki @ edc65 !
Wyjaśnienie
Test
źródło
n=>eval('for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n')
eval
umieścićfor
pętle do funkcji strzałki bez nawiasów. Zapomniałem również o~
haha operatora.Python 3,
936269 bajtówItertools nie działały, więc ponownie użyłem dwóch zakresów, ale przesunąłem zakres, aby zapisać bajty.
Edycja: Poprzedni kod tak naprawdę nie działał, ponieważ zdefiniowałem zakres powyżej n, zanim zdefiniowałem n.
źródło
APL,
232019 bajtówWyjaśnienie:
Poza tym, że APL nie ma funkcji J
i:
(liczby od -n do n), działa to prawie tak samo jak odpowiedź J.Nie możemy korzystać z pociągu, ponieważ wykonanie
-\⍳2×⍵
polecenia „nie parsuj”(-\) ⍳ (2×⍵)
kosztuje trzy bajty; podobnie z inną parą atops. Wszystkie te nawiasy skracają normalną funkcję.Wypróbuj tutaj . Dane wyjściowe
1
oznaczają, że wszystkie wartości są zgodne.źródło
Matlab 41 bajtów
Jeszcze mniejszy niż poprzednie odpowiedzi
Zasadniczo odpowiedź Agawa001 z zastąpieniem power i sqrt
źródło
Candy ,
1714 bajtówDane wejściowe wypychane początkowo na stos
~TbAT1C(sWs+Aeh)Z
~T0C(sWs+Aeh)Z
źródło
CJam, 28
Niezbyt krótki, ale wydajny. Np. Wynik dla 15625 wynosi natychmiast 28. Wykorzystuje wzór oparty na faktoryzacji z OEIS.
Wypróbuj online
Wyjaśnienie:
Niektóre szczegóły dotyczące obliczeń:
(exponent + 1) & -1
, co jestexponent + 1
(exponent + 1) & 1
, która wynosi 0, jeśli wykładnik jest nieparzysty, a 1, jeśli parzystyWszystkie te wartości pomnożone razem i pomnożone przez 4 są dokładnie formułą OEIS.
źródło
Python 2, 68 bajtów
Definiuje wywoływaną funkcję,
x()
która przyjmuje liczbę n.Wypróbuj online. http://ideone.com/aRoxGF
źródło
print
lubreturn
.n=0
in=1
(0 i 2 zamiast 1 i 4). Może limity zasięgu wymagają dostosowania?n+1
.Pyth,
4135333027 bajtówWypróbuj online.
Edycja: Dzięki isaacg mam
m
i*F
do pracy! TAK!Edycja: włóż bit bit i wróć, aby uzyskać więcej oszczędności bajtów! Usunąłem też wszystkie „dawniej” rzeczy. Zaczynało się zagracać.
Dzięki aditsu i jego rozwiązaniu CJam oraz maltysen i jego wskazówkom (Pewnego dnia zabiorę się
m*Fd
do pracy. Pewnego dnia ...)Zauważ, że
jeśli liczbą pierwszą jest 1 mod 4, otrzymujemy
-1 & (exponent + 1)
, co jestexponent + 1
ale jeśli liczbą pierwszą jest 3 mod 4, otrzymujemy
1 & (exponent + 1)
, to znaczy,0
jeśli wykładnik jest nieparzysty, a1
nawet parzystyPomnóż to wszystko razem (razy 4 na początku), a otrzymamy sumę dwóch kwadratów, które składają się na nasz wkład.
źródło
Python, 57 bajtów
Niezłe wyzwanie. Niestety w tej chwili nie jestem krótszy.
źródło
PARI / GP,
3428 bajtówKorzystanie z funkcji generowania:
Zaoszczędź 6 bajtów dzięki Mitchowi Schwartzowi .
Przy użyciu wbudowanych 33 bajtów (zapisano 1 bajt dzięki Mitchowi Schwartzowi ):
źródło
matid(2)
zapisuje bajt.n->sum(i=-n,n,x^i^2)^2\x^n%x
Matlab, 72 bajty
źródło
disp
Luis! =)Matlab,
6350 bajtówTo pobija drugi kod o tym samym tytule, dlatego go umieszczam: D.
Program znajduje pozytywne rozwiązania liczb całkowitych, a następnie pomnoży je przez 4, aby objąć rozwiązania negatywne.
Może wykonać wszystkie 25 pierwszych przypadków testowych
źródło
disp
! =)format compact
=)JavaScript, 89 bajtów
Wiem, że nie jest to najkrótsza odpowiedź JavaScript, nawet gdybym usunęła linie we / wy, ale myślę, że jest to najlepiej działająca odpowiedź JS, dająca mi wynik za milion w ciągu kilku sekund (dziesięć milionów zajęło około minuta).
źródło
PHP, 70 bajtów, nie konkuruje
algorytm skradziony jednej z odpowiedzi w języku Python ... Zapomniałem, która z nich; chciałem przynajmniej częściowo zrozumieć, co się dzieje, zanim opublikowałem.
źródło
for(;$x<=$n=$argv[1];)$s+=(-($n%(2*$x+1)<1))**$x++*4;echo$n?$s:1;
zapisuje 5 bajtów.$x-~$x
jest równa2*$x+1
i możesz teraz rozpocząć bez przypisywania zmiennej.