Algorithms

public class Solutions
{
    Dictionary<int, bool> matches = new Dictionary<int, bool>();
    int maxZ = 0;

    public bool? EvenSolutions(int z)
    {
        if (z > maxZ)
        {
            int maxY = (int)Math.Sqrt(z - 3);
            int maxX = (int)(Math.Sqrt(z - 1 / 3d));
            int n = 4;

            for (int x = 1; x < maxX; x++)
            {
                for (int y = 1; y < maxY && (n = 3 * x * x + y * y) <= z; y++)
                {
                    if (n > maxZ)
                    {
                        if (!matches.ContainsKey(n))
                            matches.Add(n, false);
                        else
                            matches[n] = !matches[n];
                    }
                }
            }

            maxZ = z;
        }

        return (matches.ContainsKey(z)) ? (bool?)matches[z] : null;
    }
}

#include <utility>
#include <array>
#include <algorithm>

template <unsigned int z>
size_t NumSolutions()
{
	typedef std::pair<unsigned int, unsigned int> Solution;
	std::array<Solution, z * z + 2 * z> All;

	std::generate(All.begin(), All.end(), 
		[]()->Solution{
		static unsigned int x = 0, y = 0;
		return y == z ? Solution(++x, y = 0) : Solution(x , ++y);});

	return std::count_if(All.begin(), All.end(), 
		[](const Solution& sol){return z == 3 * sol.first * sol.first + sol.second * sol.second;});
}

#include <utility>
#include <vector>
#include <algorithm>

typedef std::pair<unsigned int, unsigned int> Solution;

template <unsigned int z>
bool IsSolution(const Solution& sol)
{
	return z == 3 * sol.first * sol.first + sol.second * sol.second;
}

template <unsigned int z>
Solution Next()
{
	static unsigned int x = 0, y = 0;
	return y == z ? Solution(++x, y = 0) : Solution(x , ++y);
}

template <unsigned int z>
size_t NumSolutions()
{
	std::vector<Solution> All(z *z + 2 * z);
	std::generate(All.begin(), All.end(), Next<z>);
	return std::count_if(All.begin(), All.end(), IsSolution<z>);
}

#include <iostream>
int main()
{
	using std::cout;
	using std::endl;

	cout << "NumSolutions<4>(): " << NumSolutions<4>() << endl;
	cout << "NumSolutions<7>(): " << NumSolutions<7>() << endl;
	cout << "NumSolutions<28>(): " << NumSolutions<28>() << endl;
	return 0;
}

liquid_ wrote:

I wonder whether there is a more compact algorithm or maybe more efficient

#include <algorithm>
std::min_element(/* const Key* */ base, base + /*size_t*/ nElts /* = number of elements*/);

lbound(const void* key, void *base, unsigned int nmemb, unsigned int size, int (*compare)(const void *e1, const void *e2))

liquid_ wrote:

code is written in pure C and it should be just such - a more universal one.

liquid_ wrote:

What I tried to aim is logarithmic complexity.

p ^ 2 = 1 + 24 * (p - 6)

x<sup>2</sup> + x + 41