View Single Post
Old 2020-10-11, 18:11   #9
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

1B216 Posts
Default

For completeness I'ld like to add that it's more than counting.

For any n>2, we can obtain the values of A004215 (natural numbers representable by 4 squares but no less) < 2^n from the set of quadratic residues mod 2^n as follows (pseudocode):
Code:
computeA004215Mod2PowN(int n) {
    Set input = {quadratic residues modulo 2^n}; // the set of quadratic residues modulo 2^n
    Set output = new Set();
    for (qr in input) {
        output.add(2^n - qr);
    }
    output.remove(2^n);
    if (n is odd) {
        output.remove(2^(n-1));
    } else {
        output.remove(2^(n-1) + 2^(n-2));
    }
    return output;
}
Till is offline   Reply With Quote