Last active
July 8, 2024 07:00
-
-
Save Hermann-SW/18423ac08eda224dd06683883c7b10ac to your computer and use it in GitHub Desktop.
Representatins of n as sum of k squares (non-negative monotonic increasing, all, count)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
assert(b)=if(!(b),error()); | |
SquaresRepresentations(n,k,a=0)={ | |
my(R=List(),m=sqrtint(n\k)); | |
if(k==1,return(if(m>=a&&n==m^2,[m],[]))); | |
for(b=a,m,foreach(SquaresRepresentations(n-b^2,k-1,b),s,listput(R,concat([b],s)))); | |
Vec(R); | |
} | |
signs(a)={ | |
if(#a==0, | |
[[]], | |
[concat(s,v)|s<-Set([-a[1],a[1]]);v<-signs(a[2..#a])] | |
); | |
} | |
r3(n)=if(n%8==7,0,if(n%8==3,24*qfbclassno(-n),12*qfbclassno(-4*n))); | |
n=eval(getenv("n")); | |
k=eval(getenv("k")); | |
S=SquaresRepresentations(n,k); | |
{ | |
if(getenv("all"), | |
L=List(); | |
foreach(S,s, | |
forperm(s,p, | |
foreach(signs(Vec(p)),v,listput(L,v)) | |
); | |
); | |
if(getenv("all")=="count", | |
print("#(signed(permuted(elements)))=",#L); | |
if(k==3, | |
if(issquarefree(n), | |
assert(#L==r3(n)); | |
print("is equal to r3(n)"), | |
print("n not squarefree, so simple r3(n) cannot be used to compare") | |
) | |
), | |
print(Vec(L)); | |
), | |
print(S); | |
); | |
} |
Author
Hermann-SW
commented
Jul 6, 2024
Revision 4 did not work for n=100009, k=3 as well as for n=16, k-3 because simple r3(n)
https://en.wikipedia.org/wiki/Sum_of_squares_function#k_=_3
applies to squarefree n only. Revision 5 takes care of that:
hermann@j4105:~$ n=10009 k=3 all=count gp -q < SquaresRepresentations.gp
#(signed(permuted(elements)))=1152
is equal to r3(n)
hermann@j4105:~$ n=100009 k=3 all=count gp -q < SquaresRepresentations.gp
#(signed(permuted(elements)))=3456
n not squarefree, so simple r3(n) cannot be used to compare
hermann@j4105:~$
Revision 6:
vecmax(factorint(n)[,2])==1
-> issquarefree(n)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment