Problem #35, Circular primes below 1000000

I problem 35 är det åter igen primtal som ska itereras och undersökas:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

Min ganska naiva lösning tar ca 43 sekunder på min MacBook.

#!/usr/bin/env python
from math import sqrt

max = 10**6 

def is_prime(n):
  if n == 1: return False
  if n == 2: return True
  if n & 1 == 0: return False
  for i in range(2, int(sqrt(n)) + 1):
    if n % i == 0:
      return False;
  return True;

def num_digits(n):
  d = 0
  while n > 0:
    n, d = n / 10, d + 1
  return d

def next_prime():
  n = 1
  while True:
    if is_prime(n):
      yield n
    n = n + 1

def rotate(n):
  r, n = n % 10, n / 10
  return n + r * 10 ** num_digits(n)

primes = []
for n in next_prime():
  if n > max: break
  primes.append(n)

num_circular = 0
for p in primes:
  def test_circular(n):
    for i in range(0, num_digits(n)):
      if not is_prime(n):
        return False
      n = rotate(n)
    return True 
  if test_circular(p):
    num_circular += 1

print "There are", num_circular, "primes below", max

Nej, nu är det dags för middag. Specklindad kycklingfilé med rotsaksgratäng!

Fotnot: inte späck, utan Speck!

PIIIIIIIP!

Vi hade en mysig hemmakväll igår. TV4 fick stå för tvivelaktig underhållning i form av Let's Dance och "Hjälp!". Men kvällen räddades av en rejäl tallrik Antipasto och ett glas rödvin. Alice blev lite trött framåt kvällen så Gabriella lade sig bredvid henne och somnade själv så sött. Så jag var kvar själv med levande ljus i gillestugan, det var bara skit på teven, men när jag zappade runt hittade jag radiokanaler, P1 körde en repris på Vetenskapsmagasinet som jag började lyssna på.

Det handlade om lök och varför man blir tårögd när man hackar lök. Visste ni förresten att ju mer jävlig löken är, dvs ju mer tårögd man blir, desto nyttigare är den. Dessutom finns det ca 13 ämnen i löken som motverkar olika former av cancer. Själva ämnet man blir tårögd av är en mild form av svavelsyra...

Ja, som ni hör var det ett ganska tråkigt ämne igår. Jag somnade där i soffan med en filt över mig.

Sedan börjar infernot.

Jag börjar drömma. Jag och en kollega befinner oss på jobbet, det är ett ihärdigt oljud, det piper så det gör ont i öronen. Vi förstår inte vad som är fel. Det slutar med att vi ringer han som är ansvarig för driften av byggnaden, vi får bara ett svävande svar att larmet håller på att testas. Jag och kollegan blir nästan galen av oljudet, det slutar med att jag börjar plocka isär larmet (själva enheten där man knappar sin kod), och där hittar jag ett 9-voltsbatteri som jag kopplar ur.

Ahh, tystnad!

I alla fall en liten stund.

Sedan rätt vad det är, befinner vi oss på våning 2 och pipet är tillbaka! Jag springer till larmcentralen och försöker med alla medel få tyst på ljudet, men det slutar inte. Det ihärdiga pipet fortsätter och det börjar värka i öronen.

Plötsligt vaknar jag och är glad att jag bara hade en mardröm, pipet är fortfarande i mina öron och jag ligger några sekunder i hopp om att det ska försvinna. Men det försvinner inte! Jag hoppar upp ur soffan och tror att jag:

a) Fått tinnitus, eller:
b) Blivit galen.

Tankarna flyger genom mitt huvud och jag springer upp, i tron om att det brinner någonstans. "Shit det brinner!! Det måste vara brandvarnaren!" tänker jag. Väl uppe på övervåningen känner jag varken röklukt eller ser någon eld. Men pipet är fortfarande kvar och lika ihärdigt som i drömmen. Under detta ögonblick kommer jag på att vi inte ens har någon brandvarnare (note to self: Skaffa brandvarnare!).

Men jag erinrar mig att då Emil råkat öppna frysen en gång så började den pipa då temperaturen steg. Jag rusade in i köket och kontrollerade både kyl och frys, men de var ordentligt stängda. Som två kassaskåp.

Jag är fortfarande i chock från drömmen, men kan ända höra att pipet har något lägre volym på övervåningen.
Med denna upptäckt rusar jag ner i tvättstugan och kollar tvättmaskinen (man vet ju aldrig), men den var inte på och stod tyst och gapade efter ytterligare en smutstvätt.

DÅ ramlar femöringen ner. Jag hade ju tidigare lyssnat på P1, och uppenbarligen sänder dom inte på natten, eller jo, de sänder ut ett infernalistiskt ljud i form av ett ihärdigt PIIIP!

Jag slår av TV:n (som ju såg avstängd ut eftersom bilden var svart). Pipet försvinner!

Jonas - P1: 1 - 0

Stopp i avloppet för sista gången.

Då var det stopp i avloppet i köket igen. Det är inte första gången det händer, men jag tror det är sista gången.

För det första måste det vara något generalfel med avloppet, för det KAN inte bli stopp så här ofta. Nu är jag ingen expert på ämnet, men något måste vara fel när det blir stopp ca en gång per kvartal.
Jag tror att den tidigare ägaren, (vila i frid), också hade problem då det fanns en rensanordning i garaget som man kopplar till högtryckstvätten.
För att ytterligare späda på eländet så har det liksom droppat vatten runt en inspektionslucka som sitter på det lodräta avloppsröret i väggen, så isoleringen är blöt.

På måndag ringer jag försäkringsbolaget.

Vi ska se om jag kan lyckas lösa proppen med kaustiksoda så att vi kan köra diskmaskinen.

Lördagen kunde inte börja bättre!

PS. Bilden har jag lånat från Karlstads kommun

Tisdag

Jobbat tills nu med tre hotfixes. En stridsvagn i Afghanistan hade visst bekymmer.
Har inte träffat barnen på två dagar. Men imorrn ska vi minsann hitta på något, hoppas att det är skottat på skridsoplanen!

Måndag

Var på Casinot ikväll och såg Henrik Fexeus bli intervjuad av Ulf Elfving. Mycket intressant! För er som inte sett Hjärnstorm på SVT kan jag varmt rekommendera det. Måste läsa hans böcker och sätta mig in mer i ämnet känner jag.

I inträdet ingick även varmrätt och 60kr i spelmarker att spela för.

En bra start på veckan.

Favorit i repris

Problem #206, Concealed Square

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

Det tog bara 7454 iterationer att brute forcea denna.

#!/usr/bin/env python
from math import sqrt

def match(a):
  i = 10
  while (a > 0):
    a, i = a / 100, i - 1
    if a % 10 != i:
      return False
  return True

n = int(sqrt(1929394959697989999)) + 1

while not match(n * n):
  n = n - 1

print "Answer is", n

Oj, nu har melodifestivalen börjat. Ska vara lite social ett tag.

Problem #13

Problem #13 innehåller en lång lista av stora tal som ska summeras, återigen handlar det om stora tal och ja, jag är lat och kör med Python på denna ^^

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

#!/usr/bin/env python
from __future__ import with_statement

def num_digits(a):
  i = 0
  while a > 0:
    a, i = a / 10, i + 1
  return i

with open("euler13.txt") as f:
  a = 0
  for line in f:
    a = a + int(line)
  print "Answer is", (a / 10**(num_digits(a) - 10))

En mer kreativ lösning skulle vara att endast addera de första 12 siffrorna från varje rad istället eftersom de efterföljande inte kan påverka resultatet vi är ute efter (dvs, de tio första siffrorna).

Problem #48

The series, 1^(1) + 2^(2) + 3^(3) + ... + 10^(10) = 10405071317.

Find the last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + ... + 1000^(1000).

Nästan en repetion på problem 25 och 20. Här är min lösning, det fick bli Python igen för att slippa dra in ett bigint lib.

#!/usr/bin/env python
from sys import setrecursionlimit
setrecursionlimit(1002)

def f(n):
  if not n: return 0
  else: return n**n + f(n - 1)

print "Answer is %d" % (f(1000) % 10**10)

Här hittar du problemet.

Problem #25

What is the first term in the Fibonacci sequence to contain 1000 digits?

En till utmaning där vi måste hantera stora heltal.

#!/usr/bin/env python
def fibonacci():
  a, b, i = 0, 1, 0
  while 1:
    yield a, i
    a, b, i = b, a + b, i + 1

for x, i in fibonacci():
  if x >= 10**(1000 - 1):
    print "Answer is %d" % i
    break;

Bra användningsområde för yield, det blir så lättläst kod.

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)!

Problem #3

Och här en quick'n'dirty lösning till problem #3. Här kom primtalsfaktoriseringen till användning.

#include <iostream>
#include <cmath>

template <typename T>
bool is_prime(T p)
{
  for (T i = 2; i < (p / 2.0); ++i)
    if (fmod(p, i) == 0.0)
      return false;
  return true;
}

template <typename T>
T trial_division_prime_only(T n)
{
  T max = sqrt(n), result = 0.0;
  for (T i = 2; i <= max; ++i)
    if (fmod(n, i) == 0.0 && is_prime(i))
      result = i;
  return result;
}

int main(int argc, char *argv[])
{
  long double n = 600851475143;
  std::cout << "Answer is " << trial_division_prime_only(n) << std::endl;
  return 0;
}

Godnatt!

Problem #5

En möjlig lösning till problem #5. Den här snurran tar någon sekund att beta genom på min maskin, men det går att gena genom primtalsfaktorisering fick jag lära mig.

#include <iostream>

bool f(int n)
{
  for (int i = 1; i <= 20; ++i)
    if (n % i)
      return false;
  return true;
}

int main(int argc, char *argv[])
{
  int n = 1;
  while (!f(n))
    ++n;

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

Problem #2

Och här kommer lösning till problem #2:

#include <iostream>

int main(int argc, char *argv[])
{
  int sum = 0;
  for (int t, c = 2, p = 1; sum < 4000000; )
  {
    if (!(c & 1))
      sum += c;
    t = c; c += p; p = t;
  }

  std::cout << "Answer is " << sum << std::endl;

  return 0;
}

Gjorde den rekursiv först; men stacken tog lite för mycket stryk :P

Nya tidsfördriv, Project Euler

Har hittat ett nytt tidsfördriv. Project Euler.

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

Löste igår tre av 231 problem, svårighetsgraden ökar ganska snabbt, så det kommer bli en otroligt lärorik resa.

Här min lösning på Problem #1:

#include <iostream>

int f(int n)
{
  if (!n)
    return 0;
  else
    return (!(n % 3) || !(n % 5)) ? n + f(n - 1) : 0 + f(n - 1);
}

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

Känner jag mig själv rätt kommer många problem lösas av hård brute force ;)