Problem #50

This problem wasnt very hard, I pretty much do a brute force approach. I test 2, 2+3, 2+3+5, ..., 3, 3+5, 3+5+7, ..., 5, 5+7, ...

#include <iostream>
#include <cassert>
#include <cmath>

using namespace std;

bool isPrime (int);
void generatePrimes (bool*, int);

const int SIZE = 1000000;
bool primes[SIZE];

int main ()
{
    int sum = 0, seq = 0, highestSeq = 0, highestPrime = 0;
    generatePrimes (primes, SIZE);

    int iLimit = 1000000,
        jLimit = 1000000;

    for (int i = 0; i < iLimit; i++)
    {
        sum = 0;
        seq = 0;
        if (isPrime (i))
        {
            for (int j = i; j < jLimit; j+=2)
            {
                if (isPrime (j))
                {
                    sum += j;
                    seq++;
                }
                if (isPrime (sum))
                {
                    if (seq > highestSeq)
                    {
                        highestSeq = seq;
                        highestPrime = sum;
                    }
                }
                if (sum > 1000000)
                    break;
            }
        }
    }

    cout << "Highest prime: " << highestPrime << endl
         << "With a sequence of: " << highestSeq << endl;
    return 0;
}

// ----------------------------------------------------------------------------
// Check to see if a number is a prime number
// ----------------------------------------------------------------------------
bool isPrime (int num)
{
  assert (num >= 0);

  if (num >= SIZE)
  {
    if (num == 2)
      return true;
    if (num <= 2 || num % 2 == 0)
      return false;
    for (int i = 3; i < num / 2; i += 2)
      if (num % i == 0)
        return false;
    return true;
  }

  return primes[num];
}

// ----------------------------------------------------------------------------
// Generate a list of all of the primes numbers up to a specific limit.
// ----------------------------------------------------------------------------
void generatePrimes (bool *primes, int size)
{
  int pos = 2;

  primes[0] = false;
  primes[1] = false;

  for (int i = 2; i < size; i++)
    primes[i] = true;

  while (pos < size)
  {
    for (int i = 2; i * pos < size; i++)
      primes[i * pos] = false;
    pos++;
    while (primes[pos] == false && pos < size)
      pos++;
  }
}

Problem #49

Yeah, it has been a while since I've updated this blog, I havent been to Project Euler in a while, I've been busy with lots of other stuff, but, to all of my loyal readers (haha!), here's the solution to #49.

This code uses the Sieve of Erathosthenes to generate an array of primes to easy access. It then finds all of the permutations of a found prime number. It generates an adjacency matrix of distances from each prime to another prime, and uses a recursive function to parse through all of the possible paths, finding any path that has the same distances.

#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <sstream>
#include <set>

using namespace std;

bool isPrime (int);
void generatePrimes (bool*, int);

const int SIZE = 10000;
bool primes[SIZE];

struct pos
{
    int x;
    int y;
};
vector<pos> coords;

// ----------------------------------------------------------------------------
// Convert an integer to a vector. 12 becomes 0012
// ----------------------------------------------------------------------------
void numToVector (int num, vector<int> &v)
{
  v.clear ();

  stringstream ss;
  string tmp;

  ss << num;
  tmp = ss.str ();

  for (int i = tmp.size () - 1; i >= 0; i--)
    v.push_back (tmp[i] - '0');

  while (v.size () < 4)
    v.push_back (0);

  reverse (v.begin (), v.end ());

}

// ----------------------------------------------------------------------------
// Convert a vector to an integer.
// ----------------------------------------------------------------------------
int vectorToNum (vector<int> &v)
{
  int num = 0;

  for (int i = v.size () - 1; i >= 0; i--)
    num += v[i] * pow (10.0, (v.size () - 1) - i);

  return num;
}

// ----------------------------------------------------------------------------
// Generate all of the permutations of a prime number, that are also prime, and
// store them in a sorted manner.
// ----------------------------------------------------------------------------
void generatePermutationPrimes (int num, vector<int> &v)
{
  vector<int> tmp;
  numToVector (num, tmp);

  sort (tmp.begin (), tmp.end ());

  do {
    if (isPrime (vectorToNum (tmp)))
      v.push_back (vectorToNum (tmp));
  } while (next_permutation (tmp.begin (), tmp.end ()));

  sort (v.begin (), v.end ());
}

// ----------------------------------------------------------------------------
// This is a recursive function, it tests to see if a specific number (num) is
// in the adjacency matrix (matrix), with a connection to (pos). If it is, it
// increments the counter, and calls it's self to parse that new line with the
// same distance value.
// ----------------------------------------------------------------------------
void findNum (int num, int pos, vector< vector<int> > &matrix, int &counter)
{
  ::pos tmpPos;
  tmpPos.x = pos;
  counter++;
  for (int i = 0; i < matrix[pos].size (); i++)
  {
    if (matrix[pos][i] == num)
    {
      tmpPos.y = i;
      coords.push_back (tmpPos);
      findNum (matrix[pos][i], i, matrix, counter);
    }
  }
}

// ----------------------------------------------------------------------------
// This is the starting point for the recursive function. It does the initial
// loop through all of the rows in the matrix, passing each one to the findNum
// function. It then returns a string with the three numbers in it, or
// a string with "NaN" if no string was found.
// ----------------------------------------------------------------------------
string hasSequence (vector< vector<int> > &matrix, vector<int> &v)
{
  int counter = 0;
  stringstream output ("NaN");

  for (int i = 0; i < matrix.size (); i++)
  {
    for (int j = 0; j < matrix.size (); j++)
    {
      if (matrix[i][j] != 0)
      {
        coords.clear ();
        pos tmpPos;
        tmpPos.x = i;
        tmpPos.y = j;
        coords.push_back (tmpPos);
        counter = 0;
        findNum (matrix[i][j], j, matrix, counter);
        if (counter >= 2)
        {
          if ((v[coords[0].x] > 1000) &&
              (v[coords[0].y] > 1000) &&
              (v[coords[1].y] > 1000))
            output << v[coords[0].x] << " " << v[coords[0].y] << " " << v[coords[1].y];
        }
      }
    }
  }
  return output.str ();
}

// ----------------------------------------------------------------------------
// This creates an adjacency matrix for the number sequence stored in v. It
// then calls hasSequence, and returns the string that hasSequence returns.
// ----------------------------------------------------------------------------
string findSequence (vector<int> &v)
{
  vector< vector<int> > adjMatrix;

  adjMatrix.resize (v.size ());
  for (int i = 0; i < v.size (); i++)
    adjMatrix[i].resize (v.size ());

  for (int i = 0; i < adjMatrix.size (); i++)
    for (int j = 0; j < adjMatrix[i].size (); j++)
      adjMatrix[i][j] = 0;

  for (int i = 0; i < v.size () - 1; i++)
    for (int j = i + 1; j < v.size (); j++)
      adjMatrix[i][j] = abs (v[i] - v[j]);

  string seq = hasSequence (adjMatrix, v);
  return seq;
}

int main ()
{
  generatePrimes (primes, SIZE);

  set<string> results;
  for (int i = 1; i < 10000; i++)
  {
    if (isPrime (i))
    {
      vector<int> v;
      generatePermutationPrimes (i, v);

      if (v.size () >= 3)
      {
        string incSeq = findSequence (v);
        if (incSeq != "NaN")
            results.insert (incSeq);
      }
    }
  }

  cout << "Matches: " << endl;
  for (set<string>::iterator it = results.begin (); it != results.end (); it++)
    cout << (*it) << endl;

  return 0;
}

// ----------------------------------------------------------------------------
// Check to see if a number is a prime number
// ----------------------------------------------------------------------------
bool isPrime (int num)
{
  assert (num >= 0);

  if (num >= SIZE)
  {
    if (num == 2)
      return true;
    if (num <= 2 || num % 2 == 0)
      return false;
    for (int i = 3; i < num / 2; i += 2)
      if (num % i == 0)
        return false;
    return true;
  }

  return primes[num];
}

// ----------------------------------------------------------------------------
// Generate a list of all of the primes numbers up to a specific limit.
// ----------------------------------------------------------------------------
void generatePrimes (bool *primes, int size)
{
  int pos = 2;

  primes[0] = false;
  primes[1] = false;

  for (int i = 2; i < size; i++)
    primes[i] = true;

  while (pos < size)
  {
    for (int i = 2; i * pos < size; i++)
      primes[i * pos] = false;
    pos++;
    while (primes[pos] == false && pos < size)
      pos++;
  }
}

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.