Оглавление > Квадратичные простые числа
16.05.2023

Квадратичные простые числа

Эйлер опубликовал свою замечательную квадратичную формулу:
n2+n+41
Оказалось, что согласно данной формуле можно получить 40 простых чисел, последовательно подставляя значения 0≤n≤39 . Однако, при n=40 , 402+40+41=40(40+1)+41 делится на 41 без остатка, и, очевидно, при n=41,412+41+41 делится на 41 без остатка.

При помощи компьютеров была найдена невероятная формула n2−79n+1601 , согласно которой можно получить 80 простых чисел для последовательных значений n от 0 до 79. Произведение коэффициентов −79 и 1601 равно −126479.

Рассмотрим квадратичную формулу вида:

n2+an+b, где |a|<1000 и |b|≤1000 где |n| является модулем (абсолютным значением) n.
К примеру, |11|=11 и |−4|=4

Найдите произведение коэффициентов a и b квадратичного выражения, согласно которому можно получить максимальное количество простых чисел для последовательных значений n, начиная со значения n=0.

Решение (F#)

Задачу решим простым перебором с некоторыми ограничениями для снижения вычислительной сложности:

  • b может быть только простым числом, иначе при n=0 результат не будет простым
let isq = float>>sqrt>>int
let isSimp n = seq {2..isq n} |> Seq.forall(fun x-> n%x <> 0)

let simpNums a b = Seq.initInfinite (fun i -> i*i+a*i+b) |> Seq.takeWhile (fun x-> x>0 && isSimp x) 

let simpTo1000 = seq {2..1000} |> Seq.filter isSimp |> Seq.cache

let solv = seq {
            for i in -1000..1000 ->
              i,simpTo1000 |> Seq.map (simpNums i) |> Seq.map (fun s -> Seq.head s,Seq.length s) |> Seq.maxBy snd
            }
            |> Seq.maxBy (fun (a,(b,c)) -> c)

printfn "%A" solv //(-61, (971, 71))

let answer = fst solv * fst (snd solv)

printfn $"the answer is {answer}" //the answer is -59231