Quote:
Originally Posted by Till
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.
Quote:
Originally Posted by Till
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:
https://github.com/TilmanNeumann/jav...f4Squares.java

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<=(n3)/2, and for a given e you can choose k in exactly 2^(n32*e) ways. So you need 4 squares for
2^(n3)+2^(n5)+2^(n7)+... 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.