A003972 Moebius transform of A003961; a(n) = phi(A003961(n)), where A003961 shifts the prime factorization of n one step towards the larger primes.

1, 2, 4, 6, 6, 8, 10, 18, 20, 12, 12, 24, 16, 20, 24, 54, 18, 40, 22, 36, 40, 24, 28, 72, 42, 32, 100, 60, 30, 48, 36, 162, 48, 36, 60, 120, 40, 44, 64, 108, 42, 80, 46, 72, 120, 56, 52, 216, 110, 84, 72, 96, 58, 200, 72, 180, 88, 60, 60, 144, 66, 72, 200, 486, 96, 96, 70

Offset: 1

Author

Marc LeBrun

Keywords

• nonn
• mult

Links

• Antti Karttunen, Table of n, a(n) for n = 1..20000 (first 1000 terms from Vincenzo Librandi)

Crossrefs

Cf. A000010, A003961, A037225, A048673, A108228.

Cf. also A003973.

Programs

Mathematica

b[1] = 1; b[p_?PrimeQ] := b[p] = Prime[ PrimePi[p] + 1]; b[n_] := b[n] = Times @@ (b[First[#]]^Last[#] &) /@ FactorInteger[n]; a[n_] := Sum[ MoebiusMu[n/d]*b[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 70}]  (* Jean-François Alcover, Jul 18 2013 *)

PARI

A003972(n) = { my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); eulerphi(factorback(f)); }; \\ Antti Karttunen, Aug 20 2020

Python

from math import prod
from sympy import nextprime, factorint
def A003972(n): return prod((q:=nextprime(p))**(e-1)*(q-1) for p, e in factorint(n).items()) # Chai Wah Wu, Jul 18 2022

Formula

Multiplicative with a(p^e) = (q-1)q^(e-1) where q = nextPrime(p). - David W. Wilson, Sep 01 2001

a(n) = A000010(A003961(n)) = A037225(A108228(n)) = A037225(A048673(n)-1). - Antti Karttunen, Aug 20 2020

Sum_{k=1..n} a(k) ~ c * n^2, where c = (3/Pi^2) * Product_{p prime} (p^2-p)/(p^2 - nextPrime(p)) = 1.2547593344... . - Amiram Eldar, Nov 18 2022

Extensions

More terms from David W. Wilson, Aug 29 2001

Secondary name added by Antti Karttunen, Aug 20 2020