Problem 92

Problem 92
Filename: prob92.cc

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

using namespace std;

typedef unsigned long long uint64_t;

uint64_t nextInChain(uint64_t num)
{
	char number[32];
	sprintf(number, "%llu", num);

	uint64_t next_in_chain = 0;
	for(int i=0; i<strlen(number); ++i)
		{
			const int digit = number[i]-48;
			next_in_chain += (digit*digit);
		}
	
	return next_in_chain;
}


int main()
{
	int num_ending_in_89 = 0;
	for(int i=1; i<10000000; ++i)
		{
			uint64_t working_num = i;
			while(working_num != 1 && working_num != 89)
				{
					working_num = nextInChain(working_num);
				}
			
			if(working_num == 89)
				{
					++num_ending_in_89;
				}
		}

	printf("answer: %d\n", num_ending_in_89);

	return 0;
}

---

syntax highlighted by Code2HTML, v. 0.9.1

Problem 68

Problem 68
Filename: prob68.cc

// Problem 68
// 
// Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine.
// 
// 
// Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.
// 
// It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.
// 
// Total	Solution Set
// 9	4,2,3; 5,3,1; 6,1,2
// 9	4,3,2; 6,2,1; 5,1,3
// 10	2,3,5; 4,5,1; 6,1,3
// 10	2,5,3; 6,3,1; 4,1,5
// 11	1,4,6; 3,6,2; 5,2,4
// 11	1,6,4; 5,4,2; 3,2,6
// 12	1,5,6; 2,6,4; 3,4,5
// 12	1,6,5; 3,5,4; 2,4,6
// By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.
// 
// Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a "magic" 5-gon ring?

#include <sstream>
#include <iostream>
#include <math.h>
#include <vector>
#include <stdio.h>

using namespace std;

static long long convertToULL(const string &src)
{
  long long output;
  stringstream converter(src);
  converter >> output;
  
  return output;
}

class fiveGon
{
public:
  fiveGon(const vector<int> &v)
  {
    c[0] = v[0];
    c[1] = v[1];
    c[2] = v[2];
    c[3] = v[3];
    c[4] = v[4];
    c[5] = v[5];
    c[6] = v[6];
    c[7] = v[7];
    c[8] = v[8];
    c[9] = v[9];
  }
  fiveGon(unsigned int c0,
	  unsigned int c1,
	  unsigned int c2,
	  unsigned int c3,
	  unsigned int c4,
	  unsigned int c5,
	  unsigned int c6,
	  unsigned int c7,
	  unsigned int c8,
	  unsigned int c9)
  {
    c[0] = c0;
    c[1] = c1;
    c[2] = c2;
    c[3] = c3;
    c[4] = c4;
    c[5] = c5;
    c[6] = c6;
    c[7] = c7;
    c[8] = c8;
    c[9] = c9;
  }

  string stringValue() const
  {
    string s("");

    int index = lowestStartingPoint();

    for(int i=0; i<5; ++i)
      {
	s+=getSetString(index);
	index = nextIndex(index);
      }
    
    return s;
  }

private:
  unsigned int c[10];

  int nextIndex(int index) const
  {
    return (index+1)%5;
  }

  string getSetString(int index) const
  {
    stringstream ss;

    if(index < 4)
      ss << c[index] << c[index+5] << c[index+6];
    else
      ss << c[4] << c[9] << c[5];

    return ss.str();
  }

public:
  bool isMagic() const
  {
    return (getSetValue(0) == getSetValue(1)) && 
      (getSetValue(1) == getSetValue(2)) && 
      (getSetValue(2) == getSetValue(3)) && 
      (getSetValue(3) == getSetValue(4));
  }

  int getSetValue(int index) const
  {
    if(index < 4)
      return c[index]+c[index+5]+c[index+6];
    else
      return c[4]+c[9]+c[5];
  }

  int lowestStartingPoint() const
  {
    int working_index = 0;
    if(c[working_index] > c[1]) working_index = 1;
    if(c[working_index] > c[2]) working_index = 2;
    if(c[working_index] > c[3]) working_index = 3;
    if(c[working_index] > c[4]) working_index = 4;
    return working_index;
  }

public:
  void print() const
  {
    cout << "\t\t\t " << c[0] << endl;
    cout << "\t\t\t\t\t" << c[1] << endl;
    cout << "\t\t\t\t" << c[5] << endl;
    cout << "\t\t\t" << c[9] << "\t\t " << c[6] << endl;
    cout << "\t\t" << c[4] << endl;
    cout << "\t\t\t  " << c[8] << "\t\t" << c[7] << "\t" << c[2] << endl;
    cout << "\t\t\t   " << c[3] << endl;

    cout << c[0] << " " << c[5] << " " << c[6] << " = " << getSetValue(0) << endl;
    cout << c[1] << " " << c[6] << " " << c[7] << " = " << getSetValue(1) << endl;
    cout << c[2] << " " << c[7] << " " << c[8] << " = " << getSetValue(2) << endl;
    cout << c[3] << " " << c[8] << " " << c[9] << " = " << getSetValue(3) << endl;
    cout << c[4] << " " << c[9] << " " << c[5] << " = " << getSetValue(4) << endl;

    cout << "Number: " << convertToULL(stringValue()) << endl;
  }

};

static inline vector<int> next(const vector<int> &v)
{
  vector<int> a(v);
  int n=v.size();
  int k;
  unsigned int l=0;
  for(k=n-2; 
      k>-1 && a[k] > a[k+1];
      --k)
    {			
    }
  
  for(l=n-1; a[k] > a[l]; --l)
    ;
  
  {
    const char temp = a[k];
    a[k] = a[l];
    a[l] = temp;
  }
  
  ++k;
  for(unsigned int i=0; k+i<n-i; ++i)
    {
      const char temp = a[k+i];
      a[k+i] = a[(n-1)-i];
      a[(n-1)-i] = temp;
    }

  return a;
}

//static void print(const vector<int> &v)
//{
//  for(vector<int>::const_iterator i = v.begin();
//      i != v.end();
//      ++i)
//    {
//      printf("%d%c", *i, i+1 != v.end() ? '.' : '\n');
//    }
//}

int main()
{
  vector<int> v;

  for(int i=1; i<=10; ++i)
    {
      v.push_back(i);
    }

  long long max = -1;

  for(int i=0; i<3300000; ++i)
    {
      fiveGon f(v);
      if(f.isMagic())
	{
	  string s(f.stringValue());
	  if(s.length() == 16)
	    {
	      if(convertToULL(s) > max)
		{
		  max = convertToULL(s);
		}
	    }
	}
      v=next(v);
    }

  cout << "answer: " << max << endl;

  return 0;
} 

---

syntax highlighted by Code2HTML, v. 0.9.1

Problem 43

Problem 43
Filename: prob43.cc

// Prob 43
#include <stdio.h>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

typedef long long unsigned int LLUINT;
typedef unsigned int UINT;

LLUINT toLLUINT(const string &num)
{
	LLUINT x;
	istringstream(num) >> x;
	return x;
}

string toString(UINT n)
{
	string s;
	stringstream out;
	out << n;
	s = out.str();

	if(s.length() == 2)
		{
			s.insert(0, "0");
		}

	return s;
}

UINT nextNum(UINT first_digit, const string &working_pandigital_number)
{
	string fd = toString(first_digit);
	string new_pd = fd+working_pandigital_number;
	UINT numb;
	istringstream(new_pd.substr(0, 3)) >> numb;
	return numb;
}

bool isSuitable(UINT n, const string &working_pandigital_number)
{
	string running_working_pandigital_number_copy(working_pandigital_number);
	const string s = toString(n);
	const int original_length = running_working_pandigital_number_copy.length();
	
	for(string::const_iterator it=s.begin(); it!=s.end(); ++it)
		{
			running_working_pandigital_number_copy.push_back(*it);
		}

	sort(running_working_pandigital_number_copy.begin(), running_working_pandigital_number_copy.end());
	string::iterator new_end = unique(running_working_pandigital_number_copy.begin(), running_working_pandigital_number_copy.end());
	
	running_working_pandigital_number_copy.erase(new_end, running_working_pandigital_number_copy.end());

	return running_working_pandigital_number_copy.length() == (original_length + s.length());
}

string addLastDigit(const string &num)
{
	string digits="0123456789";

	for(string::const_iterator i = num.begin();
		i!=num.end();
		++i)
		{
			for(string::iterator j = digits.begin();
				j!=digits.end();
				++j)
				{
					if(*j==*i)
						{
							digits.erase(j);
							break;
						}
				}
		}

	string new_num(num);
	new_num.insert(0, digits);
	return new_num;
}

void outputPandigitals(const vector<string> &wp)
{
	printf("######################\n");
	for(vector<string>::const_iterator working_pandigital_number=wp.begin();
		working_pandigital_number!=wp.end();
		++working_pandigital_number)
		{
			printf("\t%s\n", (*working_pandigital_number).c_str());
		}
}

int main()
{
	vector<string> working_pandigitals;
	vector<UINT> divisors;
	divisors.push_back(13);
	divisors.push_back(11);
	divisors.push_back(7);
	divisors.push_back(5);
	divisors.push_back(3);
	divisors.push_back(2);

	for(UINT i=17; i < 1000; i+=17)
		{
			string working_pandigital_number("");
			if(isSuitable(i, working_pandigital_number))
				{	
					const string s17(toString(i));
					for(string::const_iterator it = s17.begin(); it != s17.end(); ++it)
						{
							working_pandigital_number.push_back(*it);
						}
					working_pandigitals.push_back(working_pandigital_number);
				}
		}

	for(vector<UINT>::const_iterator divisor=divisors.begin(); divisor!=divisors.end(); ++divisor)
		{
			vector<string> new_working_pandigitals;
			for(vector<string>::const_iterator working_pandigital_number=working_pandigitals.begin(); 
				working_pandigital_number!=working_pandigitals.end(); 
				++working_pandigital_number)
				{
					for(UINT i=0; i<10; ++i)
						{
							string temp_working_pandigital_number(*working_pandigital_number);
							UINT new_num = nextNum(i, temp_working_pandigital_number);
							//							printf("i: %d nn: %d divisor: %d\n", i, new_num, *divisor);
							if((new_num%(*divisor) == 0) && isSuitable(i, temp_working_pandigital_number))
								{
									//									printf("\t\tbefore twpn: %s\n", temp_working_pandigital_number.c_str());
									temp_working_pandigital_number.insert(0, toString(i));
									//									printf("\t\tafter  twpn: %s\n", temp_working_pandigital_number.c_str());
									new_working_pandigitals.push_back(temp_working_pandigital_number);
								}
						}
				}
			working_pandigitals = new_working_pandigitals;
		}

	LLUINT result(0);
	for(vector<string>::const_iterator working_pandigital_number=working_pandigitals.begin();
		working_pandigital_number!=working_pandigitals.end();
		++working_pandigital_number)
		{
			result += toLLUINT(addLastDigit(*working_pandigital_number));
		}


	printf("answer: %llu\n", result);
}

---

syntax highlighted by Code2HTML, v. 0.9.1

Problem 63

Problem 63
Filename: prob63.cc

#include <stdio.h>
#include <math.h>
#include <list>
#include <string.h>

using namespace std;

int digits(double num)
{
	char decimal[512];
	sprintf(decimal, "%lf", num);
	if(strcmp(decimal, "inf") == 0) return -1;

	char *pch = strtok (decimal,".");
	return strlen(decimal);
}

//long long power(int base, int exponent)
//{
//	long long result = 1;
//	for(int i=0; i<exponent; ++i)
//		{
//			const long long prev_result = result;
//			result *= base;
//			if(prev_result > result && base != 0) return -1;
//		}
//
//	return result;
//}

int main()
{
	list<long long>l;
	for(int n=0; digits(pow(2,n)) != -1; ++n)
		{
//			printf("pow(2,%d): %lf\n", n, pow(2,n));
//			printf("digits(pow(%d,%d)) : %d     n : %d     pow(%d,%d): %lf\n", 0, n, digits(pow(0,n)), n, 0, n, pow(0,n));
			for(int x=0; x<10; ++x)
				{
					//					printf("digits(pow(%d,%d)) : %d     n : %d     pow(%d,%d): %lf\n", x, n, digits(pow(x,n)), n, x, n, pow(x,n));
					if(digits(pow(x,n)) == n) 
						{
							l.push_back(pow(x,n));
							printf("x: %d, n: %d\n\tdigits(pow(x,n)): %d\n\tpow(x,n): %lf\n", x, n, digits(pow(x,n)), pow(x,n));
						}
				}
		}
	
	l.sort();
	l.unique();

	printf("answer: %d\n", l.size());

	return 0;
}

---

syntax highlighted by Code2HTML, v. 0.9.1

Problem 58

Problem 58
Filename: prob58.cc

// Problem 58
//
//Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.
//
//37 36 35 34 33 32 31
//38 17 16 15 14 13 30
//39 18  5  4  3 12 29
//40 19  6  1  2 11 28
//41 20  7  8  9 10 27
//42 21 22 23 24 25 26
//43 44 45 46 47 48 49
//
//  It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13  62%.
//
//																							   If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?
//

#include <stdio.h>
#include <math.h>


static bool isPrime(const unsigned int n)
{
  if(n==2 || n== 3)
    {
      return true;
    }

  // short cuts to reduce search space
  if((n-1)%6 != 0 &&
     (n+1)%6 != 0)
    {
      return false;
    }

  for(unsigned int i=3; i<=ceil(sqrt(n)); i+=2)
    {
      if(n%i == 0)
        {
          return false;
        }
    }

  return true;
}


int main()
{
  unsigned int num_primes = 8;

  unsigned int ne=31;
  unsigned int ne_inc=26;

  unsigned int nw=37;
  unsigned int nw_inc=28;

  unsigned int sw=43;
  unsigned int sw_inc=30;

  unsigned int se=49;
  unsigned int se_inc=32;

  unsigned int side_length = 7;
  
  while((float)num_primes/(float)((side_length*2)-1) > 0.10)
    {
      side_length+=2;
      
      ne+=ne_inc;
      if(isPrime(ne)) ++num_primes;
      ne_inc+=8;
      
      nw+=nw_inc;
      if(isPrime(nw)) ++num_primes;
      nw_inc+=8;
      
      sw+=sw_inc;
      if(isPrime(sw)) ++num_primes;
      sw_inc+=8;
      
      se+=se_inc;
      if(isPrime(se)) ++num_primes;
      se_inc+=8;
      
      //      printf("%f\n", (float)num_primes/(float)((side_length*2)-1));
    }
  
  printf("answer: %d\n", side_length);

  return 0;
}

---

syntax highlighted by Code2HTML, v. 0.9.1

Problem 56

Problem 56
Filename: prob56.hs

-- Problem 56

-- A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
-- 
-- Considering natural numbers of the form, ab, where a, b  100, what is the maximum digital sum?

import Char
digitalSum a b = sum(map digitToInt (show(a^b)))
maxDigitalSum x = maximum(map (digitalSum x) [1..100])
answer = maximum(map maxDigitalSum [1..100])

---

syntax highlighted by Code2HTML, v. 0.9.1

Problem 49

Problem 49
Filename: prob49.cc

// Problem 49
// 
// The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
// 
//   There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
// 
// What 12-digit number do you form by concatenating the three terms in this sequence?

#include <iostream>
#include <math.h>
#include <sstream>
#include <vector>
#include <algorithm>
#include <stdio.h>

#define LB 1001
#define UB 10000

using namespace std;

static bool isPrime(const unsigned int n)
{
  if(n%2 == 0) return false;
  
  for(int i=3; i<=ceil(sqrt(n)); i+=2)
    {
      if(n%i == 0)
	{
	  return false;
	}
    }
  
  return true;
}

static string toString(const unsigned int n)
{
  stringstream out;
  out << n;
  return out.str();
}

static unsigned int toInt(char c)
{
  return c-48;
}

static vector<int> toVector(short a)
{
  vector<int> v;

  string sa(toString(a));

  for(string::const_iterator i = sa.begin();
      i != sa.end();
      ++i)
    {
      
      v.push_back(toInt(*i));
    }

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

  return v;
}

static bool isPermute(short a, short b)
{
  vector<int> va = toVector(a);
  vector<int> vb = toVector(b);

  return va == vb;
}

int main()
{
  vector<int> primes;
  primes.push_back(2);
  for(int i=LB; i<UB; i+=2)
    {
      if(isPrime(i))
	{
	  primes.push_back(i);
	} 
    } 

  const vector<int> primes2 = primes;
  const vector<int> primes3 = primes;

  for(vector<int>::const_iterator i = primes.begin();
      i!=primes.end();
      ++i)
    {
      for(vector<int>::const_iterator j = primes2.begin();
	  j!=primes2.end();
	  ++j)
	{
	  if(*i < *j && isPermute(*i, *j))
	    {
	      int diff = *j-*i;
	      if(*j+diff < 10000 && isPrime(*j+diff) && isPermute(*j, *j+diff))
		{
		  printf("%d %d %d\n", *i, *j, *j+diff);
		}
	    }
	}      
    }

  return 0;
}
 

---

syntax highlighted by Code2HTML, v. 0.9.1