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.