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

Author

David James Sycamore, Jan 04 2024

Keywords

• nonn

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).

Examples

			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.
		

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.

Crossrefs

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

Programs

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 *)

PARI

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

Formula

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

Extensions

More terms from Michel Marcus, Jan 04 2024