A368748 a(n) is the number of numbers between prime(n) and prime(n+1) that are not prime powers.

0, 0, 1, 1, 1, 2, 1, 3, 3, 1, 4, 3, 1, 3, 4, 5, 1, 4, 3, 1, 5, 2, 5, 7, 3, 1, 3, 1, 3, 11, 2, 5, 1, 9, 1, 5, 5, 3, 4, 5, 1, 9, 1, 3, 1, 11, 11, 3, 1, 3, 5, 1, 8, 4, 5, 5, 1, 5, 3, 1, 8, 13, 3, 1, 3, 13, 5, 8, 1, 3, 5, 6, 5, 5, 3, 5, 7, 3, 7, 9, 1, 9, 1, 5, 3, 5, 7, 3, 1, 3

Offset

1,6

Comments

Here "between" refers to numbers in the range [prime(n) + 1, prime(n+1) - 1], all of which are composite, and the sequence counts the numbers in each such range which are not prime powers. Whereas the corresponding number of prime powers seems bounded (see A080101), the number of numbers which are not prime powers is unbounded (see A014963). Conjecture: Every nonnegative integer appears in this sequence (at least once).

Links

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Michael De Vlieger, Annotated log scatterplot of a(n), n = 1..2^20, showing records in red.

Formula

a(n) = A001223(n) - A080101(n) - 1. - Michael De Vlieger, Jan 04 2024

Example

Between 2 and 3 there are no other numbers so a(1) = 0.
Between 3 and 5 there is only one number (4) and it is a prime power, so a(2) = 0.
Between 5 and 7 the only number is 6 and it is not a prime power, so a(3) = 1.
Between 47 and 53 there are 5 composite numbers, but one of them (49) is a prime power, so since 47 = prime(15), a(15) = 4.

Maple

N:= 101: # for a(1) .. a(N-1)
P:= [seq(ithprime(i), i=1..N)]:
PP:= {seq(seq(P[i]^j, j = 2 .. ilog[P[i]](P[N])), i=1..N)}:
seq(nops({$P[i]+1 .. P[i+1]-1} minus PP), i=1 .. N-1); # Robert Israel, Jan 04 2024

Mathematica

Map[Count[Range[#1, #2 - 1], _?(Not@*PrimePowerQ)] & @@ # &, Partition[Prime@ Range[120], 2, 1]] (* Michael De Vlieger, Jan 04 2024 *)

Prog

(PARI) a(n) = sum(k=prime(n)+1, prime(n+1)-1, !isprimepower(k)); \\ Michel Marcus, Jan 04 2024

Crossrefs

Cf. A000040, A000961, A001223, A014963, A024619, A080101, A085970, A093555, A368749.

Sequence in context: A324602 A319226 A307449 * A207645 A115131 A263916

Adjacent sequences: A368745 A368746 A368747 * A368749 A368750 A368751

Keyword

nonn

Author

David James Sycamore, Jan 04 2024

Extensions

More terms from Michel Marcus, Jan 04 2024

Status

approved