#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;
}
Friday, November 28, 2008
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.
Wednesday, November 26, 2008
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;
}
Tuesday, November 18, 2008
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.
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
Problem #42
This one was just a modification of the source code for a previous version.
#include <iostream>
#include <ctime>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int sum (string);
int main()
{
clock_t start = clock();
long int total = 0;
char ch;
ifstream fi;
vector<string> v;
bool table [100000];
for (unsigned int i = 0; i < 100000; i++)
table[i] = false;
for (unsigned int i = 0; ; i++)
if (static_cast<int>((1/static_cast<double> (2)) * static_cast<double> ((i + 1) * ((i + 1) + 1))) > 100000)
break;
else
table[static_cast<int>((1/static_cast<double> (2)) * static_cast<double> ((i + 1) * ((i + 1) + 1)))] = true;
fi.open ("words.txt");
while (!fi.eof ())
{
v.resize (v.size () + 1);
ch = fi.get ();
while (ch != ',' && !fi.eof ())
{
v[v.size () - 1] += ch;
ch = fi.get ();
}
}
for (unsigned int i = 0; i < v.size (); i++)
if (table[sum (v[i])] == true)
total++;
fi.close ();
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
int sum (string str)
{
int total = 0;
for (unsigned int i = 0; i < str.size (); i++)
if (isalpha (str[i]))
total += tolower (str[i]) - 96;
return total;
}
Problem #40
Heres #40. There are ways to speed this up, like loop through it all and count the numbers as they are found (instead of storing them all in a string), then when you have found the last one break out of the loop. That would save on memory, and speed, but I decided to go the easy way (and it runs to completion in 1.657 seconds, quick enough for me).
#include <iostream>
#include <string>
#include <ctime>
using namespace std;
int main()
{
clock_t start = clock();
int total = 0;
char buffer[32];
string str;
for (unsigned int i = 0; i < 1000000; i++)
{
sprintf (buffer, "%i", i);
str += buffer;
}
total = (str[1] - '0') * (str[10] - '0') * (str[100] - '0') * (str[1000] - '0') * (str[10000] - '0') * (str[100000] - '0') * (str[1000000] - '0');
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
Monday, November 17, 2008
Problem #36
#include <iostream>
#include <string>
#include <ctime>
#include <cmath>
#include <limits>
using namespace std;
bool isDecPal (int);
bool isBinPal (int);
string reverseString (string);
string cvt_binary(unsigned int);
int main()
{
clock_t start = clock();
int total = 0;
for (unsigned int i = 0; i < 1000000; i++)
if (isDecPal (i))
if (isBinPal (i))
total += i;
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
bool isDecPal (int num)
{
char buffer[32];
string str;
sprintf (buffer, "%i", num);
str = buffer;
if (str == reverseString (str))
return true;
return false;
}
bool isBinPal (int num)
{
string str;
str = cvt_binary (num);
if (str == reverseString (str))
return true;
return false;
}
string reverseString (string str)
{
string str2;
for (unsigned int i = 0; i < str.size(); i++)
str2 += str[str.size () - i - 1];
return str2;
}
string cvt_binary(unsigned int input)
{
string result;
if(input == 0)
return "0";
for(int i = numeric_limits<unsigned int>::digits - 1; i >= 0; i--)
if(input & (1 << i))
result += "1";
else
if(!result.empty())
result += "0";
return result;
}
Problem #34
Very closely related to the power of 5 one...was just a quick couple of modifications to that source code:
#include <iostream>
#include <string>
#include <ctime>
#include <cmath>
using namespace std;
unsigned int sumFactorialOfDigits (unsigned int);
int factorial (int);
int main()
{
clock_t start = clock();
int total = 0;
for (unsigned int i = 10; i < 1000000; i++)
if (i == sumFactorialOfDigits (i))
total += i;
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
unsigned int sumFactorialOfDigits (unsigned int num)
{
unsigned int total = 0;
char buffer[16];
string str;
sprintf (buffer, "%i", num);
str = buffer;
for (unsigned int i = 0; i < str.size (); i++)
total += factorial (str[i] - '0');
return total;
}
int factorial (int num)
{
int total = 1;
for (int i = 1; i <=num; i++)
total *= i;
return total;
}
Problem #30
Also quite simple of code:
#include <iostream>
#include <string>
#include <ctime>
#include <cmath>
using namespace std;
unsigned int sumFifthPowerOfDigits (unsigned int);
int main()
{
clock_t start = clock();
int total = 0;
for (unsigned int i = 10; i < 1000000; i++)
if (i == sumFifthPowerOfDigits (i))
total += i;
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
unsigned int sumFifthPowerOfDigits (unsigned int num)
{
unsigned int total = 0;
char buffer[16];
string str;
sprintf (buffer, "%i", num);
str = buffer;
for (unsigned int i = 0; i < str.size (); i++)
total += pow (static_cast<double> (str[i] - '0'), 5);
return total;
}
Problem #29
This is some elses solution, really short and simple. I am posting this instead of mine because mine was a long process using Notepad++, Mathematica, and C++. I used Mathematica to generate the tables, Notepad++ to split everything onto seperate lines, then C++ to read in the file, sort it, and delete any duplicates. It then output the total number of remaining elements.
#include <iostream>
#include <ctime>
#include <cmath>
#include <set>
using namespace std;
int main()
{
clock_t start = clock();
int total = 0;
set<double> answer;
for (double a = 2; a <= 100; a++)
for (double b = 2; b <= 100; b++)
answer.insert (pow (a, b));
total = answer.size ();
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
Problem #27
This one was fairly easy to reproduce:
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
bool isPrime (int);
int main()
{
clock_t start = clock();
int total = 0;
int holder = 0;
int count = 0;
for (int a = -999; a < 1000; a++)
for (int b = -999; b < 1000; b++)
{
count = 0;
for (int n = 0; ; n++)
if (isPrime (n * n + a * n + b))
count++;
else
break;
if (count > holder)
{
holder = count;
total = a * b;
}
}
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
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 #25
I use Mathematica for this. The original way I did it was with guess-and-check (e.g. is the 1000th one larger than it? no? how about the 5000th one? too large? ...). But, heres some Mathematica code that is a bit more efficient:
For[i = 0, 1000 > Length@IntegerDigits@Fibonacci@i, i++]; i
Problem #24
Another permutations problem. Rather simple...one problem was getting it to output, for some reason atoi (str.c_str ()) wasnt working correctly, so I just have it output the string instead.
#include <iostream>
#include <ctime>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
clock_t start = clock();
int total = 0;
int count = 0;
string str;
int holder[] = {0,1,2,3,4,5,6,7,8,9};
sort (holder,holder+10);
do {
count++;
if (count == 1000000)
{
for (unsigned int i = 0; i < 10; i++)
str += holder[i] + '0';
break;
}
} while ( next_permutation (holder,holder+10) );
cout << str << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
Problem #22
This takes the exact text file they give you as input, reads each name into a vector that it keeps resizing, then sorts the vector and sums up all the numerical values for the names.
#include <iostream>
#include <ctime>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int sum (string);
int main()
{
clock_t start = clock();
long int total = 0;
int count = 0;
char ch;
ifstream fi;
vector<string> v;
fi.open ("names.txt");
while (!fi.eof ())
{
v.resize (v.size () + 1);
count = 0;
ch = fi.get ();
while (ch != ',' && !fi.eof ())
{
v[v.size () - 1] += ch;
ch = fi.get ();
count++;
}
}
sort (v.begin (), v.end ());
for (unsigned int i = 0; i < v.size (); i++)
total += (i + 1) * sum (v[i]);
fi.close ();
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
int sum (string str)
{
int total = 0;
for (unsigned int i = 0; i < str.size (); i++)
if (isalpha (str[i]))
total += tolower (str[i]) - 96;
return total;
}
Problem #67
This just uses the source code for #18, just slightly modified to run with a larger file.
#include <iostream>
#include <ctime>
#include <fstream>
#define ROWS 100
using namespace std;
int main()
{
clock_t start = clock();
int total = 0;
unsigned int numbers[ROWS][ROWS];
ifstream fi;
fi.open("pyramid.txt");
for (int l=0;l<ROWS;l++)
for (int n=0;n<l+1;n++)
fi >> numbers[l][n];
fi.close ();
for (int l=ROWS - 2;l>=0;l--)
for (int n=0;n<l+1;n++)
if (numbers[l+1][n]>numbers[l+1][n+1])
numbers[l][n]+=numbers[l+1][n];
else numbers[l][n]+=numbers[l+1][n+1];
cout << numbers[0][0] << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
Problem #20
Very similar to the 2^1000 problem, simply one line in Mathematica:
Plus @@ IntegerDigits[100!]
Problem #18
I never did write code for this one...I just kind of looked at it and was able to spot the best possible route. I got it on my first try.
But, if you cannot do it on your own, here is a slightly modified version of someone elses code that works for finding the solution. When originally doing these, I think I used this code and modified it a bit farther to allow for solving the bigger triangle. The file pyramid.txt contains the pyramid, just copy/pasted from the page.
But, if you cannot do it on your own, here is a slightly modified version of someone elses code that works for finding the solution. When originally doing these, I think I used this code and modified it a bit farther to allow for solving the bigger triangle. The file pyramid.txt contains the pyramid, just copy/pasted from the page.
#include <iostream>
#include <ctime>
#include <fstream>
//#include <sstream>
using namespace std;
int main()
{
clock_t start = clock();
int total = 0;
unsigned int numbers[15][15];
ifstream fi;
fi.open("pyramid.txt");
for (int l=0;l<15;l++)
for (int n=0;n<l+1;n++)
fi >> numbers[l][n];
fi.close ();
for (int l=13;l>=0;l--)
for (int n=0;n<l+1;n++)
if (numbers[l+1][n]>numbers[l+1][n+1])
numbers[l][n]+=numbers[l+1][n];
else numbers[l][n]+=numbers[l+1][n+1];
cout << numbers[0][0] << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
Problem #17
For this one, I found someones code on Planet Source Code and modified it to add the number of characters, ignoring dashes and spaces, from 1 to 1000.
Problem #16
Quite simple in Mathematica (funny, this is exactly what someone else used in the thread for this problem).
Plus@@IntegerDigits[2^1000]
Problem #15
This one took me a while to figure out. I never actually wrote code for it (I wasnt sure how to do it exactly). But I was able to solve it mathematically using the pascals triangle (well, nCr that makes it up).
If you will notice, for a 1x1 block, there are 2 possible paths, for a 2x2 block, there are 6 possible paths, for a 3x3 block, there are 20 possible paths. if you will see, for an 'n' possible paths, it is the center of the 2n (if the first row is '0', second is '1', etc.). So, paths for n x n = (2n) C (n).
Thus, for a 1x1, it is 2 C 1.
nCr is defined as:
where
So, jumping up, we want the paths for a 20x20 grid:
(2 * 20) C (20)
40 C 20
Typing that into Mathematica (or a calculator) will give the correct answer.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
If you will notice, for a 1x1 block, there are 2 possible paths, for a 2x2 block, there are 6 possible paths, for a 3x3 block, there are 20 possible paths. if you will see, for an 'n' possible paths, it is the center of the 2n (if the first row is '0', second is '1', etc.). So, paths for n x n = (2n) C (n).
Thus, for a 1x1, it is 2 C 1.
nCr is defined as:
n!
------------
r! (n-r)!
where
n! = 1 * 2 * 3 * ... * (n - 2) * (n - 1) * n
So, jumping up, we want the paths for a 20x20 grid:
(2 * 20) C (20)
40 C 20
Typing that into Mathematica (or a calculator) will give the correct answer.
Problem #14
#include <iostream>
#include <ctime>
using namespace std;
int main()
{
clock_t start = clock();
int total = 0;
int temp;
int holder;
int count;
holder = 0;
for (unsigned int i = 1; i <= 1000000; i++)
{
temp = i;
count = 1;
while (i != 1)
if (i % 2 == 0)
{
i /= 2;
count++;
}
else
{
i = 3*i + 1;
count++;
}
if (count > holder)
{
holder = count;
total = temp;
}
i = temp;
}
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
Problem #13
For this one I just used Notepad++ to add +'s to the end of each line, then I copied and pasted the whole big long sum thing into Mathematica and had it calculate it for me, I then took the first ten digits and thats the answer.
Problem #12
This one took me a bit to re-create. I had to get it to work quickly, I was able to get it to run fairly quickly, it now runs to completion in just under three seconds on my computer.
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
int numberOfDivisors (int);
int main()
{
clock_t start = clock();
int total = 1;
int count = 1;
while (numberOfDivisors (total) < 500)
total += ++count;
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
int numberOfDivisors (int num)
{
int total = 0;
for (unsigned int i = 1; i <= sqrt (static_cast<double> (num)); i++)
if (num % i == 0)
if (i == sqrt (static_cast<double> (num)))
{
if (i * i == num)
total++;
}
else
total+=2;
return total;
}
Problem #11
Heres my code for solving this one. After writing this code and getting the solution I looked at the problem and found the solution on my own (the four numbers multiplied together to find it). Oh well, heres the code:
#include <iostream>
#include <ctime>
using namespace std;
int main()
{
clock_t start = clock();
int total = 0;
int holder[20][20] = {{ 8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8},
{49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0},
{81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65},
{52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91},
{22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
{24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
{32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
{67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21},
{24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
{21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95},
{78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92},
{16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57},
{86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
{19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40},
{ 4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
{88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
{ 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36},
{20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16},
{20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54},
{ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48}};
for(int i=0;i<20;i++)
{
for(int j=0;j<20;j++)
{
if(i<17)
if (total < holder[i][j] * holder[i+1][j] * holder[i+2][j] * holder[i+3][j])
total = holder[i][j] * holder[i+1][j] * holder[i+2][j] * holder[i+3][j];
if(j<17)
if (total < holder[i][j] * holder[i][j+1] * holder[i][j+2] * holder[i][j+3])
total = holder[i][j] * holder[i][j+1] * holder[i][j+2] * holder[i][j+3];
if(i>2 && i<17)
if(j>2 && j<17)
{
if (total < holder[i][j] * holder[i+1][j+1] * holder[i+2][j+2] * holder[i+3][j+3])
total = holder[i][j] * holder[i+1][j+1] * holder[i+2][j+2] * holder[i+3][j+3];
if (total < holder[i][j] * holder[i+1][j-1] * holder[i+2][j-2] * holder[i+3][j-3])
total = holder[i][j] * holder[i+1][j-1] * holder[i+2][j-2] * holder[i+3][j-3];
if (total < holder[i][j] * holder[i-1][j-1] * holder[i-2][j-2] * holder[i-3][j-3])
total = holder[i][j] * holder[i-1][j-1] * holder[i-2][j-2] * holder[i-3][j-3];
if (total < holder[i][j] * holder[i-1][j+1] * holder[i-2][j+2] * holder[i-3][j+3])
total = holder[i][j] * holder[i-1][j+1] * holder[i-2][j+2] * holder[i-3][j+3];
}
}
}
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
Problem #10
I had to make total a long long int to hold the value for this one hehe.
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
bool isPrime (int);
int main(void)
{
clock_t start = clock();
long long int total = 0;
int holder = 0;
while (holder < 2000000)
{
if (isPrime (holder))
total += holder;
holder++;
}
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
bool isPrime (int num)
{
if (num == 0 || 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 #9
#include <iostream>
#include <ctime>
using namespace std;
int main(void)
{
clock_t start = clock();
int total = 0;
for (unsigned int i = 1; i < 1000; i++)
for (unsigned int j = 1; j + i < 1000; j++)
if (i * i + j * j == (1000 - i - j) * (1000 - i - j))
total = i * j * (1000 - i - j);
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
Problem #8
#include <iostream>
#include <string>
#include <ctime>
using namespace std;
int main(void)
{
clock_t start = clock();
int total = 0;
int holder = 0;
string str = "\
73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450";
for (unsigned int i = 0; i < str.size () - 1 - 5; i++)
{
holder = (str[i] - '0') * (str[i + 1] - '0') * (str[i + 2] - '0') * (str[i + 3] - '0') * (str[i + 4] - '0');
if (holder > total)
total = holder;
}
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
Sunday, November 16, 2008
Problem #41
This one was actually quite easy.
#include <iostream>
#include <string>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
bool isPrime (int);
int main(void)
{
clock_t start = clock();
int total = 0;
string str;
int holder[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int holder2 = 0;
for (int j = 1; j <= 9; j++)
{
sort (holder, holder + j);
do {
str.clear();
for (unsigned int i = 0; i < j; i++)
str += holder[i] + '0';
holder2 = atoi (str.c_str());
if (isPrime (holder2))
if (holder2 > total)
total = holder2;
} while ( next_permutation (holder,holder+j) );
}
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
bool isPrime (int num)
{
if (num == 0 || 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 #44
I had to re do this one three different times because I kept messing it up lol.
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
unsigned long long int pent(unsigned long long int n);
bool ipent(unsigned long long int n);
int main(void)
{
clock_t start = clock();
int total = 0;
for (unsigned long long int i = 1; i < 3000; i++)
for (unsigned long long int j = 1; j < i; j++)
if (ipent(pent(i) + pent(j)))
if (ipent(pent(i) - pent(j)))
total = pent(i) - pent(j);
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system("pause");
return 0;
}
unsigned long long int pent(unsigned long long int n)
{
return n * (3 * n - 1) / 2;
}
bool ipent(unsigned long long int n)
{
if (floor((1 + sqrt(static_cast<double> (1 + 24 * n))) / 6) == ceil((1 + sqrt(static_cast<double> (1 + 24 * n))) / 6))
return true;
return false;
}
Problem #38
This one was rather simple, I just borrowed a bit of a function I wrote for another problem that required basically the same thing.
#include <iostream>
#include <string>
#include <ctime>
#include <cmath>
using namespace std;
bool isPrime (int);
bool isPentaganal (string);
int main()
{
clock_t start = clock();
int total = 0;
string str;
char buffer[32];
int holder = 0;
for (unsigned int i = 1; i < 1000000; i++)
{
str.clear();
for (unsigned int j = 1; j < 10; j++)
{
sprintf (buffer, "%i", i * j);
str += buffer;
if (str.size() == 9)
{
if (isPentaganal (str))
{
holder = atoi (str.c_str());
if (holder > total)
total = holder;
}
break;
}
else if (str.size() > 9)
break;
}
}
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system ("pause");
return 0;
}
bool isPrime (int num)
{
if (num == 0 || 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;
}
bool isPentaganal (string str)
{
bool found = false;
bool totalFound = true;
totalFound = true;
for (unsigned int i = 1; i <= 9; i++)
{
found = false;
for (unsigned int j = 0; j < str.size(); j++)
if (str[j] == i + '0')
{
found = true;
break;
}
if (found == false)
{
totalFound = false;
break;
}
}
return totalFound;
}
Problem #26
This one took me a bit, I could not write a program to get it to work. I eventually looked at the numbers and the lengths of the repeats, then I noticed that the larger the numbers, the larger the repeats, especially the prime numbers. I then used Mathematica to list some primes (Table[Prime[i],{i,100,200}]) and started at the highest prime under 1000. The third-highest prime worked.
Problem #7
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
bool isPrime (int);
int main()
{
clock_t start = clock();
int total = 0;
int count = 0;
int count2 = 0;
while (true)
{
if (isPrime (count))
count2++;
if (count2 == 10001)
{
total = count;
break;
}
else
count++;
}
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system ("pause");
return 0;
}
bool isPrime (int num)
{
if (num == 0 || 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 #6
#include <iostream>
#include <string>
#include <ctime>
#include <cmath>
using namespace std;
int main()
{
clock_t start = clock();
int total = 0;
int holder1 = 0;
int holder2 = 0;
for (unsigned int i = 1; i <= 100; i++)
{
holder1 += pow (static_cast<double> (i), 2);
holder2 += i;
}
total = pow (static_cast<double> (holder2),2) - holder1;
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system ("pause");
return 0;
}
Problem #5
I did this one by pencil and paper...I wrote out the prime factors for each number from 1 - 20, then took the largest power of each prime number and added them all together.
Problem #4
#include <iostream>
#include <string>
#include <ctime>
using namespace std;
bool isPalindromic (int);
string reverseString (string);
int main()
{
clock_t start = clock();
int total = 0;
for (unsigned int i = 100; i < 1000; i++)
for (unsigned int j = 100; j < 1000; j++)
if (isPalindromic (i * j))
if (i * j > total)
total = i * j;
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system ("pause");
return 0;
}
bool isPalindromic (int num)
{
char buffer[32];
string str;
sprintf (buffer, "%i", num);
str = buffer;
if (str == reverseString (str))
return true;
return false;
}
string reverseString (string str)
{
string str2;
for (unsigned int i = 0; i < str.size(); i++)
str2 += str[str.size () - i - 1];
return str2;
}
Problem #31
Heres my code at solving this problem...I also added a timer into the code to calculate how quickly it solves the problems, it solved this one in 0.078 seconds.
#include <iostream>
#include <ctime>
using namespace std;
int main()
{
clock_t start = clock();
int total = 0;
for (unsigned int i = 0; i <= 200; i++)
for (unsigned int j = 0; i + j * 2 <= 200; j++)
for (unsigned int k = 0; i + j * 2 + k * 5 <= 200; k++)
for (unsigned int l = 0; i + j * 2 + k * 5 + l * 10 <= 200; l++)
for (unsigned int m = 0; i + j * 2 + k * 5 + l * 10 + m * 20 <= 200; m++)
for (unsigned int n = 0; i + j * 2 + k * 5 + l * 10 + m * 20 + n * 50 <= 200; n++)
for (unsigned int o = 0; i + j * 2 + k * 5 + l * 10 + m * 20 + n * 50 + o * 100 <= 200; o++)
for (unsigned int p = 0; i + j * 2 + k * 5 + l * 10 + m * 20 + n * 50 + o * 100 + p * 200 <= 200; p++)
if (i * 1 + j * 2 + k * 5 + l * 10 + m * 20 + n * 50 + o * 100 + p * 200 == 200)
total++;
cout << total << endl
<< "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;
system ("pause");
return 0;
}
Problem #37
This one is kind of like the circular primes...quite simple really.
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
bool isPrime (int);
int truncLeft (int);
int truncRight (int);
bool checkLeft (int);
bool checkRight (int);
int main()
{
int total = 0;
for (unsigned int i = 10; i < 1000000; i++)
if (isPrime (i))
if (checkLeft (i) == true && checkRight (i) == true)
total+=i;
cout << total << endl;
system ("pause");
return 0;
}
bool isPrime (int num)
{
if (num == 0 || 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;
}
int truncLeft (int num)
{
char buffer[32];
string str, str2;
sprintf (buffer, "%i", num);
str = buffer;
str2 = str.substr (1);
return atoi (str2.c_str ());
}
int truncRight (int num)
{
char buffer[32];
string str, str2;
sprintf (buffer, "%i", num);
str = buffer;
str2 = str.substr (0, str.size () - 1);
return atoi (str2.c_str ());
}
bool checkLeft (int num)
{
while (num > 10)
{
num = truncLeft (num);
if (!isPrime (num))
return false;
}
return true;
}
bool checkRight (int num)
{
while (num > 10)
{
num = truncRight (num);
if (!isPrime (num))
return false;
}
return true;
}
Problem #39
This one was quite simple to think up the way to find the solution...even though this way is kind of slow (takes it about 20 seconds), it gets the job done. After writing it I thought that maybe doing something like problem 205 would be much quicker, but oh well, I already have this one done now haha.
#include <iostream>
#include <cmath>
using namespace std;
bool isATriangle (int, int, int);
int main()
{
int total = 0;
int count = 0;
int currTotal = 0;
int totalTotal = 0;
for (unsigned int p = 1; p <= 1000; p++)
{
currTotal = 0;
for (unsigned int c = 1; c < p; c++)
for (unsigned int a = 1; a < c; a++)
if (isATriangle (a, p - c - a, c))
currTotal++;
if (currTotal > totalTotal)
{
total = p;
totalTotal = currTotal;
}
}
cout << total << endl;
system ("pause");
return 0;
}
bool isATriangle (int a, int b, int c)
{
if (static_cast<int> (pow (static_cast<double> (a), 2)) + static_cast<int> (pow (static_cast<double> (b), 2)) == static_cast<int> (pow (static_cast<double> (c), 2)))
return true;
return false;
}
Problem #32
I avoided doing this one for quite some time because I didnt really know where to begin. But once I started it, it was fairly easy (got the correct answer on my first try).
#include <iostream>
#include <string>
using namespace std;
bool isThisANumberWeAreLookingFor (int, int, int);
int main()
{
int total = 0;
int fullList[32];
int count = 0;
// we want one times four, and two times three, so:
for (unsigned int i = 0; i < 100; i++)
for (unsigned int j = 100; j < 10000; j++)
if (isThisANumberWeAreLookingFor (i, j, i*j))
fullList[count++] = i * j;
else
{
// This is not the number you are looking for ... move along
}
for (unsigned int i = 0; i < count; i++)
for (unsigned int j = i + 1; j < count; j++)
if (fullList[i] == fullList[j])
fullList[j] = 0;
for (unsigned int i = 0; i < count; i++)
total += fullList[i];
cout << total << endl;
system ("pause");
return 0;
}
bool isThisANumberWeAreLookingFor (int a, int b, int c)
{
char buffer[16];
string str;
bool found = false;
bool totalFound = true;
sprintf (buffer, "%i%i%i", a, b, c);
str = buffer;
if (str.size() != 9)
return false;
totalFound = true;
for (unsigned int i = 1; i <= 9; i++)
{
found = false;
for (unsigned int j = 0; j < str.size(); j++)
if (str[j] == i + '0')
{
found = true;
break;
}
if (found == false)
{
totalFound = false;
break;
}
}
return totalFound;
}
Problem #35
Here is the code I wrote to solve problem 35. It is just a brute force attempt, it checks every number from [2, 1000000). If it is not a prime in any step, it is eliminated from the test and it goes on to test the next number, if not, it tests the next rotation of the number...quite simple really.
I did have to change the isPrime function to test up to the square root, rather than half of the number. It was really slowing down the process the way it was before, so this is a bit more efficient way of doing that.
I did have to change the isPrime function to test up to the square root, rather than half of the number. It was really slowing down the process the way it was before, so this is a bit more efficient way of doing that.
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
bool isPrime (int);
bool containsAZero (int);
int rotateOnce (int);
int main()
{
int total = 0;
int holder = 0;
bool prime = true;
for (unsigned int i = 2; i < 1000000; i++)
if (!containsAZero (i))
if (isPrime (i))
{
prime = true;
holder = i;
for (unsigned int j = 0; j < 6; j++)
{
holder = rotateOnce (holder);
if (!isPrime (holder))
{
prime = false;
break;
}
}
if (prime == true)
total++;
}
cout << total << endl;
system ("pause");
return 0;
}
bool isPrime (int num)
{
if (num == 1 || 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;
}
bool containsAZero (int num)
{
char buffer[16];
string str;
sprintf (buffer, "%i", num);
str = buffer;
for (unsigned int i = 0; i < str.size () - 1; i++)
if (str[i] == '0')
return true;
return false;
}
int rotateOnce (int num)
{
char buffer[16];
string str, str2;
sprintf (buffer, "%i", num);
str = str2 = buffer;
for (unsigned int i = 0; i < str.size() - 1; i++)
str[i] = str2[i+1];
str[str.size() - 1] = str2[0];
return atoi (str.c_str ());
}
Friday, November 14, 2008
What I am doing here and stuff
Well, I wanted to know how I solved a few of the previous problems that I solved, so I thought that posting my solutions from now on would be a good way to keep track of how I solved the problems.
I will post entries for the previous problems that I have solved (re-write the code).
I do not want to directly give out the answers to anyone, so I will not post what the programs will output when they run, but to find the answers it should be rather easy, just copy/paste the source code into a Code::Blocks or Microsoft Visual C++ project and compile/run.
I will post entries for the previous problems that I have solved (re-write the code).
I do not want to directly give out the answers to anyone, so I will not post what the programs will output when they run, but to find the answers it should be rather easy, just copy/paste the source code into a Code::Blocks or Microsoft Visual C++ project and compile/run.
Problem #33
Nothing too special...heres what I did to solve it:
#include <iostream>
#include <string>
using namespace std;
struct fraction
{
int numerator;
int denominator;
};
fraction factor (fraction);
int missingWhatNumber (int, int);
int main()
{
fraction fract, fract2, total;
// Because the fraction 49/98 -> 4/8 -> 1/2, and the program would not detect that, because it
// only looks at the 1/2, not that middle step. So I am using that as an initial value, since
// I already know that (it was given in the problem).
total.numerator = 4;
total.denominator = 8;
for (unsigned int i = 10; i < 100; i++)
for (unsigned int j = i + 1; j < 100; j++)
{
fract.numerator = i;
fract.denominator = j;
fract2 = factor (fract);
if (fract2.numerator != fract.numerator || fract2.denominator != fract.denominator)
if (missingWhatNumber (fract.numerator, fract2.numerator) == missingWhatNumber (fract.denominator, fract2.denominator) && missingWhatNumber (fract.numerator, fract2.numerator) != 0)
{
total.numerator *= fract2.numerator;
total.denominator *= fract2.denominator;
}
}
total = factor (total);
cout << total.denominator << endl;
system ("pause");
return 0;
}
fraction factor (fraction fract)
{
fraction newFract;
unsigned int goTo = 0;
unsigned int gcf = 0;
if (fract.numerator > fract.denominator)
goTo = fract.denominator;
else
goTo = fract.numerator;
if (fract.denominator == 0 || fract.numerator == 0)
{
// Nothing...
}
else
{
for (unsigned int i = 1; i <= goTo; i++)
if (fract.numerator % i == 0 && fract.denominator %i == 0)
gcf = i;
newFract.numerator = fract.numerator / gcf;
newFract.denominator = fract.denominator / gcf;
}
return newFract;
}
int missingWhatNumber (int a, int b)
{
string str1, str2;
char cString1[4], cString2[4];
sprintf (cString1, "%i", a);
sprintf (cString2, "%i", b);
str1 = cString1;
str2 = cString2;
// Ok, to make it easy on myself, I will assume that str1 contains
// 2 charactesr, and str2 contains 1 character. Bad coding practice to
// just assume something like that, but I will make sure thats all that is passed
// to it wherever it is used. If you plan to change anything in this
// program that might pass other stuff to it, then you may want to add in
// some error checking.
if (str2[0] == str1[0])
return (str1[1] - '0');
else if (str2[0] == str1[1])
return (str1[0] - '0');
else
return 0;
}
Thursday, November 13, 2008
Problem #19
Ok, first thing about solving this is that, since we are going from 1901 - 2000, we dont have to worry about any special leap year conditions, just that it is a leap year every year divisible by four (1904, 1908, 1912, ..., 2000).
I avoided doing this one for a while because I thought it would be hard...heres the code I wrote for it, solved it correctly on my first try.
I avoided doing this one for a while because I thought it would be hard...heres the code I wrote for it, solved it correctly on my first try.
#include <iostream>
#include <string>
using namespace std;
int daysPerMonth (int, int);
void addOneDay (string&);
int main()
{
string day = "Monday";
int total = 0;
for (unsigned int i = 1901; i < 2001; i++)
for (unsigned int j = 1; j <= 12; j++)
for (unsigned int k = 1; k <= static_cast<unsigned int> (daysPerMonth (j, i)); k++)
{
addOneDay (day);
if (k == 1 && day == "Sunday")
total++;
}
cout << total << endl;
system ("pause");
return 0;
}
// Returns the number of days in that month. If the month is february, it returns
// 29 iff the year is divisible by four
int daysPerMonth (int month, int year)
{
switch (month)
{
case 1:// Jan
return 31;
case 2:// Feb
if (year % 4 == 0)
return 29;
return 28;
case 3:// March
return 31;
case 4:// April
return 30;
case 5:// May
return 31;
case 6:// June
return 30;
case 7:// July
return 31;
case 8:// August
return 31;
case 9:// Sep
return 30;
case 10:// Oct
return 31;
case 11:// Nov
return 30;
case 12:// Dec
return 31;
default:// Error
return 0;
}
}
void addOneDay (string &day)
{
if (day == "Sunday")
day = "Monday";
else if (day == "Monday")
day = "Tuesday";
else if (day == "Tuesday")
day = "Wednesday";
else if (day == "Wednesday")
day = "Thursday";
else if (day == "Thursday")
day = "Friday";
else if (day == "Friday")
day = "Saturday";
else if (day == "Saturday")
day = "Sunday";
}
Problem #96
For this one, I used someone elses program and slightly modified it to check every one of them (I know...I didnt write my own, but I am a programmer and programmers are lazy, "If someone has already invented a wheel that works, why go and make your own wheel?"
It did not work on four of the sudoku's, so I used this javascript solver for those four.
Once I had the full list of digits, I used a simple macro in Notepad++ to add a plus between them all, then input it into Mathematica for the final answer.
For reference though:
It did not work on four of the sudoku's, so I used this javascript solver for those four.
Once I had the full list of digits, I used a simple macro in Notepad++ to add a plus between them all, then input it into Mathematica for the final answer.
For reference though:
483
245
462
137
523
176
143
487
814
761
976
962
397
639
697
361
359
786
743
782
428
425
348
124
361
581
387
345
235
298
761
132
698
852
453
516
945
365
134
193
814
384
469
316
586
954
159
861
294
351
Problem #53
This problem looked like it would be easiest with Mathematica. So thats what I used.
totalsum = 0;
For[i = 1, i <= 100, i++,
For[j = 1, j < i, j++,
If[Binomial[i, j] > 1000000, totalsum++];
];
];
Print[totalsum];
Problem #28
The majority of the work for this went to pencil-and-paper. I made a spiral 11x11, that gave me enough terms to create mathematical formulas for each of the directions. I then make a program to just calculate each of those directions outward until it got far enough.
#include <iostream>
#define MAX_SIZE_TO_GO_TO 1001
#define REALLY_SIZE_TO_GO (MAX_SIZE_TO_GO_TO + 1) / 2
using namespace std;
int equationOne (int);
int equationTwo (int);
int equationThree (int);
int equationFour (int);
int main()
{
unsigned long long int total = 0;
// Left-Down
total += equationOne (REALLY_SIZE_TO_GO);
// Left-Up
total += equationFour (REALLY_SIZE_TO_GO);
// Right-Up
total += equationTwo (REALLY_SIZE_TO_GO);
total--;
// Right-Down
total += equationThree (REALLY_SIZE_TO_GO);
cout << total << endl;
system("pause");
return 0;
}
int equationOne (int terms)
{
int totalSum = 0;
for (unsigned int i = 1; i <= terms; i++)
totalSum += (2*i - 2) * (2*i - 2) + 1;
return totalSum;
}
int equationTwo (int terms)
{
int totalSum = 0;
for (unsigned int i = 1; i <= terms; i++)
totalSum +=(2*i - 1) * (2*i - 1);
return totalSum;
}
int equationThree (int terms)
{
int placeHolder = 0;
int totalSum = 0;
placeHolder = 1;
for (unsigned int i = 1; i < terms; i++)
{
placeHolder = placeHolder + 2 + (i - 1) * 8;
totalSum += placeHolder;
}
return totalSum;
}
int equationFour (int terms)
{
int placeHolder = 0;
int totalSum = 0;
placeHolder = 1;
for (unsigned int i = 1; i < terms; i++)
{
placeHolder = placeHolder + (6 + (i - 1)*8);
totalSum += placeHolder;
}
return totalSum;
}
Problem #23
This one was rather easy, I just modified the code I used from Problem #21.
#include <iostream>
#define MAX_SIZE_TO_GO_TO 28123
using namespace std;
int sumDivisors (int);
bool isAbundant (int);
int main()
{
int total = 0;
int count = 0;
int allAbundantNumbers[MAX_SIZE_TO_GO_TO];
bool allNums[MAX_SIZE_TO_GO_TO];
for (unsigned int i = 0; i < MAX_SIZE_TO_GO_TO; i++)
allNums[i] = allAbundantNumbers[i] = false;
for (unsigned int i = 0; i < MAX_SIZE_TO_GO_TO; i++)
if (isAbundant (i))
{
allAbundantNumbers[count] = i;
count++;
}
for (unsigned int i = 0; i < count; i++)
for (unsigned int j = 0; j < count; j++)
if (allAbundantNumbers[i] + allAbundantNumbers[j] <= MAX_SIZE_TO_GO_TO)
allNums[allAbundantNumbers[i] + allAbundantNumbers[j]] = true;
for (unsigned int i = 0; i < MAX_SIZE_TO_GO_TO; i++)
if (allNums[i] == false)
total += i;
cout << total << endl;
system("pause");
return 0;
}
int sumDivisors (int num)
{
int total = 0;
for (unsigned int i = 1; i < static_cast<unsigned int> (num / 2 + 1); i++)
if (num % i == 0)
total += i;
return total;
}
// An abundant number is a number whos proper divisors sum higher than the number it's self
bool isAbundant (int num)
{
int total = 0;
total = sumDivisors (num);
if (total > num)
return true;
return false;
}
Problem #21
This one took me a bit...first I didnt notice that (6,6) (and others like that) are not pairs, the pairs have to be different numbers. Second I was only going up to 1000, not 10000, and third I was counting the number of pairs, not the sum of the numbers...but I eventually got it down. Heres the C++ code to solve this one:
#include <iostream>
using namespace std;
int sumDivisors (int);
int main()
{
int total = 0;
bool allNums[10000];
for (unsigned int i = 0; i < 10000; i++)
allNums[i] = false;
for (unsigned int i = 0; i < 10000; i++)
if (i == sumDivisors (sumDivisors (i)) && i != sumDivisors (i))
allNums[i] = allNums[sumDivisors (i)] = true;
for (unsigned int i = 0; i < 10000; i++)
if (allNums[i] == true)
total += i;
cout << total << endl;
system("pause");
return 0;
}
int sumDivisors (int num)
{
int total = 0;
for (unsigned int i = 1; i < static_cast<unsigned int> (num / 2 + 1); i++)
if (num % i == 0)
total += i;
return total;
}
Wednesday, November 12, 2008
Problem #205
Here's the code I used to solve Problem #205. Because I didnt want to have to go through the work of calculating the numbers in C++ (not sure if it would be easy or not) I just output the fraction. Just take the fraction and plug it into a calculator (Windows Calculator works fine)
#include <iostream>
using namespace std;
int main()
{
long long int total = 0;
int SixSidedNumbers[36];
int FourSidedNumbers[36];
for (unsigned int i = 0; i < 36; i++)
{
SixSidedNumbers[i] = 0;
FourSidedNumbers[i] = 0;
}
for (int i = 1; i < 5; i++)
for (int j = 1; j < 5; j++)
for (int k = 1; k < 5; k++)
for (int l = 1; l < 5; l++)
for (int m = 1; m < 5; m++)
for (int n = 1; n < 5; n++)
for (int o = 1; o < 5; o++)
for (int p = 1; p < 5; p++)
for (int q = 1; q < 5; q++)
FourSidedNumbers[i + j + k + l + m + n + o + p + q - 1]++;
for (int i = 1; i < 7; i++)
for (int j = 1; j < 7; j++)
for (int k = 1; k < 7; k++)
for (int l = 1; l < 7; l++)
for (int m = 1; m < 7; m++)
for (int n = 1; n < 7; n++)
SixSidedNumbers[i + j + k + l + m + n - 1]++;
for (unsigned int i = 0; i < 36; i++)
for (unsigned int j = 0; j < i; j++)
total += SixSidedNumbers[j] * FourSidedNumbers[i];
// 12230590464 comes from 262144 * 46656, which is the total possible combinations for all the dice rolls.
// 262144 = 4^9
// 46656 = 6^6
cout << total << " / " << "12230590464" << endl;
system("pause");
return 0;
}
Welcome
Welcome to my blog. I just thought that maybe I should post my solutions to Project Euler problems. I should have started when I first joined Project Euler, but I guess now is as good of a time as any.
I will post the code that I used to solve the problems on Project Euler here.
All code will be written as C++, Mathematica, or Pencil/Paper. Because those are the only three I use for solving the problems.
For C++, all code should be able to compile on Code::Blocks using the MingW GNU GCC compiler that comes with it.
I will post the code that I used to solve the problems on Project Euler here.
All code will be written as C++, Mathematica, or Pencil/Paper. Because those are the only three I use for solving the problems.
For C++, all code should be able to compile on Code::Blocks using the MingW GNU GCC compiler that comes with it.
Subscribe to:
Posts (Atom)
