/- 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

Smallest $k \ge 1$ such that the concatenation of $k$ threes and $\text{prime}(n)$ is prime

Let $b_k = 3 \dots 3$ consist of $k \ge 1$ threes in base $10$. The sequence $a(n)$ is the smallest $k \ge 1$ such that the decimal concatenation of $b_k$ and $\text{prime}(n)$ is prime, or $a(n) = 0$ if no such prime exists.

References:

@[expose] public sectionnamespace OeisA242775

The number formed by concatenating $k$ threes with $p$ in base $10$.

def concatThrees (k p : ℕ) : ℕ := ((10 ^ k - 1) / 3) * (10 ^ max 1 (Nat.digits 10 p).length) + pk:ℕhk:0 < kthis:10 ^ 1 ≤ 10 ^ k⊢ 3 ≤ (10 ^ k - 1) / 3 All goals completed! 🐙k:ℕih:3 ∣ (10 ^ k - 1) / 3this:1 ≤ 10 ^ kh2:(10 ^ (k + 1) - 1) / 3 = 3 * 10 ^ k + (10 ^ k - 1) / 3⊢ 3 ∣ 3 * 10 ^ k + (10 ^ k - 1) / 3 All goals completed! 🐙

Smallest $k \ge 1$ such that the concatenation of $k$ threes and $\text{prime}(n)$ is prime, or $0$ if no such prime exists.

noncomputable def a (n : ℕ) : ℕ := if n = 0 then 0 else sInf {k : ℕ | 0 < k ∧ Nat.Prime (concatThrees k (Nat.nth Nat.Prime (n - 1)))}k:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 2)}hk:0 < khp:Nat.Prime (concatThrees k 2)hval:concatThrees k 2 = (10 ^ k - 1) / 3 * 10 + 2hdvd:2 ∣ concatThrees k 2hgt:2 < concatThrees k 2⊢ False k:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 2)}hk:0 < khp:Nat.Prime (concatThrees k 2)hval:concatThrees k 2 = (10 ^ k - 1) / 3 * 10 + 2hdvd:2 ∣ concatThrees k 2hgt:2 < concatThrees k 2h:2 = 1⊢ Falsek:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 2)}hk:0 < khp:Nat.Prime (concatThrees k 2)hval:concatThrees k 2 = (10 ^ k - 1) / 3 * 10 + 2hdvd:2 ∣ concatThrees k 2hgt:2 < concatThrees k 2h:2 = concatThrees k 2⊢ False k:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 2)}hk:0 < khp:Nat.Prime (concatThrees k 2)hval:concatThrees k 2 = (10 ^ k - 1) / 3 * 10 + 2hdvd:2 ∣ concatThrees k 2hgt:2 < concatThrees k 2h:2 = 1⊢ Falsek:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 2)}hk:0 < khp:Nat.Prime (concatThrees k 2)hval:concatThrees k 2 = (10 ^ k - 1) / 3 * 10 + 2hdvd:2 ∣ concatThrees k 2hgt:2 < concatThrees k 2h:2 = concatThrees k 2⊢ False All goals completed! 🐙k:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 3)}hk:0 < khp:Nat.Prime (concatThrees k 3)hval:concatThrees k 3 = (10 ^ k - 1) / 3 * 10 + 3hdvd:3 ∣ concatThrees k 3hgt:3 < concatThrees k 3⊢ False k:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 3)}hk:0 < khp:Nat.Prime (concatThrees k 3)hval:concatThrees k 3 = (10 ^ k - 1) / 3 * 10 + 3hdvd:3 ∣ concatThrees k 3hgt:3 < concatThrees k 3h:3 = 1⊢ Falsek:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 3)}hk:0 < khp:Nat.Prime (concatThrees k 3)hval:concatThrees k 3 = (10 ^ k - 1) / 3 * 10 + 3hdvd:3 ∣ concatThrees k 3hgt:3 < concatThrees k 3h:3 = concatThrees k 3⊢ False k:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 3)}hk:0 < khp:Nat.Prime (concatThrees k 3)hval:concatThrees k 3 = (10 ^ k - 1) / 3 * 10 + 3hdvd:3 ∣ concatThrees k 3hgt:3 < concatThrees k 3h:3 = 1⊢ Falsek:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 3)}hk:0 < khp:Nat.Prime (concatThrees k 3)hval:concatThrees k 3 = (10 ^ k - 1) / 3 * 10 + 3hdvd:3 ∣ concatThrees k 3hgt:3 < concatThrees k 3h:3 = concatThrees k 3⊢ False All goals completed! 🐙k:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 5)}hk:0 < khp:Nat.Prime (concatThrees k 5)hval:concatThrees k 5 = (10 ^ k - 1) / 3 * 10 + 5hdvd:5 ∣ concatThrees k 5hgt:5 < concatThrees k 5⊢ False k:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 5)}hk:0 < khp:Nat.Prime (concatThrees k 5)hval:concatThrees k 5 = (10 ^ k - 1) / 3 * 10 + 5hdvd:5 ∣ concatThrees k 5hgt:5 < concatThrees k 5h:5 = 1⊢ Falsek:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 5)}hk:0 < khp:Nat.Prime (concatThrees k 5)hval:concatThrees k 5 = (10 ^ k - 1) / 3 * 10 + 5hdvd:5 ∣ concatThrees k 5hgt:5 < concatThrees k 5h:5 = concatThrees k 5⊢ False k:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 5)}hk:0 < khp:Nat.Prime (concatThrees k 5)hval:concatThrees k 5 = (10 ^ k - 1) / 3 * 10 + 5hdvd:5 ∣ concatThrees k 5hgt:5 < concatThrees k 5h:5 = 1⊢ Falsek:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 5)}hk:0 < khp:Nat.Prime (concatThrees k 5)hval:concatThrees k 5 = (10 ^ k - 1) / 3 * 10 + 5hdvd:5 ∣ concatThrees k 5hgt:5 < concatThrees k 5h:5 = concatThrees k 5⊢ False All goals completed! 🐙⊢ sInf {k | 0 < k ∧ Nat.Prime (concatThrees k 7)} = 1 exact IsLeast.csInf_eq (⊢ IsLeast {k | 0 < k ∧ Nat.Prime (concatThrees k 7)} 1 All goals completed! 🐙)hlen:(Nat.digits 10 11).length = 2⊢ sInf {k | 0 < k ∧ Nat.Prime (concatThrees k 11)} = 1 exact IsLeast.csInf_eq ⟨⟨hlen:(Nat.digits 10 11).length = 2⊢ 0 < 1 All goals completed! 🐙, hlen:(Nat.digits 10 11).length = 2⊢ Nat.Prime (concatThrees 1 11) hlen:(Nat.digits 10 11).length = 2⊢ Nat.Prime ((10 ^ 1 - 1) / 3 * 10 ^ max 1 2 + 11); All goals completed! 🐙⟩, fun _ h => h.1⟩hlen:(Nat.digits 10 13).length = 2⊢ sInf {k | 0 < k ∧ Nat.Prime (concatThrees k 13)} = 1 exact IsLeast.csInf_eq ⟨⟨hlen:(Nat.digits 10 13).length = 2⊢ 0 < 1 All goals completed! 🐙, hlen:(Nat.digits 10 13).length = 2⊢ Nat.Prime (concatThrees 1 13) hlen:(Nat.digits 10 13).length = 2⊢ Nat.Prime ((10 ^ 1 - 1) / 3 * 10 ^ max 1 2 + 13); All goals completed! 🐙⟩, fun _ h => h.1⟩hlen:(Nat.digits 10 17).length = 2⊢ sInf {k | 0 < k ∧ Nat.Prime (concatThrees k 17)} = 1 exact IsLeast.csInf_eq ⟨⟨hlen:(Nat.digits 10 17).length = 2⊢ 0 < 1 All goals completed! 🐙, hlen:(Nat.digits 10 17).length = 2⊢ Nat.Prime (concatThrees 1 17) hlen:(Nat.digits 10 17).length = 2⊢ Nat.Prime ((10 ^ 1 - 1) / 3 * 10 ^ max 1 2 + 17); All goals completed! 🐙⟩, fun _ h => h.1⟩hlen:(Nat.digits 10 19).length = 2k:ℕx✝:k ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 19)}hk:0 < khp:Nat.Prime (concatThrees k 19)hlt:k < 2hk1:k = 1⊢ False hlen:(Nat.digits 10 19).length = 2x✝:1 ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 19)}hk:0 < 1hp:Nat.Prime (concatThrees 1 19)hlt:1 < 2⊢ False hlen:(Nat.digits 10 19).length = 2x✝:1 ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 19)}hk:0 < 1hlt:1 < 2hp:Nat.Prime ((10 ^ 1 - 1) / 3 * 10 ^ max 1 2 + 19)⊢ False exact absurd hp (hlen:(Nat.digits 10 19).length = 2x✝:1 ∈ {k | 0 < k ∧ Nat.Prime (concatThrees k 19)}hk:0 < 1hlt:1 < 2hp:Nat.Prime ((10 ^ 1 - 1) / 3 * 10 ^ max 1 2 + 19)⊢ ¬Nat.Prime ((10 ^ 1 - 1) / 3 * 10 ^ max 1 2 + 19) All goals completed! 🐙)

Conjecture: For $n \ge 4$, $a(n) > 0$.

@[category research open, AMS 11] theorem conjecture (n : ℕ) (hn : 4 ≤ n) : 0 < a n := n:ℕhn:4 ≤ n⊢ 0 < a n All goals completed! 🐙end OeisA242775