Problem #20

n! means n × (n − 1) × ... × 3 × 2 × 1

Find the sum of the digits in the number 100!

Ytterligare en utmaning där det handlar om stora tal. I Python behöver man inte anstränga sig särskilt mycket ^^ (länk till problemet här)

#!/usr/bin/env python

def factorial(n):
  if n == 0: return 1
  else: return n * factorial(n - 1)

x = factorial(100)
a = 0
while x > 0:
  a += x % 10;
  x /= 10

print "Answer is %d" % a

Nästa blir problem 25.

Problem #16

What is the sum of the digits of the number 2^1000?

Här fick det bli en riktig snabblösning, Python hanterar stora tal utan att jag behöver tänka på vilken datatyp som gäller. En mer elegant lösning skulle vara att göra en egen binär till decimal snurra och addera sifforna under tiden talet byter talbas.

#!/usr/bin/env python

a = 2**1000
sum = 0

while a > 0:
 sum += a % 10
 a /= 10

print "Answer is %d" % sum

Problem #9

Den här var rolig, jag tog hjälp av denna Wiki-artikel ang. Pythagorean triplets för att generera alla möjliga triplets. Länk till problemet här.

#include <iostream>

template <typename T>
T triplet_sum(T k, T m, T n, T &product)
{
  T a = k * (2 * m * n);
  T b = k * ((m * m) - (n * n));
  T c = k * ((m * m) + (n * n));
  product = a * b * c;
  return a + b + c;
}

int problem9()
{
  int p; 
  for (int k = 1; k < 100; ++k)
    for (int n = 1; n < 100; ++n)
      for (int m = n + 1; m < 100; ++m)
        if (triplet_sum(k, m, n, p) == 1000)
          return p;
}

int main(int argc, char *argv[])
{
  std::cout << "Answer is " << problem9() << std::endl;
  return 0;
}

Nej, dags för kvällsfika. Gabriellas muffins och O'boy!

Problem #10

Calculate the sum of all the primes below two million.

Inte så elegant lösning, transportsträcka.

#include <iostream>
#include <cmath>

template <typename T>
inline bool is_prime(T p)
{
  if (p == 1)
    return false;

  if (p == 2)
    return true;

  if (!(p & 1))
    return false;

  for (T i = 2; i < sqrt(p) + 1; ++i)
    if (!(p % i))
      return false;
  return true;
}

int main(int argc, char *argv[])
{
  uint64_t prime_sum = 0;
  for (uint64_t i = 0; i < 2000000; ++i)
    if (is_prime(i))
      prime_sum += i;
  std::cout << "Answer is " << prime_sum << std::endl;
  return 0;
}

Problem #14

Här kommer min lösning till problem 14. Här stötte jag på problem då mina 32-bit int's inte räckte till på min plattform. Därav uint64_t, då talet växte till ganska stora tal (dvs större än 4294967296).

#include <iostream>
#include <utility>

template <typename T>
inline T next_seq(T n)
{
  return n & 1 ? (n * 3) + 1 : n / 2;
}

template <typename T>
inline T chain_length(T n)
{
  T i;
  for (i = 1; n != 1; ++i)
    n = next_seq(n);
  return i;
}

int main(int argc, char *argv[])
{
  std::pair<int64_t, uint64_t> chain_pair;
  for (uint64_t i = 2; i < 1000000; ++i)
  {
    uint64_t len = chain_length(i);
    if (len > chain_pair.first)
      chain_pair = std::make_pair(len, i);
  }

  std::cout << "Answer is "
            << chain_pair.first
            << " for n = "
            << chain_pair.second
            << std::endl;

  return 0;
}

Det finns en ganska bra optimering att göra in chain_length() genom att ha en hashtabell med n som nyckel och längden som värde för att inte göra onödigt jobb. Men med brute force på min MacBook går det <1s så det känns ganska onödigt.

Godnatt! Snart dags för en ny arbetsvecka.

Unix timestamp 1234567890

... har precis inträffat! Det är ett stort ögonblick. :D

Problem #8

Find the greatest product of five consecutive digits in the 1000-digit number.

Nästan för enkel:

#include <iostream>

char nums[] = {
  "73167176531330624919225119674426574742355349194934"
  "96983520312774506326239578318016984801869478851843"
  "85861560789112949495459501737958331952853208805511"
  "12540698747158523863050715693290963295227443043557"
  "66896648950445244523161731856403098711121722383113"
  "62229893423380308135336276614282806444486645238749"
  "30358907296290491560440772390713810515859307960866"
  "70172427121883998797908792274921901699720888093776"
  "65727333001053367881220235421809751254540594752243"
  "52584907711670556013604839586446706324415722155397"
  "53697817977846174064955149290862569321978468622482"
  "83972241375657056057490261407972968652414535100474"
  "82166370484403199890008895243450658541227588666881"
  "16427171479924442928230863465674813919123162824586"
  "17866458359124566529476545682848912883142607690042"
  "24219022671055626321111109370544217506941658960408"
  "07198403850962455444362981230987879927244284909188"
  "84580156166097919133875499200524063689912560717606"
  "05886116467109405077541002256983155200055935729725"
  "71636269561882670428252483600823257530420752963450"
};

int main(int argc, char *argv[])
{
  for (size_t i = 0; i < sizeof(nums); ++i)
    nums[i] -= '0'; // Just convenience

  int largest_product = 0;
  for (size_t i = 0; i < sizeof(nums) - 5; ++i)
  {
    int p = nums[i]*nums[i+1]*nums[i+2]*nums[i+3]*nums[i+4];
    largest_product = std::max(p, largest_product);
  }

  std::cout << "Answer is " << largest_product << std::endl;
  return 0;
}

Problem 7: Find the 10001st prime.

Problem #7 var lite tråkigt. Min is_prime() är inte optimal direkt. Följande fakta borde ha implementerats också:

• 1 är inte ett primtal.


• Alla primtal utom 2 är udda.


• Givet n kan bara ha en primtalsfaktor större än sqrt(n).

Min lösning:

#include <iostream>

template <typename T>
inline bool is_prime(T p)
{
  for (T i = 2; i < p; ++i)
    if (!(p % i))
      return false;
  return true;
}

int main(int argc, char *argv[])
{
  int n = 10001; 
  for (int pnum = 0, i = 2;; ++i)
  {
    if (is_prime(i))
    {
      pnum++;
      if (pnum == n)
      {
        std::cout << "Answer is " << i << std::endl;
        return 0;
      }
    }
  }
}

Godnatt!

Problem #6

Hade redan öppnat sidan för problem #6 i browsern...

#include <iostream>

template <typename T>
T sum_square(T n)
{
  T result = 0;
  for (T i = 1; i <= n; ++i)
    result += i * i;
  return result;
}

template <typename T>
T square_sum(T n)
{
  T result = 0;
  for (T i = 1; i <= n; ++i)
    result += i;
  return result * result;
}

int main(int argc, char *argv[])
{
  int n = 100;
  std::cout << "Answer is "
            << square_sum(n) - sum_square(n)
            << std::endl;
  return 0;
}

Nej, nu stänger jag av datorn för ikväll!

Problem #4

Okej, vi tar problem #4 också. Här är utmaningen att hitta det största talet som är ett palindrom genom produkten av två heltal på minst tre siffror.

#include <iostream>

template <typename T>
bool is_palindrome(T candidate)
{
  T n = candidate, rev = 0;
  while (n > 0)
  {
    rev = rev * 10 + n % 10;
    n /= 10;
  }
  return candidate == rev;
}

int main(int argc, char *argv[])
{
  int largest_palindrome = 0, cx, cy;
  int max = 1000, min = 100;
  for (int x = min; x < max; ++x)
  {
    for (int y = min; y < max; ++y)
    {
      if (is_palindrome(x * y))
      {
        int product = x * y;
        if (product > largest_palindrome)
        {
          cx = x; cy = y;
          largest_palindrome = product;
        }
      }
    }
  }
 
  std::cout << "Answer is "
            << largest_palindrome
            << " (" << cx << " * " << cy << ")"
            << std::endl;
  return 0;
}

Godnatt (på riktigt)!