A389467 Number of natural numbers in range [n .. A003961(n)-1] that are coprime to n.

0, 0, 1, 2, 1, 3, 3, 9, 10, 4, 1, 11, 3, 8, 11, 32, 1, 19, 3, 17, 19, 7, 5, 37, 19, 11, 65, 30, 1, 20, 5, 105, 19, 10, 29, 63, 3, 14, 28, 59, 1, 35, 3, 33, 69, 19, 5, 119, 61, 38, 27, 46, 5, 107, 25, 103, 36, 16, 1, 68, 5, 23, 121, 332, 39, 39, 3, 48, 48, 55, 1, 201, 5, 23, 91, 62, 51, 54, 3, 194, 362, 22, 5, 118

Offset

1,4

Links

Antti Karttunen, Table of n, a(n) for n = 1..20000

Formula

a(n) = Sum_{k=n..A003961(n)-1} [1==gcd(k,n)], where [ ] is the Iverson bracket.

a(n) >= A389464(n).

Mathematica

a3961[x_]:=Times @@ MapApply[#1^#2 &, FactorInteger[x] /. {p_, e_} /; e > 0 :> {Prime[PrimePi[p]+1], e}] - Boole[x == 1]; Table[Count[Range[n, a3961[n] - 1], _?(CoprimeQ[n, #] &)], {n, 84}] (* Michael De Vlieger, Oct 12 2025 *)

Prog

(PARI)
A003961(n) = { my(f=factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); };
A389467(n) = sum(k=n, A003961(n)-1, 1==gcd(k, n));

Crossrefs

Row lengths of A389468.

Cf. A001359 (positions of 1's), A003961.

Cf. also A389464.

Sequence in context: A249137 A246174 A176054 * A257703 A061413 A286385

Adjacent sequences: A389464 A389465 A389466 * A389468 A389469 A389470

Keyword

nonn

Author

Antti Karttunen, Oct 12 2025

Status

approved