A003958 -id:A003958 - cp's OEIS frontend

A013929 Numbers that are not squarefree. Numbers that are divisible by a square greater than 1. The complement of A005117.

4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 60, 63, 64, 68, 72, 75, 76, 80, 81, 84, 88, 90, 92, 96, 98, 99, 100, 104, 108, 112, 116, 117, 120, 121, 124, 125, 126, 128, 132, 135, 136, 140, 144, 147, 148, 150, 152, 153, 156, 160

Offset: 1

Henri Lifchitz

Sometimes misnamed squareful numbers, but officially those are given by A001694.
This is different from the sequence of numbers k such that A007913(k) < phi(k). The two sequences differ at the values: 420, 660, 780, 840, 1320, 1560, 4620, 5460, 7140, ..., which is essentially A070237. - Ant King, Dec 16 2005
Numbers k such that Sum_{d|k} (d/phi(d))*mu(k/d) = 0. - Benoit Cloitre, Apr 28 2002
Also, k with at least one x < k such that A007913(x) = A007913(k). - Benoit Cloitre, Apr 28 2002
Numbers k for which there exists a partition into two parts p and q such that p + q = k and p*q is a multiple of k. - Amarnath Murthy, May 30 2003
Numbers k such that there is a solution 0 < x < k to x^2 == 0 (mod k). - Franz Vrabec, Aug 13 2005
Numbers k such that moebius(k) = 0.
a(n) = k such that phi(k)/k = phi(m)/m for some m < k. - Artur Jasinski, Nov 05 2008
Appears to be numbers such that when a column with index equal to a(n) in A051731 is deleted, there is no impact on the result in the first column of A054525. - Mats Granvik, Feb 06 2009
Numbers k such that the number of prime divisors of (k+1) is less than the number of nonprime divisors of (k+1). - Juri-Stepan Gerasimov, Nov 10 2009
Orders for which at least one non-cyclic finite abelian group exists: A000688(a(n)) > 1. This follows from the fact that not all exponents in the prime factorization of a(n) are 1 (moebius(a(n)) = 0). The number of such groups of order a(n) is A192005(n) = A000688(a(n)) - 1. - Wolfdieter Lang, Jul 29 2011
Subsequence of A193166; A192280(a(n)) = 0. - Reinhard Zumkeller, Aug 26 2011
It appears that terms are the numbers m such that Product_{k=1..m} (prime(k) mod m) <> 0. See Maple code. - Gary Detlefs, Dec 07 2011
A008477(a(n)) > 1. - Reinhard Zumkeller, Feb 17 2012
A057918(a(n)) > 0. - Reinhard Zumkeller, Mar 27 2012
A056170(a(n)) > 0. - Reinhard Zumkeller, Dec 29 2012
Numbers k such that A001221(k) != A001222(k). - Felix Fröhlich, Aug 13 2014
Numbers k such that A001222(k) > A001221(k), since in this case at least one prime factor of k occurs more than once, which implies that k is divisible by at least one perfect square > 1. - Carlos Eduardo Olivieri, Aug 02 2015
Lexicographically least sequence such that each term has a positive even number of proper divisors not occurring in the sequence, cf. the sieve characterization of A005117. - Glen Whitney, Aug 30 2015
There are arbitrarily long runs of consecutive terms. Record runs start at 4, 8, 48, 242, ... (A045882). - Ivan Neretin, Nov 07 2015
A number k is a term if 0 < min(A000010(k) + A023900(k), A000010(k) - A023900(k)). - Torlach Rush, Feb 22 2018
Every squareful number > 1 is nonsquarefree, but the converse is false and the nonsquarefree numbers that are not squareful (see first comment) are in A332785. - Bernard Schott, Apr 11 2021
Integers m where at least one k < m exists such that m divides k^m. - Richard R. Forberg, Jul 31 2021
Consider the Diophantine equation S(x,y) = (x+y) + (x-y) + (x*y) + (x/y) = z, when x and y are both positive integers with y | x. Then, there is a solution (x,y) iff z is a term of this sequence; in this case, if x = K*y, then z = S(K*y,y) = K*(y+1)^2 (see A351381, link and references Perelman); example: S(12,4) = 75 = a(28). The number of solutions for S(x,y) = a(n) is A353282(n). - Bernard Schott, Mar 29 2022
For each positive integer m, the number of unitary divisors of m = the number of squarefree divisors of m (see A034444); but only for the terms of this sequence does the set of unitary divisors differ from the set of squarefree divisors. Example: the set of unitary divisors of 20 is {1, 4, 5, 20}, while the set of squarefree divisors of 20 is {1, 2, 5, 10}. - Bernard Schott, Oct 15 2022

			For the terms up to 20, we compute the squares of primes up to floor(sqrt(20)) = 4. Those squares are 4 and 9. For every such square s, put the terms s*k^2 for k = 1 to floor(20 / s). This gives after sorting and removing duplicates the list 4, 8, 9, 12, 16, 18, 20. - _David A. Corneth_, Oct 25 2017

I. Perelman, L'Algèbre récréative, Deux nombres et quatre opérations, Editions en langues étrangères, Moscou, 1959, pp. 101-102.
Ya. I. Perelman, Algebra can be fun, Two numbers and four operations, Mir Publishers Moscow, 1979, pp. 131-132.

David A. Corneth, Table of n, a(n) for n = 1..100000 (first 1000 terms from T. D. Noe)
H. Gent, Letter to N. J. A. Sloane, Nov 27 1975.
Louis Marmet, First occurrences of square-free gaps and an algorithm for their computation, arXiv:1210.3829 [math.NT], 2012.
Ya. I. Perelman, Algebra Can Be Fun, Chapter IV, Diophantine Equations, Two numbers and four operations, Mir Publishers Moscow, 1979, pp. 131-132.
Srinivasa Ramanujan, Irregular numbers, J. Indian Math. Soc. 5 (1913) 105-106.
Eric Weisstein's World of Mathematics, Smarandache Near-to-Primorial Function, Squarefree, Squareful, Moebius Function.

Complement of A005117. Subsequences: A130897, A190641, A332785.
Cf. A001694, A008683, A034444, A038109, A351381, A353282.
Partitions into: A114374, A256012.

a013929 n = a013929_list !! (n-1)
a013929_list = filter ((== 0) . a008966) [1..]
-- Reinhard Zumkeller, Apr 22 2012

[ n : n in [1..1000] | not IsSquarefree(n) ];

a := n -> `if`(numtheory[mobius](n)=0,n,NULL); seq(a(i),i=1..160); # Peter Luschny, May 04 2009
t:= n-> product(ithprime(k),k=1..n): for n from 1 to 160 do (if t(n) mod n <>0) then print(n) fi od; # Gary Detlefs, Dec 07 2011
with(NumberTheory): isQuadrateful := n -> irem(Radical(n), n) <> 0:
select(isQuadrateful, [`$`(1..160)]);  # Peter Luschny, Jul 12 2022

Union[ Flatten[ Table[ n i^2, {i, 2, 20}, {n, 1, 400/i^2} ] ] ]
Select[ Range[2, 160], (Union[Last /@ FactorInteger[ # ]][[ -1]] > 1) == True &] (* Robert G. Wilson v, Oct 11 2005 *)
Cases[Range[160], n_ /; !SquareFreeQ[n]] (* Jean-François Alcover, Mar 21 2011 *)
Select[Range@160, ! SquareFreeQ[#] &] (* Robert G. Wilson v, Jul 21 2012 *)
Select[Range@160, PrimeOmega[#] > PrimeNu[#] &] (* Carlos Eduardo Olivieri, Aug 02 2015 *)
Select[Range[200], MoebiusMu[#] == 0 &] (* Alonso del Arte, Nov 07 2015 *)

{a(n)= local(m,c); if(n<=1,4*(n==1), c=1; m=4; while( cMichael Somos, Apr 29 2005 */

for(n=1, 1e3, if(omega(n)!=bigomega(n), print1(n, ", "))) \\ Felix Fröhlich, Aug 13 2014

upto(n)=my(res = List()); forprime(p = 2, sqrtint(n), for(k = 1, n \ p^2, listput(res, k * p^2))); listsort(res, 1); res \\ David A. Corneth, Oct 25 2017

from sympy.ntheory.factor_ import core
def ok(n): return core(n, 2) != n
print(list(filter(ok, range(1, 161)))) # Michael S. Branicky, Apr 08 2021

from math import isqrt
from sympy import mobius
def A013929(n):
    def f(x): return n+sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return m # Chai Wah Wu, Jul 20 2024

A008966(a(n)) = 0. - Reinhard Zumkeller, Apr 22 2012
Sum_{n>=1} 1/a(n)^s = (zeta(s)*(zeta(2*s)-1))/zeta(2*s). - Enrique Pérez Herrero, Jul 07 2012
a(n) ~ n/k, where k = 1 - 1/zeta(2) = 1 - 6/Pi^2 = A229099. - Charles R Greathouse IV, Sep 13 2013
A001222(a(n)) > A001221(a(n)). - Carlos Eduardo Olivieri, Aug 02 2015
phi(a(n)) > A003958(a(n)). - Juri-Stepan Gerasimov, Apr 09 2019

More terms from Erich Friedman

More terms from Franz Vrabec, Aug 13 2005

A033879 Deficiency of n, or 2n - (sum of divisors of n).

Original entry on oeis.org

1, 1, 2, 1, 4, 0, 6, 1, 5, 2, 10, -4, 12, 4, 6, 1, 16, -3, 18, -2, 10, 8, 22, -12, 19, 10, 14, 0, 28, -12, 30, 1, 18, 14, 22, -19, 36, 16, 22, -10, 40, -12, 42, 4, 12, 20, 46, -28, 41, 7, 30, 6, 52, -12, 38, -8, 34, 26, 58, -48, 60, 28, 22, 1, 46, -12, 66, 10, 42, -4, 70, -51

Offset: 1

N. J. A. Sloane

Records for the sequence of the absolute values are in A075728 and the indices of these records in A074918. - R. J. Mathar, Mar 02 2007
a(n) = 1 iff n is a power of 2. a(n) = n - 1 iff n is prime. - Omar E. Pol, Jan 30 2014
If a(n) = 1 then n is called a least deficient number or an almost perfect number. All the powers of 2 are least deficient numbers but it is not known if there exists a least deficient number that is not a power of 2. See A000079. - Jianing Song, Oct 13 2019
It is not known whether there are any -1's in this sequence. See comment in A033880. - Antti Karttunen, Feb 02 2020

			For n = 10 the divisors of 10 are 1, 2, 5, 10, so the deficiency of 10 is 10 minus the sum of its proper divisors or simply 10 - 5 - 2 - 1 = 2. - _Omar E. Pol_, Dec 27 2013

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B2, pp. 74-84.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 147.

N. J. A. Sloane, Table of n, a(n) for n = 1..25000 [First 2000 terms from T. D. Noe, terms up to 16384 from Antti Karttunen]
Nichole Davis, Dominic Klyve and Nicole Kraght, On the difference between an integer and the sum of its proper divisors, Involve, Vol. 6 (2013), No. 4, 493-504; DOI: 10.2140/involve.2013.6.493.
Jose A. B. Dris, Conditions Equivalent to the Descartes-Frenicle-Sorli Conjecture on Odd Perfect Numbers, arXiv preprint arXiv:1610.01868 [math.NT], 2016.
Jose Arnaldo B. Dris, Analysis of the Ratio D(n)/n, arXiv:1703.09077 [math.NT], 2017.
Jose Arnaldo Bebita Dris, On a curious biconditional involving the divisors of odd perfect numbers, Notes on Number Theory and Discrete Mathematics, 23(4) (2017), 1-13.
Jose Arnaldo Bebita Dris and Immanuel Tobias San Diego, Some Modular Considerations Regarding Odd Perfect Numbers, arXiv:2002.12139 [math.NT], 2020.
Jose Arnaldo Bebita Dris and Doli-Jane Uvales Tejada, Conditions equivalent to the Descartes-Frenicle-Sorli Conjecture on odd perfect numbers - Part II, Notes on Number Theory and Discrete Mathematics (2018) Vol. 24, No. 3, 62-67.
Jose Arnaldo Bebita Dris and Doli-Jane Uvales Tejada, A note on the OEIS sequence A228059, Notes on Number Theory and Discrete Mathematics (2019) Vol. 25, No. 1, 199-205.
Index entries for sequences related to sigma(n).

Cf. A000396 (positions of zeros), A005100 (of positive terms), A005101 (of negative terms).
Cf. A000203, A033880, A074918, A075728, A192895, A286385, A286449, A295881, A295882.
Cf. A083254 (Möbius transform), A228058, A296074, A296075, A323910, A325636, A325826, A325970, A325976.
Cf. A141545 (positions of a(n) = -12).
For this sequence applied to various permutations of natural numbers and some other sequences, see A323174, A323244, A324055, A324185, A324546, A324574, A324575, A324654, A325379.

with(numtheory): A033879:=n->2*n-sigma(n): seq(A033879(n), n=1..100);

Table[2n-DivisorSigma[1,n],{n,80}] (* Harvey P. Dale, Oct 24 2011 *)

a(n)=2*n-sigma(n) \\ Charles R Greathouse IV, Oct 13 2016

from sympy import divisor_sigma
def A033879(n): return (n<<1)-divisor_sigma(n) # Chai Wah Wu, Apr 13 2024

[2*n-sigma(n, 1) for n in range(1, 73)] # Stefano Spezia, Jul 18 2025

a(n) = -A033880(n).
a(n) = A005843(n) - A000203(n). - Omar E. Pol, Dec 14 2008
a(n) = n - A001065(n). - Omar E. Pol, Dec 27 2013
G.f.: 2*x/(1 - x)^2 - Sum_{k>=1} k*x^k/(1 - x^k). - Ilya Gutkovskiy, Jan 24 2017
a(n) = A286385(n) - A252748(n). - Antti Karttunen, May 13 2017
From Antti Karttunen, Dec 29 2017: (Start)
a(n) = Sum_{d|n} A083254(d).
a(n) = Sum_{d|n} A008683(n/d)*A296075(d).
a(n) = A065620(A295881(n)) = A117966(A295882(n)).
a(n) = A294898(n) + A000120(n).
(End)
From Antti Karttunen, Jun 03 2019: (Start)
Sequence can be represented in arbitrarily many ways as a difference of the form (n - f(n)) - (g(n) - n), where f and g are any two sequences whose sum f(n)+g(n) = sigma(n). Here are few examples:
a(n) = A325314(n) - A325313(n) = A325814(n) - A034460(n) = A325978(n) - A325977(n).
a(n) = A325976(n) - A325826(n) = A325959(n) - A325969(n) = A003958(n) - A324044(n).
a(n) = A326049(n) - A326050(n) = A326055(n) - A326054(n) = A326044(n) - A326045(n).
a(n) = A326058(n) - A326059(n) = A326068(n) - A326067(n).
a(n) = A326128(n) - A326127(n) = A066503(n) - A326143(n).
a(n) = A318878(n) - A318879(n).
a(A228058(n)) = A325379(n). (End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = 1 - Pi^2/12 = 0.177532... . - Amiram Eldar, Dec 07 2023

Definition corrected by N. J. A. Sloane, Jul 04 2005

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

Original entry on oeis.org

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

José María Grau Ribas, Feb 21 2010

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A003959 If n = Product p(k)^e(k) then a(n) = Product (p(k)+1)^e(k), a(1) = 1.

Original entry on oeis.org

1, 3, 4, 9, 6, 12, 8, 27, 16, 18, 12, 36, 14, 24, 24, 81, 18, 48, 20, 54, 32, 36, 24, 108, 36, 42, 64, 72, 30, 72, 32, 243, 48, 54, 48, 144, 38, 60, 56, 162, 42, 96, 44, 108, 96, 72, 48, 324, 64, 108, 72, 126, 54, 192, 72, 216, 80, 90, 60, 216, 62, 96, 128, 729, 84, 144, 68

Offset: 1

Marc LeBrun

Completely multiplicative.

Sum of divisors of n with multiplicity. If n = p^m, the number of ways to make p^k as a divisor of n is C(m,k); and sum(C(m,k)*p^k) = (p+1)^k. The rest follows because the function is multiplicative. - Franklin T. Adams-Watters, Jan 25 2010

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 1000 terms from T. D. Noe)
Index to divisibility sequences

Apart from initial terms, same as A064478.
Cf. A003958, A027746, A036987, A061142, A163407.
Cf. A063441, A165824, A165825, A165826, A165827.
Cf. A165828, A165829, A165831, A167350, A166590.
Cf. A166642, A166643, A166644, A166645, A166646.
Cf. A166647, A166649, A166650, A166586, A165830.
Cf. A167351, A168065, A168066.

a003959 1 = 1
a003959 n = product $ map (+ 1) $ a027746_row n
-- Reinhard Zumkeller, Apr 09 2012

a:= n-> mul((i[1]+1)^i[2], i=ifactors(n)[2]):
seq(a(n), n=1..80);  # Alois P. Heinz, Sep 13 2017

a[1] = 1; a[n_] := (fi = FactorInteger[n]; Times @@ ((fi[[All, 1]]+1)^fi[[All, 2]])); a /@ Range[67] (* Jean-François Alcover, Apr 22 2011 *)

a(n)=if(n<1,0,direuler(p=2,n,1/(1-X-p*X))[n]) /* Ralf Stephan */

Multiplicative with a(p^e) = (p+1)^e. - David W. Wilson, Aug 01 2001
Sum_{n>0} a(n)/n^s = Product_{p prime} 1/(1-p^(-s)-p^(1-s)) (conjectured). - Ralf Stephan, Jul 07 2013
This follows from the absolute convergence of the sum (compare with a(n) = n^2) and the Euler product for completely multiplicative functions. Convergence occurs for at least Re(s)>3. - Thomas Anton, Jul 15 2021
Sum_{k=1..n} a(k) ~ c * n^2, where c = A065488/2 = 1/(2*A005596) = 1.3370563627850107544802059152227440187511993141988459926... - Vaclav Kotesovec, Jul 17 2021
From Thomas Scheuerle, Jul 19 2021: (Start)
a(n) = gcd(A166642(n), A166643(n)).
a(n) = A166642(n)/A061142(n).
a(n) = A166643(n)/A165824(n).
a(n) = A166644(n)/A165825(n).
a(n) = A166645(n)/A165826(n).
a(n) = A166646(n)/A165827(n).
a(n) = A166647(n)/A165828(n).
a(n) = A166649(n)/A165830(n).
a(n) = A166650(n)/A165831(n).
a(n) = A167351(n)/A166590(n). (End)
Dirichlet g.f.: zeta(s-1) * Product_{primes p} (1 + 1/(p^s - p - 1)). - Vaclav Kotesovec, Aug 22 2021

Definition reedited (with formula) by Daniel Forgues, Nov 17 2009

A336466 Fully multiplicative with a(p) = A000265(p-1) for any prime p, where A000265(k) gives the odd part of k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 5, 1, 3, 3, 1, 1, 1, 1, 9, 1, 3, 5, 11, 1, 1, 3, 1, 3, 7, 1, 15, 1, 5, 1, 3, 1, 9, 9, 3, 1, 5, 3, 21, 5, 1, 11, 23, 1, 9, 1, 1, 3, 13, 1, 5, 3, 9, 7, 29, 1, 15, 15, 3, 1, 3, 5, 33, 1, 11, 3, 35, 1, 9, 9, 1, 9, 15, 3, 39, 1, 1, 5, 41, 3, 1, 21, 7, 5, 11, 1, 9, 11, 15, 23, 9, 1, 3, 9, 5, 1, 25, 1, 51, 3, 3

Offset: 1

Antti Karttunen, Jul 22 2020

For the comment here, we extend the definition of the second kind of Cunningham chain (see Wikipedia-article) so that also isolated primes for which neither (p+1)/2 nor 2p-1 is a prime are considered to be in singular chains, that is, in chains of the length one. If we replace one or more instances of any particular odd prime factor p in n with any odd prime q in such a chain, so that m = (q^k)*n / p^(e-k), where e is the exponent of p of n, and k <= e is the number of instances of p replaced with q, then it holds that a(m) = a(n), and by induction, the value stays invariant for any number of such replacements. Note also that A001222, but not necessarily A001221 will stay invariant in such changes.
For example, if some of the odd prime divisors p of n are in A005382, then replacing it with 2p-1 (i.e., the corresponding terms of A005383), gives a new number m, for which a(m) = a(n). And vice versa, the same is true for any of the prime divisors > 3 of n that are in A005383, then replacing any one of them with (p+1)/2 will not affect the result. For example, a(37*37*37) = a(19*37*73) = 729 as 37 is both in A005382 and in A005383.
a(n) = A053575(n) for squarefree n (A005117). - Antti Karttunen, Mar 16 2021

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Wikipedia, Cunningham chain

Cf. A000265, A003958, A005117, A005382, A005383, A053575, A329697, A333787, A335915, A336396, A336467, A336468, A339870, A339876 [= a(A122111(n))], A339903 [= a(A003961(n))], A340084 [= gcd(n-1, a(n))], A340085, A340086.

Cf. also A336460, A336470, A339974.

Array[Times @@ Map[If[# <= 2, 1, (# - 1)/2^IntegerExponent[# - 1, 2]] &, Flatten[ConstantArray[#1, #2] & @@@ FactorInteger[#]]] &, 105] (* Michael De Vlieger, Jul 24 2020 *)

A000265(n) = (n>>valuation(n,2));
A336466(n) = { my(f=factor(n)); prod(k=1,#f~,A000265(f[k,1]-1)^f[k,2]); };

a(n) = A000265(A003958(n)) = A000265(A333787(n)).
a(A000010(n)) = A336468(n) = a(A053575(n)).
A329697(a(n)) = A336396(n) = A329697(n) - A087436(n).
a(n) = A335915(n) / A336467(n). - Antti Karttunen, Mar 16 2021

A097945 a(n) = mu(n)*phi(n) where mu(n) is the Mobius function (A008683) and phi(n) is the Euler totient function (A000010).

Original entry on oeis.org

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

Offset: 1

Gerald McGarvey, Sep 04 2004

Also, a(n) = mu(n)*uphi(n) where mu(n) is the Mobius function (A008683) and uphi(n) is the unitary totient function (A047994), since phi(n) = uphi(n) when n is squarefree, while mu(n) = 0 when n is not squarefree. - Franklin T. Adams-Watters, May 14 2006
Conjecture: Sum_{n>=1} mu(n)/phi(n) = Sum_{n>=1} a(n)/phi(n)^2 = 0. It is true that Sum_{n>=1} mu(n)/phi(n)^s = 0 at least for s > 1 since: phi(2)=1, phi is multiplicative, so for n's that are squarefree, the phi(n) values can be partitioned in pairs where phi(m)=phi(2m) and mu(m) = -mu(2m). So Sum_{i=1..n} mu(i)/phi(i)^s < Sum_{j=floor(n/2)..n} 1/phi(j)^s, which approaches 0 as n increases since (1) n^(1-e) < phi(n) < n for any e > 0 and n > N(e) and (2) Sum_{i..n} 1/n^s converges for s > 1. Conjecture: Sum_{n>=1} mu(n)/phi(n)^z = 0 for Re(z) > 1.
Multiplicative with a(p^1) = 1-p, a(p^e) = 0, e > 1. - Mitch Harris, May 24 2005
Row sums of triangle A143153 = a signed version of the sequence such that parity = (-) iff A008683(n) = (+); 0 or (+): (1, 1, 2, 0, 4, -2, 6, 0, 0, -4, 10, 0, 12, -6, 0, 0, 0, ...). - Gary W. Adamson, Jul 27 2008
Dirichlet inverse of A003958. - R. J. Mathar, Jul 08 2011

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Wikipedia, Euler's totient function

Cf. A000010, A003958, A007947, A008683, A008966, A023900, A047994, A143153, A173557, A322581.

with(numtheory):
a:= n-> mobius(n)*phi(n):
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 06 2012

Table[ MoebiusMu[n]EulerPhi[n], {n, 85}] (* Robert G. Wilson v, Sep 06 2004 *)

a(n)=moebius(n)*eulerphi(n) \\ Charles R Greathouse IV, Feb 21 2013

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

Dirichlet g.f.: Product_{primes p} (1-p^(1-s)+p^(-s)). - R. J. Mathar, Aug 29 2011
Sum_{d|n} abs(a(d)) = rad(n) = A007947(n). - Rémy Sigrist, Nov 05 2017
Sum_{k=1..n} abs(a(k)) ~ c * n^2, where c = A065464/2 = (1/2) * Product_{primes p} (1 - 2/p^2 + 1/p^3) = 0.21412475283854722... Equivalently, c = A065463 * 3 / Pi^2. - Vaclav Kotesovec, Jun 14 2020
From Antti Karttunen, Aug 20 2021: (Start)
a(n) = mu(n)*A000010(n) = mu(n)*A003958(n) = mu(n)*A047994(n) = mu(n)*A173557(n), where mu is Möbius mu function (A008683).
a(n) = A008966(n) * A023900(n) = abs(mu(n)) * A023900(n).
a(n) = A322581(n) - A003958(n).
(End)

More terms from Robert G. Wilson v, Sep 06 2004

Edited by N. J. A. Sloane, May 20 2006

A299150 Denominators of the positive solution to n = Sum_{d|n} a(d) * a(n/d).

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 2, 8, 2, 2, 4, 2, 2, 4, 8, 2, 8, 2, 4, 4, 2, 2, 4, 8, 2, 16, 4, 2, 4, 2, 8, 4, 2, 4, 16, 2, 2, 4, 4, 2, 4, 2, 4, 16, 2, 2, 16, 8, 8, 4, 4, 2, 16, 4, 4, 4, 2, 2, 8, 2, 2, 16, 16, 4, 4, 2, 4, 4, 4, 2, 16, 2, 2, 16, 4, 4, 4, 2, 16, 128, 2, 2

Offset: 1

Gus Wiseman, Feb 03 2018

			Sequence begins: 1, 1, 3/2, 3/2, 5/2, 3/2, 7/2, 5/2, 27/8, 5/2, 11/2, 9/4, 13/2, 7/2.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (first 1000 terms from Andrew Howroyd)

Cf. A000010, A003958, A005187, A006519, A007431, A011371, A018804, A023900, A029935, A037445, A046643, A046644, A165825, A257098, A298971, A299119, A299149 (numerators), A299151, A317848, A317929, A317932, A318314, A318512, A318653, A318681.

Cf. A318440 (the 2-adic valuation).

nn=50;
sys=Table[n==Sum[a[d]*a[n/d],{d,Divisors[n]}],{n,nn}];
Denominator[Array[a,nn]/.Solve[sys,Array[a,nn]][[2]]]
f[p_, e_] := 2^((1 + Mod[p, 2])*e - DigitCount[e, 2, 1]); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Apr 28 2023 *)

a(n)={my(v=factor(n)[,2]); denominator(n*prod(i=1, #v, my(e=v[i]); binomial(2*e, e)/4^e))} \\ Andrew Howroyd, Aug 09 2018

A299150(n) = { my(f = factor(n), m=1); for(i=1, #f~, m *= 2^(((1+(f[i,1]%2))*f[i,2]) - hammingweight(f[i,2]))); (m); }; \\ Antti Karttunen, Sep 03 2018

for(n=1, 100, print1(denominator(direuler(p=2, n, 1/(1-p*X)^(1/2))[n]), ", ")) \\ Vaclav Kotesovec, May 08 2025

a(n) = denominator(n*A317848(n)/A165825(n)) = A165825(n)/(A037445(n) * A006519(n)). - Andrew Howroyd, Aug 09 2018
a(n) = A046644(n)/A006519(n). - Andrew Howroyd and Antti Karttunen, Aug 30 2018
From Antti Karttunen, Sep 03 2018: (Start)
a(n) = 2^A318440(n).
Multiplicative with a(2^e) = 2^A011371(e), a(p^e) = 2^A005187(e) for odd primes p.
Multiplicative with a(p^e) = 2^(((1+A000035(p))*e)-A000120(e)) for all primes p.
(End)

Keyword:mult added by Andrew Howroyd, Aug 09 2018

cp's OEIS Frontend

A307579 Numbers k such that A003958(k) does not divide phi(k).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A340093 Composite numbers k such that A003958(k) divides k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A372781 Odd numbers k such that A001221(k) < A001221(A003958(k)).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

A013929 Numbers that are not squarefree. Numbers that are divisible by a square greater than 1. The complement of A005117.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

Extensions

A033879 Deficiency of n, or 2n - (sum of divisors of n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

SageMath

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica