読者です 読者をやめる 読者になる 読者になる

mu chance or much chance ?

日々の戯れ言

Project Euler 27

Project Euler

Problem27を解きました.

  • Reciprocal cycles

Euler discovered the remarkable quadratic formula: n^2+n+41
It turns out that the formula will produce 40 primes for the consecutive integer values 0≤n≤39. However, when n=40,40^2+40+41=40(40+1)+41 is divisible by 41, and certainly when n=41,41^2+41+41 is clearly divisible by 41.

The incredible formula n^2−79n+1601 was discovered, which produces 80 primes for the consecutive values 0≤n≤79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n^2+an+b, where |a|<1000 and |b|≤1000

where |n| is the modulus/absolute value of n
e.g. |11|=11 and |−4|=4
Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n=0.

https://projecteuler.net/problem=27

問題は「2次式n^2 + an + bにおける,n = 0から始めて連続する整数で素数を生成したときに最長の長さとなる係数a, bの積を答求めよ」.

require 'prime'
def func(n, a, b)
	return n ** 2 + a * n + b 
end
pNum = Prime.each(1000).to_a
maxCount = 0
ansA = 0
ansB = 0

for i in 0..pNum.length - 1 do
	b = pNum[i]	
	for a in -999..999 do
		n = 0
		while Prime.prime?(func(n, a, b)) do
			n += 1
		end
		if maxCount < n then
			ansA = a
			ansB = b
			maxCount = n			
		end
	end
end

print(ansA, " * ", ansB, " = ", ansA * ansB, "\n")

n = 0のとき,bのみとなるため
bが素数であることがわかります.
そのため,まず先に1000未満の素数リストを作成しています.