Problem #47

2.203 seconds for it to complete on my computer. I had the loop check to 2 * sqrt(num), for checking for factors, because it didnt work correctly checking to just sqrt(num). Probably because something can be 2 * , so I tried to check all the way up to that, and the answer was correct.

#include <iostream>
#include <ctime>
#include <cmath>

using namespace std;

int countPrimeFactors (int);
bool isPrime (int);

int main() 
{
    clock_t start = clock();
    int total = 0;

    for (int i = 1; ; i++)
        if (countPrimeFactors (i) == 4)
            if (countPrimeFactors (i + 1) == 4)
                if (countPrimeFactors (i + 2) == 4)
                    if (countPrimeFactors (i + 3) == 4)
                    {
                        total = i;
                        break;
                    }
    cout << total << endl 
         << "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;

    system("pause");
    return 0;
}

int countPrimeFactors (int num)
{
    int holder = 0;

    for (int i = 1; i <= sqrt (static_cast<double> (num)) * 2; i++)
        if (num % i == 0)
            if (isPrime (i))
                holder++;
    return holder;
}

bool isPrime (int num)
{
    if (num <= 1)
        return false;
  
    if (num == 2 || num == 3)
        return true;

    for (unsigned int i = 2; i < static_cast<int> (sqrt (static_cast<double> (num))) + 1; i++)
        if (num % i == 0)
            return false;
   return true;
}

Problem #46

For this one, all I did was create an array of bools all the way up to 10000 that sets every number to false, then loops through every possibility of adding primes with two times a square, it then sets that value in the array to true. Then just checks for an odd number that is still false in the array. The first one must be what we are looking for.

#include <iostream>
#include <ctime>
#include <string>
#include <cmath>

#define MAX    10000

using namespace std;

int getNextPrime (int);
bool isPrime (int);

int main() 
{
    clock_t start = clock();
    long long int total = 0;
    bool numbers[MAX];

    for (int i = 0; i < MAX; i++)
        numbers[i] = false;

    for (int i = 1; ;i = getNextPrime (i))
    {
        if (i > MAX - 1)
            break;

        for (int j = 0; ;j++)
            if (i + 2 * j * j > MAX)
                break;
            else
                numbers[i + 2 * j * j] = true;
    }
    
    for (int j = 10; j < MAX; j++)
        if (numbers[j] == false)
            if (j % 2 == 1)
            {
                total = j;
                break;
            }

    cout << total << endl 
         << "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;

    system("pause");
    return 0;
}

int getNextPrime (int num)
{
    int holder = 0;

    for (int i = num + 1; ;i++)
        if (isPrime (i))
            return i;
}

bool isPrime (int num)
{
    if (num <= 1)
        return false;
  
    if (num == 2 || num == 3)
        return true;

    for (unsigned int i = 2; i < static_cast<int> (sqrt (static_cast<double> (num))) + 1; i++)
        if (num % i == 0)
            return false;
   return true;
}

Problem #45

This one took me a little bit. The first thing that should be realized is that every hexagonal number is a triangle number. Thus theres no need to check to make sure it is a hex if it is already a tri. Also, with the code I have, I start out with i being 144, because we already know that H(143) is what works, so we need one slightly larger than that to find the next number. My code runs to completion in 0.078 seconds.

#include <iostream>
#include <ctime>
#include <string>
#include <cmath>

//#define T(x) x * (x + 1) / 2
//#define iT(x) (sqrt(static_cast<double>(8 * x + 1)) - 1) / 2

//#define P(x) x * (3 * x - 1) / 2
#define iP(x) (sqrt(static_cast<double>(24 * x + 1)) + 1) / 6

#define H(x) x * (2 * x - 1)
//#define iH(x) (sqrt(static_cast<double>(8 * x + 1)) + 1) / 4

using namespace std;

bool findDeciaml (string);

int main() 
{
    clock_t start = clock();
    long long int total = 0;
    char buffer[256];
    string str;
    long long int holder = 0;

    for (long long int i = 143 + 1; ;i++)
    {
        holder = H(i);

        sprintf (buffer, "%f", iP(holder));
        str = buffer;
        if (!findDeciaml (str))
        {
                total = holder;
                break;
        }
    }

    cout << total << endl 
         << "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;

    system("pause");
    return 0;
}

bool findDeciaml (string str)
{
    bool found = false;
    for (int i = 0; i < str.size (); i++)
    {
        if (found == false)
        {
            if (str[i] == '.')
                found = true;
        }
        else
            if (str[i] - '0' > 0)
                return true;
    }
    return false;
}

Problem #43

I was kind of lazy with this, but finally got around to re-creating my code for it. Here it is, it runs in 4.187 seconds on my computer.

#include <iostream>
#include <ctime>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

bool isCompatible (string);
bool checkDivisibility (int, int, int, int);

int main() 
{
    clock_t start = clock();
    long long int total = 0;
    long long int holder = 0;
    string str;

    int num[]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    sort (num, num + 10);

    do {
        str.clear ();
        for (int i = 0; i < 10; i++)
            str += num[i] + '0';
        if (isCompatible (str))
        {
            holder = 0;
            for (int i = 0; i < 10; i++)
                holder += (str[str.size () - 1 - i] - '0') * pow (10, static_cast<double>(i));
            total += holder;
        }
    } while ( next_permutation (num, num + 10));


    cout << total << endl 
         << "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;

    system("pause");
    return 0;
}

bool isCompatible (string str)
{
    if ((str[3] - '0') % 2 == 0)
        if (((str[2] - '0') + (str[3] - '0') + (str[4] - '0')) % 3 == 0)
            if ((str[5] - '0') % 5 == 0)
                if (checkDivisibility (str[4] - '0', str[5] - '0', str[6] - '0', 7))
                    if (checkDivisibility (str[5] - '0', str[6] - '0', str[7] - '0', 11))
                        if (checkDivisibility (str[6] - '0', str[7] - '0', str[8] - '0', 13))
                            if (checkDivisibility (str[7] - '0', str[8] - '0', str[9] - '0', 17))
                                return true;
                            else
                                return false;
                        else
                            return false;
                    else
                        return false;
                else
                    return false;
            else
                return false;
        else
            return false;
    else
        return false;
}

bool checkDivisibility (int a, int b, int c, int d)
{
    if ((a * 100 + b * 10 + c) % d == 0)
        return true;
    return false;
}

Problem #97

This one I also did with Mathematica, just like the other one where they wanted the last ten digits, I just plugged the number into Mathematica, and took the last 10 digits.

Problem #56

The way I originally did this one was I made a table,in Mathematica, of all the possible solutions, I then used Notepad++ to place '+'s where I needed them, then finally back to Mathematica to do all of the addition and find the largest of all the values.

If I were to solve this one now, I would use a big integer library (like BigInteger or some other arbitrarily long integer library), then make a function that adds all of the digits together, keep track of the largest one in a variable, and run the loop, outputting the largest one when it is done.

Problem #48

I used mathematica for this one. I just summed everything up, the copied the last ten digits.

For[i = 1; j = 0, i <= 1000, i++, j += i^i]; j