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,3

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

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

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

Example

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

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}]

Prog

(Haskell)
a173557 1 = 1
a173557 n = product $ map (subtract 1) $ a027748_row n
-- Reinhard Zumkeller, Jun 01 2015
(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
(Scheme, with memoization-macro definec) (definec (A173557 n) (if (= 1 n) 1 (* (- (A020639 n) 1) (A173557 (A028234 n))))) ;; Antti Karttunen, Nov 28 2017
(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
(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

Crossrefs

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

Sequence in context: A300234 A070777 A173614 * A023900 A141564 A239641

Adjacent sequences: A173554 A173555 A173556 * A173558 A173559 A173560

Keyword

nonn,easy,mult

Author

José María Grau Ribas, Feb 21 2010

Extensions

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

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

Status

approved