A003557 n divided by largest squarefree divisor of n; if n = Product p(k)^e(k) then a(n) = Product p(k)^(e(k)-1), with a(1) = 1.

1, 1, 1, 2, 1, 1, 1, 4, 3, 1, 1, 2, 1, 1, 1, 8, 1, 3, 1, 2, 1, 1, 1, 4, 5, 1, 9, 2, 1, 1, 1, 16, 1, 1, 1, 6, 1, 1, 1, 4, 1, 1, 1, 2, 3, 1, 1, 8, 7, 5, 1, 2, 1, 9, 1, 4, 1, 1, 1, 2, 1, 1, 3, 32, 1, 1, 1, 2, 1, 1, 1, 12, 1, 1, 5, 2, 1, 1, 1, 8, 27, 1, 1, 2, 1, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 16, 1, 7

Offset: 1

Author

Marc LeBrun

Keywords

• nonn
• easy
• mult

Comments

a(n) is the size of the Frattini subgroup of the cyclic group C_n - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 07 2001.

Also of the Frattini subgroup of the dihedral group with 2*n elements. - Sharon Sela (sharonsela(AT)hotmail.com), Jan 01 2002

Number of solutions to x^m==0 (mod n) provided that n < 2^(m+1), i.e. the sequence of sequences A000188, A000189, A000190, etc. converges to this sequence. - Henry Bottomley, Sep 18 2001

a(n) is the number of nilpotent elements in the ring Z/nZ. - Laszlo Toth, May 22 2009

The sequence of partial products of a(n) is A085056(n). - Peter Luschny, Jun 29 2009

The first occurrence of n in this sequence is at A064549(n). - Franklin T. Adams-Watters, Jul 25 2014

From Hal M. Switkay, Jul 03 2025: (Start)

For n > 1, a(n) is a proper divisor of n. Thus the sequence n, a(n), a(a(n)), ... eventually becomes 1. This yields a minimal factorization of n as a product of squarefree numbers (A005117), each factor dividing all larger factors, in a factorization that is conjugate to the minimal factorization of n as a product of prime powers (A000961), as follows.

Let f(n,0) = n, and let f(n,k) = a(f(n,k-1)) for k > 0. A051903(n) is the minimal value of k such that f(n,k) = 1. A051903(n) <= log(n)/log(2). Since n/a(n) = A007947(n) is always squarefree by definition, n is a product of squarefree factors in the form Product_{i=1..A051903(n)} [f(n,i-1)/f(n,i)].

The two factorizations correspond to conjugate partitions of bigomega(n) = A001222(n). (End)

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Henry Bottomley, Some Smarandache-type multiplicative sequences.
• Steven R. Finch, Idempotents and Nilpotents Modulo n, arXiv:math/0605019 [math.NT], 2006-2017.

Crossrefs

Cf. A007947, A062378, A062379, A064549, A300717 (Möbius transform), A326306 (inv. Möbius transf.), A328572.

Sequences that are multiples of this sequence (the other factor of a pointwise product is given in parentheses): A000010 (A173557), A000027 (A007947), A001615 (A048250), A003415 (A342001), A007434 (A345052), A057521 (A071773).

Cf. A082695 (Dgf at s=2), A065487 (Dgf at s=3).

Cf. A000961, A001222, A005117, A051903.

Programs

Haskell

a003557 n = product $ zipWith (^)
                      (a027748_row n) (map (subtract 1) $ a124010_row n)
-- Reinhard Zumkeller, Dec 20 2013

Julia

using Nemo
function A003557(n)
    n < 4 && return 1
    q = prod([p for (p, e) ∈ Nemo.factor(fmpz(n))])
    return n == q ? 1 : div(n, q)
end
[A003557(n) for n in 1:90] |> println  # Peter Luschny, Feb 07 2021

Magma

[(&+[(Floor(k^n/n)-Floor((k^n-1)/n)): k in [1..n]]): n in [1..100]]; // G. C. Greubel, Nov 02 2018

Maple

A003557 := n -> n/ilcm(op(numtheory[factorset](n))):
seq(A003557(n), n=1..98); # Peter Luschny, Mar 23 2011
seq(n / NumberTheory:-Radical(n), n = 1..98); # Peter Luschny, Jul 20 2021

Mathematica

Prepend[ Array[ #/Times@@(First[ Transpose[ FactorInteger[ # ] ] ])&, 100, 2 ], 1 ] (* Olivier Gérard, Apr 10 1997 *)

PARI

a(n)=n/factorback(factor(n)[,1]) \\ Charles R Greathouse IV, Nov 17 2014

PARI

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

Python

from sympy.ntheory.factor_ import core
from sympy import divisors
def a(n): return n / max(i for i in divisors(n) if core(i) == i)
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Apr 16 2017

Python

from math import prod
from sympy import primefactors
def A003557(n): return n//prod(primefactors(n)) # Chai Wah Wu, Nov 04 2022

Sage

def A003557(n) : return n*mul(1/p for p in prime_divisors(n))
[A003557(n) for n in (1..98)] # Peter Luschny, Jun 10 2012

Formula

Multiplicative with a(p^e) = p^(e-1). - Vladeta Jovovic, Jul 23 2001

a(n) = n/rad(n) = n/A007947(n) = sqrt(J_2(n)/J_2(rad(n))), where J_2(n) is A007434. - Enrique Pérez Herrero, Aug 31 2010

a(n) = (J_k(n)/J_k(rad(n)))^(1/k), where J_k is the k-th Jordan Totient Function: (J_2 is A007434 and J_3 A059376). - Enrique Pérez Herrero, Sep 03 2010

Dirichlet convolution of A000027 and A097945. - R. J. Mathar, Dec 20 2011

a(n) = A000010(n)/|A023900(n)|. - Eric Desbiaux, Nov 15 2013

a(n) = Product_{k = 1..A001221(n)} (A027748(n,k)^(A124010(n,k)-1)). - Reinhard Zumkeller, Dec 20 2013

a(n) = Sum_{k=1..n}(floor(k^n/n)-floor((k^n-1)/n)). - Anthony Browne, May 11 2016

a(n) = e^[Sum_{k=2..n} (floor(n/k)-floor((n-1)/k))*(1-A010051(k))*Mangoldt(k)] where Mangoldt is the Mangoldt function. - Anthony Browne, Jun 16 2016

a(n) = Sum_{d|n} mu(d) * phi(d) * (n/d), where mu(d) is the Moebius function and phi(d) is the Euler totient function (rephrases formula of Dec 2011). - Daniel Suteu, Jun 19 2018

G.f.: Sum_{k>=1} mu(k)*phi(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Nov 02 2018

Dirichlet g.f.: Product_{primes p} (1 + 1/(p^s - p)). - Vaclav Kotesovec, Jun 24 2020

From Richard L. Ollerton, May 07 2021: (Start)

a(n) = Sum_{k=1..n} mu(n/gcd(n,k))*gcd(n,k).

a(n) = Sum_{k=1..n} mu(gcd(n,k))*(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)

a(n) = A001615(n)/A048250(n) = A003415/A342001(n) = A057521(n)/A071773(n). - Antti Karttunen, Jun 08 2021

Extensions

Secondary definition added to the name by Antti Karttunen, Jun 08 2021