/* @author Connor Guerin
 * @date February 23, 2017
 * @purpose Question 5 of homework #5
 */

#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

long evenLucasSum(int n);

long long * firstDDigitLucas(int d);

int main() {
	cout << "--- Question 5a ---" << endl;

	//Runs evenLucasSum() (Question 5a)
	cout << "Value for N:" << endl;
	int n;
	cin >> n;
	cout << "Sum of even numbers in Lucas Sequence of " << n << " + 1 numbers: ";
	cout << evenLucasSum(n) << endl;

	cout << "--- Question 5b ---" << endl;

	//Runs firstDDigitLucas() (Question 5b)
	cout << "Value for D:" << endl;
	int d;
	cin >> d;
	long long * result;
	//result[0] is index, resut[1] is the value at that index
	result = firstDDigitLucas(d);
	cout << "First value with " << d << " digits occurs at index " << result[0] << " and has a value of " << result[1] << endl;
}

//Question 5a
long evenLucasSum(int n) {
	long lucasSequence[n + 1];

	//Creates the Lucas Sequence
	lucasSequence[0] = 2;
	lucasSequence[1] = 1;
	for (int i = 2; i < n + 1; i ++) {
		lucasSequence[i] = lucasSequence[i - 1] + lucasSequence[i - 2];
	}

	//Sums all even numbers in Sequence
	long sum = 0;
	for (int i = 0; i < n + 1; i ++) {
		//Checks if number is even
		if (lucasSequence[i] % 2 == 0) {
			sum += lucasSequence[i];
		}
	}

	return sum;
}

//Question 5b
long long * firstDDigitLucas(int d) {
	//Creates a Lucas sequence to build on
	vector<long long> lucasSequence = {2, 1};

	//Creates an array to store return values
	//result[0] is index, resut[1] is the value at that index
	long long result[2];
	long long * pointResult = result;

	//Searches the sequence for the first number with d digits
	int index = 0;
	int digitCompare  = pow(10, d - 1);
	bool indexFound = false;
	while (indexFound == false) {
		//Checks if the value at index has d digits
		if ((lucasSequence[index] / digitCompare) >= 1) {
			result[0] = index;
			result[1] = lucasSequence[index];
			indexFound = true;
		}
		else {
			//Adds to the Lucas Sequence
			if (index == lucasSequence.size() - 1) {
				lucasSequence.push_back(lucasSequence.at(index) + lucasSequence.at(index - 1));
				//Used for debugging
				//cout << "Added: " << lucasSequence[index] << endl;
			}
			index ++;
		}
	}

	return pointResult;
}