Fjerde og sidste spørgsmål i denne omgang har nu været tilgængeligt i et døgns tid. Opgaven handler om primtals-sekvenser. Man får oplyst fire tal (n1, n2, n3 og n4) og skal så finde et tal som har de egenskaber at det:
- er et primtal
- kan udtrykkes som summen af n1 på hinanden følgende primtal
- kan udtrykkes som summen af n2 på hinanden følgende primtal
- kan udtrykkes som summen af n3 på hinanden følgende primtal
- kan udtrykkes som summen af n4 på hinanden følgende primtal
Da n’erne er ret høje (op til omkring 800 i de to tilfælde jeg har set) er der tale om en opgave som kræver lidt regnearbejde.
Jeg har løst opgaven ved at generere en liste med den første million primtal (programmer til dette findes let på Google), samt skrive og køre et lille Ruby script vist nedenfor. Scriptet indlæser listen af primtal (denne antages at ligge i en fil ved navn ‘primes.txt’ i samme mappe som scriptet) til både et Hash og et Array. Derefter filtreres primtals-Hash’et først på alle n1-sekvenser, derefter på n2-, n3- og n4-sekvenser. For begge tilfælde jeg har prøvet har resultatet været et enkelt tal. Hvis der ikke findes resultater kan det måske være nødvendigt med mere end 1 million primtal.
Scriptet ser ud som følger (på 42 linier naturligvis):
ph = {} # prime hash $pa = [] # prime array n1 = 31 n2 = 63 n3 = 415 n4 = 799 File.open('primes.txt') do |f| f.each do |l| ph[l.to_i] = true $pa.push(l.to_i) end end $pmax = $pa[$pa.length-1] puts "Loaded #{$pa.length} primes from #{$pa[0]} to #{$pmax}" def search(filter, length) result = {} $pa.each_index do |n| slice = $pa.slice(n, length) if slice.length == length then sum = slice.inject {|sum, n| sum + n } result[sum] = true if filter[sum] end break if sum > $pmax end result end p1 = search(ph, n1) puts "#{p1.length} of those primes can be expressed as the sum of #{n1} consecutive primes" p2 = search(p1, n2) puts "#{p2.length} of those primes can be expressed as the sum of #{n2} consecutive primes" p3 = search(p2, n3) puts "#{p3.length} of those primes can be expressed as the sum of #{n3} consecutive primes" p4 = search(p3, n4) puts "#{p4.length} of those primes can be expressed as the sum of #{n4} consecutive primes" p4.each do |p, b| puts p end
Eksempel output fra kørsel af programmet er:
Loaded 1000000 primes from 2 to 15485863 5314 of those primes can be expressed as the sum of 31 consecutive primes 18 of those primes can be expressed as the sum of 63 consecutive primes 1 of those primes can be expressed as the sum of 415 consecutive primes 1 of those primes can be expressed as the sum of 799 consecutive primes 6814289
God fornøjelse!