View Single Post
Old 2020-09-20, 16:58   #3
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

1,531 Posts

Originally Posted by Till View Post
Hi all,
today I found something curious...

Let X(m) be the number of distinct quadratic residues mod m. (A023105 for m=2^n)
It says that there are floor(2^n+10)/6 quadratic residues mod 2^n.
Originally Posted by Till View Post
Let Y(m) be the number of n < m that can be expressed as a sum of 4 squares, but not by a sum of less than four squares. (A004015)

Then it appears that X(2^n) == Y(2^n) + 2 for all n.

A simple Java test program can be found here:
You need 4 squares for x iff x=4^e*(8*k+7) it is pretty old fact.
If you want the count for this for x<2^n then you can set e<=(n-3)/2, and for a given e you can choose k in exactly 2^(n-3-2*e) ways. So you need 4 squares for
2^(n-3)+2^(n-5)+2^(n-7)+... numbers and this is a geometric progression, its sum is roughly 2^n/6. So it looks like your conjecture is true.
Note that for any m Y(m) is "close" to m/6.
R. Gerbicz is offline   Reply With Quote