Lemoine’s Conjecture


Lemoine’s Conjecture says any odd integer greater than 5 can be represented as the sum of an odd prime number and an even semiprime. Another statement which is suitable for programming is that 2n + 1 = p + 2q always has a solution in primes p and q (not necessarily distinct) for n > 2. We will write a Go program to find p and q for given odd number greater than 5.

Run Code on Go Playground

package lemoine

import (
      "fmt"
)

func IsPrime(n int) bool {
      if n < 2 {
              return false
      }

      for i := 2; i*i <= n; i++ {
              if n%i == 0 {
                      return false
              }
      }
      return true
}

func Lemoine(n int) {
      if n <= 5 || n%2 == 0 {
              panic("n must be greater than 5 and must be odd")
      }

      m := make(map[int]int)

      for q := 1; q <= n/2; q++ {
              p := n - 2*q

              if IsPrime(p) && IsPrime(q) {
                      m[p] = q
              }
      }

      for p, q := range m {
              fmt.Println(n, "=", p, "+ ( 2 *", q, ")")
      }
}

Example:

package lemoine

import (
      "testing"
)

func TestIsPrime(t *testing.T) {
      if IsPrime(97) != true {
              t.Error("97 fail")
      }
      if IsPrime(98) != false {
              t.Error("98 fail")
      }
}

func TestLemoine(t *testing.T) {
      Lemoine(39)
      Lemoine(7)
      Lemoine(101)
}

Tested on:


References:

[1]Lemoine's Conjecture - GeeksforGeeks
[2][Golang] Sieve of Eratosthenes