A173557 a(n) = Product_{primes p dividing n} (p-1).

1, 1, 2, 1, 4, 2, 6, 1, 2, 4, 10, 2, 12, 6, 8, 1, 16, 2, 18, 4, 12, 10, 22, 2, 4, 12, 2, 6, 28, 8, 30, 1, 20, 16, 24, 2, 36, 18, 24, 4, 40, 12, 42, 10, 8, 22, 46, 2, 6, 4, 32, 12, 52, 2, 40, 6, 36, 28, 58, 8, 60, 30, 12, 1, 48, 20, 66, 16, 44, 24, 70, 2, 72, 36

Offset: 1

Author

José María Grau Ribas, Feb 21 2010

Keywords

• nonn
• easy
• mult

Comments

This is A023900 without the signs. - T. D. Noe, Jul 31 2013

Numerator of c_n = Product_{odd p| n} (p-1)/(p-2). Denominator is A305444. The initial values c_1, c_2, ... are 1, 1, 2, 1, 4/3, 2, 6/5, 1, 2, 4/3, 10/9, 2, 12/11, 6/5, 8/3, 1, 16/15, ... [Yamasaki and Yamasaki]. - N. J. A. Sloane, Jan 19 2020

Kim et al. (2019) named this function the absolute Möbius divisor function. - Amiram Eldar, Apr 08 2020

Examples

			300 = 3*5^2*2^2 => a(300) = (3-1)*(2-1)*(5-1) = 8.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..65536 (first 1000 terms from T. D. Noe)
• Daeyeoul Kim, Umit Sarp, and Sebahattin Ikikardes, Certain combinatoric convolution sums arising from Bernoulli and Euler Polynomials, Miskolc Mathematical Notes, No. 20, Vol. 1 (2019): pp. 311-330.
• Daeyeoul Kim, Umit Sarp, and Sebahattin Ikikardes, Iterating the Sum of Möbius Divisor Function and Euler Totient Function, Mathematics, Vol. 7, No. 11 (2019), pp. 1083-1094.
• Yamasaki, Yasuo, and Aiichi Yamasaki, On the Gap Distribution of Prime Numbers, Kyoto University Research Information Repository, October 1994. MR1370273 (97a:11141).

Crossrefs

Cf. A023900, A141564, A027748, A305444, A307868.

Programs

Haskell

a173557 1 = 1
a173557 n = product $ map (subtract 1) $ a027748_row n
-- Reinhard Zumkeller, Jun 01 2015

Magma

[EulerPhi(n)/(&+[(Floor(k^n/n)-Floor((k^n-1)/n)): k in [1..n]]): n in [1..100]]; // Vincenzo Librandi, Jan 20 2020

Maple

A173557 := proc(n) local dvs; dvs := numtheory[factorset](n) ; mul(d-1,d=dvs) ; end proc: # R. J. Mathar, Feb 02 2011
# second Maple program:
a:= n-> mul(i[1]-1, i=ifactors(n)[2]):
seq(a(n), n=1..80);  # Alois P. Heinz, Aug 27 2018

Mathematica

a[n_] := Module[{fac = FactorInteger[n]}, If[n==1, 1, Product[fac[[i, 1]]-1, {i, Length[fac]}]]]; Table[a[n], {n, 100}]

PARI

a(n) = my(f=factor(n)[,1]); prod(k=1, #f, f[k]-1); \\ Michel Marcus, Oct 31 2017

PARI

for(n=1, 100, print1(direuler(p=2, n, (1 - 2*X + p*X)/(1 - X))[n], ", ")) \\ Vaclav Kotesovec, Jun 18 2020

PARI

apply( {A173557(n)=vecprod([p-1|p<-factor(n)[,1]])}, [1..77]) \\ M. F. Hasler, Aug 14 2021

Python

from math import prod
from sympy import primefactors
def A173557(n): return prod(p-1 for p in primefactors(n)) # Chai Wah Wu, Sep 08 2023

Scheme

;; With memoization-macro definec.
(definec (A173557 n) (if (= 1 n) 1 (* (- (A020639 n) 1) (A173557 (A028234 n))))) ;; Antti Karttunen, Nov 28 2017

Formula

a(n) = A003958(n) iff n is squarefree. a(n) = |A023900(n)|.

Multiplicative with a(p^e) = p-1, e >= 1. - R. J. Mathar, Mar 30 2011

a(n) = phi(rad(n)) = A000010(A007947(n)). - Enrique Pérez Herrero, May 30 2012

a(n) = A000010(n) / A003557(n). - Jason Kimberley, Dec 09 2012

Dirichlet g.f.: zeta(s) * Product_{p prime} (1 - 2p^(-s) + p^(1-s)). The Dirichlet inverse is multiplicative with b(p^e) = (1 - p) * (2 - p)^(e - 1) = Sum_k A118800(e, k) * p^k. - Álvar Ibeas, Nov 24 2017

a(1) = 1; for n > 1, a(n) = (A020639(n)-1) * a(A028234(n)). - Antti Karttunen, Nov 28 2017

From Vaclav Kotesovec, Jun 18 2020: (Start)

Dirichlet g.f.: zeta(s) * zeta(s-1) / zeta(2*s-2) * Product_{p prime} (1 - 2/(p + p^s)).

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = A307868 = Product_{p prime} (1 - 2/(p*(p+1))) = 0.471680613612997868... (End)

a(n) = (-1)^A001221(n)*A023900(n). - M. F. Hasler, Aug 14 2021

Extensions

Definition corrected by M. F. Hasler, Aug 14 2021

Incorrect formula removed by Pontus von Brömssen, Aug 15 2021