OFFSET
1,2
COMMENTS
Bertrand's postulate guarantees for every integer n the existence of at least one prime q with n < q < 2n. Equivalently, A(n) has at least one skew diagonal below the main skew diagonal whose entries will be equal to 1.
LINKS
David A. Corneth, Table of n, a(n) for n = 1..10000
William Dowling and Nadia Lafreniere, Homomesy on permutations with toggling actions, arXiv:2312.02383 [math.CO], 2023. See page 10.
FORMULA
From Alois P. Heinz, Sep 29 2017: (Start)
a(n) = a(n-1) + 2 * (pi(2*n-1) - pi(n)) for n > 1, a(1) = 1.
a(n) = Sum_{i=1..n} (pi(n+i) - pi(i)), where pi = A000720. - Ridouane Oudra, Aug 29 2019
a(n) = Sum_{p <= 2n+1, p prime} min(p-1, 2n+1-p). - Ridouane Oudra, Oct 30 2023
EXAMPLE
|1 1 0 1 0|
|1 0 1 0 1|
A_5 = |0 1 0 1 0| and so a(5) = 11.
|1 0 1 0 0|
|0 1 0 0 0|
MAPLE
with(numtheory):
a:= proc(n) option remember; `if`(n=1, 1,
a(n-1)+2*(pi(2*n-1)-pi(n)))
end:
seq(a(n), n=1..80); # Alois P. Heinz, Sep 29 2017
MATHEMATICA
A[n_] := Table[Boole[PrimeQ[i + j]], {i, 1, n}, {j, 1, n}]; a[n_] := Count[Flatten[A[n]], 1];
(* or, after Alois P. Heinz (200 times faster): *)
a[1] = 1; a[n_] := a[n] = a[n-1] + 2(PrimePi[2n-1] - PrimePi[n]);
Array[a, 80] (* Jean-François Alcover, Sep 29 2017 *)
PROG
(Python)
from sympy import primepi
from sympy.core.cache import cacheit
@cacheit
def a(n): return 1 if n==1 else a(n - 1) + 2*(primepi(2*n - 1) - primepi(n))
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Dec 13 2017, after Alois P. Heinz
(Magma) sol:=[]; for n in [1..56] do k:=0; for i, j in [1..n] do if IsPrime(i+j) then k:=k+1; end if; end for; Append(~sol, k); end for; sol; // Marius A. Burtea, Aug 29 2019
(PARI) first(n) = {my(res = vector(n), pn = 0, p2n1 = 1); res[1] = 1; for(i = 2, n,
if(isprime(i), pn++); if(isprime(2*i-1), p2n1++); res[i] = res[i-1] + 2*(p2n1 - pn)); res} \\ David A. Corneth, Aug 31 2019
KEYWORD
nonn
AUTHOR
Anthony Hernandez, Sep 26 2017
STATUS
approved