/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Partitions $n = x + y$ with $x^2 + xy + y^2$ prime

For $n \ge 1$, $a(n)$ is the number of ways to write $n$ as $x + y$ with $0 < x \le y$ such that $x^2 + xy + y^2$ is prime.

References:

    A218585

    E. Hecke, "Eine neue Art von Zetafunktionen und ihre Beziehungen zur Verteilung der Primzahlen. Zweite Mitteilung", Math. Z. 6 (1920), 11–51.

@[expose] public sectionnamespace OeisA218585

Number of ways to write $n = x + y$ with $0 < x \le y$ and $x^2 + xy + y^2$ prime.

def a (n : ℕ) : ℕ := ∑ x ∈ Finset.Icc 1 (n / 2), let y := n - x if Nat.Prime (x ^ 2 + x * y + y ^ 2) then 1 else 0@[category test, AMS 11] theorem a_1 : a 1 = 0 := ⊢ a 1 = 0 All goals completed! 🐙@[category test, AMS 11] theorem a_2 : a 2 = 1 := ⊢ a 2 = 1 All goals completed! 🐙@[category test, AMS 11] theorem a_3 : a 3 = 1 := ⊢ a 3 = 1 All goals completed! 🐙@[category test, AMS 11] theorem a_4 : a 4 = 1 := ⊢ a 4 = 1 All goals completed! 🐙@[category test, AMS 11] theorem a_7 : a 7 = 2 := ⊢ a 7 = 2 All goals completed! 🐙@[category test, AMS 11] theorem a_8 : a 8 = 0 := ⊢ a 8 = 0 All goals completed! 🐙

For a prime $p \equiv 1 \pmod 3$, xp p is the unique integer $x > 0$ such that $p = x^2 + xy + y^2$ with $x > y > 0$ (or $0$ if no such representation exists).

def xp (p : ℕ) : ℕ := ((List.range p).find? fun x => (List.range x).any fun y => 0 < y && x ^ 2 + x * y + y ^ 2 == p).getD 0

For a prime $p \equiv 1 \pmod 3$, yp p is the unique integer $y > 0$ such that $p = x^2 + xy + y^2$ with $x > y > 0$ (or $0$ if no such representation exists).

def yp (p : ℕ) : ℕ := ((List.range p).find? fun y => 0 < y && (List.Ico (y + 1) p).any fun x => x ^ 2 + x * y + y ^ 2 == p).getD 0

Conjecture: $a(n) > 0$ for all $n > 1$ with the only exception $n = 8$.

@[category research open, AMS 11] theorem conjecture_1 (n : ℕ) (hn : 1 < n) (h8 : n ≠ 8) : 0 < a n := n:ℕhn:1 < nh8:n ≠ 8⊢ 0 < a n All goals completed! 🐙

Conjecture: The number of primes of the form $nx + (n - x)^2$ with $0 < x < n / 3$ is positive for $n > 12$.

    Zak Seidov, Sep 25 2013

@[category research open, AMS 11] theorem conjecture_2 (n : ℕ) (hn : 12 < n) : ∃ x : ℕ, 0 < x ∧ 3 * x < n ∧ Nat.Prime (n * x + (n - x) ^ 2) := n:ℕhn:12 < n⊢ ∃ x, 0 < x ∧ 3 * x < n ∧ Nat.Prime (n * x + (n - x) ^ 2) All goals completed! 🐙

$$\lim_{N \to \infty} \frac{\sum_{p < N, , p \equiv 1 \pmod 3} x(p)}{\sum_{p < N, , p \equiv 1 \pmod 3} y(p)} = 1 + \sqrt{3},$$ where for a prime $p \equiv 1 \pmod 3$, $x(p) > y(p) > 0$ are the unique positive integers such that $p = x(p)^2 + x(p)y(p) + y(p)^2$.

    Zhi-Wei Sun

This follows from Hecke's (1920) equidistribution theorem for Hecke Grossencharacters of $\mathbb{Q}(\sqrt{-3})$ and partial summation with the prime number theorem.

@[category research solved, AMS 11] theorem conjecture_3 : Filter.atTop.Tendsto (fun N : ℕ => (∑ p ∈ (Finset.range N).filter (fun p => p.Prime ∧ p % 3 = 1), (xp p : ℝ)) / (∑ p ∈ (Finset.range N).filter (fun p => p.Prime ∧ p % 3 = 1), (yp p : ℝ))) (nhds (1 + Real.sqrt 3)) := ⊢ Filter.Tendsto (fun N ↦ (∑ p ∈ Finset.range N with Nat.Prime p ∧ p % 3 = 1, ↑(xp p)) / ∑ p ∈ Finset.range N with Nat.Prime p ∧ p % 3 = 1, ↑(yp p)) Filter.atTop (nhds (1 + √3)) All goals completed! 🐙

Conjecture: $$\lim_{N \to \infty} \frac{\sum_{p < N, , p \equiv 1 \pmod 3} x(p)^2}{\sum_{p < N, , p \equiv 1 \pmod 3} y(p)^2} = \frac{52}{9},$$ where for a prime $p \equiv 1 \pmod 3$, $x(p) > y(p) > 0$ are the unique positive integers such that $p = x(p)^2 + x(p)y(p) + y(p)^2$.

    Zhi-Wei Sun

Disproved by Hecke's (1920) equidistribution theorem for Hecke Grossencharacters of $\mathbb{Q}(\sqrt{-3})$, which yields the true limit $$\frac{\int_0^{\pi/6} (\cos\theta - \frac{1}{\sqrt{3}}\sin\theta)^2,d\theta}{\int_0^{\pi/6} \frac{4}{3}\sin^2\theta,d\theta} = \frac{2\pi}{2\pi - 3\sqrt{3}} \approx 5.780124 \neq \frac{52}{9}.$$

@[category research solved, AMS 11] theorem conjecture_4 : ¬ Filter.atTop.Tendsto (fun N : ℕ => (∑ p ∈ (Finset.range N).filter (fun p => p.Prime ∧ p % 3 = 1), ((xp p : ℝ) ^ 2)) / (∑ p ∈ (Finset.range N).filter (fun p => p.Prime ∧ p % 3 = 1), ((yp p : ℝ) ^ 2))) (nhds (52 / 9 : ℝ)) := ⊢ ¬Filter.Tendsto (fun N ↦ (∑ p ∈ Finset.range N with Nat.Prime p ∧ p % 3 = 1, ↑(xp p) ^ 2) / ∑ p ∈ Finset.range N with Nat.Prime p ∧ p % 3 = 1, ↑(yp p) ^ 2) Filter.atTop (nhds (52 / 9)) All goals completed! 🐙end OeisA218585