#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <fstream>
#include <string.h>
#include <stdlib.h>

#include "gmp.h"

using namespace std;

/*
	Case 1, 1, 2, 3, 5, 8, ...
		Step 1:
			s(x) = x + x^2 + x(s(x) - x) + x^2s(x)
			https://www.wolframalpha.com/input/?i=s(x)+%3D+x+%2B+x%5E2+%2B+x(s(x)+-+x)+%2B+x%5E2s(x)

		Step 2:
			k = x/(1 - x - x^2)
			https://www.wolframalpha.com/input/?i=solve+k+%3D+x%2F(1+-+x+-+x%5E2)+for+x

		Step 3:
			b^2 = sqrt(5k^2 + 2k + 1)

	Case 1, 2, 3, 5, 8, ...
		Step 1:
			s(x) = x + 2x^2 + x(s(x) - x) + x^2s(x)
			https://www.wolframalpha.com/input/?i=s(x)+%3D+x+%2B+2x%5E2+%2B+x(s(x)+-+x)+%2B+x%5E2s(x)

		Step 2:
			k = (x^2 + x)/(1 - x - x^2)
			https://www.wolframalpha.com/input/?i=solve+k+%3D+(x%5E2+%2B+x)%2F(1+-+x+-+x%5E2)+for+x

		Step 3:
			b^2 = sqrt(5k^2 + 6k + 1)

	Case 1, 3, 4, 7, 11, ...
		Step 1:
			s(x) = x + 3x^2 + x(s(x) - x) + x^2s(x)
			https://www.wolframalpha.com/input/?i=s(x)+%3D+x+%2B+3x%5E2+%2B+x(s(x)+-+x)+%2B+x%5E2s(x)

		Step 2:
			k = (2x^2 + x)/(1 - x - x^2)
			https://www.wolframalpha.com/input/?i=solve+k+%3D+(2x%5E2+%2B+x)%2F(1+-+x+-+x%5E2)+for+x

		Step 3:
			b^2 = sqrt(5k^2 + 10k + 1)

	Case 1, 4, 5, 9, 14, 23, ...
		Step 1:
			s(x) = x + 4x^2 + x(s(x) - x) + x^2s(x)
			https://www.wolframalpha.com/input/?i=s(x)+%3D+x+%2B+4x%5E2+%2B+x(s(x)+-+x)+%2B+x%5E2s(x)

		Step 2:
			k = (3x^2 + x)/(1 - x - x^2)
			https://www.wolframalpha.com/input/?i=solve+k+%3D+(3x%5E2+%2B+x)%2F(1+-+x+-+x%5E2)+for+x

		Step 3:
			b^2 = sqrt(5k^2 + 14k + 1)
*/

long long f() {
	long long k;
	mpz_t x, y;

	//Init
	mpz_init(x);
	mpz_init(y);

	for(k = 1; k < 1000000000; k++) {
		mpz_set_ui(x, 5);
		mpz_mul_ui(x, x, k);
		mpz_mul_ui(x, x, k);

		//mpz_set_ui(y, 2);
		//mpz_set_ui(y, 6);
		//mpz_set_ui(y, 10);
		//mpz_set_ui(y, 14);
		mpz_set_ui(y, 16);
		mpz_mul_ui(y, y, k);

		mpz_add(x, x, y);
		mpz_add_ui(x, x, 1);

		if(mpz_perfect_square_p(x) == 1)
			cout << k << endl;
	}

	return 0;
}

int check(mpz_t x, mpz_t y, long long k, int s) {
	mpz_set_ui(x, 5);
	mpz_mul_ui(x, x, k);
	mpz_mul_ui(x, x, k);

	mpz_set_ui(y, s);
	mpz_mul_ui(y, y, k);

	mpz_add(x, x, y);
	mpz_add_ui(x, x, 1);

	return mpz_perfect_square_p(x);
}

/*
	Data:
		3
		6
		30
		51
		216
		360
		1491
		2478
		10230
		16995
		70128
		116496
		480675
		798486
		3294606
		5472915
		22581576
		37511928
		154776435
		257110590
		1060853478
		1762262211
		7271197920
		12078724896
*/
long long f2() {
	long long k, m, s;
	mpz_t x, y;

	//Init
	mpz_init(x);
	mpz_init(y);
	k = 2;
	m = 2;
	s = 0;

	while(true) {
		if(check(x, y, k, 18) == 1) {
			cout << k << endl;
			//cout << k << " " << s << endl;

			//k -= s;
			//k *= m;

			//m = (m == 2) ? 183 : 2;
			//s = 0;
		}

		k++;
	}

	return 0;
}

int main() {
	cout << "Result = " << f2() << endl;

	return 0;
}