A054525 -id:A054525 - cp's OEIS frontend

A051953 Cototient(n) := n - phi(n).

0, 1, 1, 2, 1, 4, 1, 4, 3, 6, 1, 8, 1, 8, 7, 8, 1, 12, 1, 12, 9, 12, 1, 16, 5, 14, 9, 16, 1, 22, 1, 16, 13, 18, 11, 24, 1, 20, 15, 24, 1, 30, 1, 24, 21, 24, 1, 32, 7, 30, 19, 28, 1, 36, 15, 32, 21, 30, 1, 44, 1, 32, 27, 32, 17, 46, 1, 36, 25, 46, 1, 48, 1, 38, 35, 40, 17, 54, 1, 48, 27

Offset: 1

Labos Elemer, Dec 21 1999

Unlike totients, cototient(n+1) = cototient(n) never holds -- except 2-phi(2) = 3 - phi(3) = 1 -- because cototient(n) is congruent to n modulo 2. - Labos Elemer, Aug 08 2001
Theorem (L. Redei): b^a(n) == b^n (mod n) for every integer b. - Thomas Ordowski and Robert Israel, Mar 11 2016
Let S be the sum of the cototients of the divisors of n (A001065). S < n iff n is deficient, S = n iff n is perfect, and S > n iff n is abundant. - Ivan N. Ianakiev, Oct 06 2023

			n = 12, phi(12) = 4 = |{1, 5, 7, 11}|, a(12) = 12 - phi(12) = 8, numbers not exceeding 12 and not coprime to 12: {2, 3, 4, 6, 8, 9, 10, 12}.

T. D. Noe, Table of n, a(n) for n = 1..10000
J. Browkin and A. Schinzel, On integers not of the form n-phi(n), Colloq. Math., 68 (1995), 55-58.
R. E. Jamison, The Helly bound for singular sums, Discrete Math., 249 (2002), 117-133.
Paul Pollack and Carl Pomerance, Some problems of Erdős on the sum-of-divisors function, Trans. Amer. Math. Soc. Ser. B 3 (2016), 1-26. For Richard Guy on his 99th birthday. May his sequence be unbounded.
Carl Pomerance and Hee-Sung Yang, Variant of a theorem of Erdős on the sum-of-proper-divisors function, Math. Comp. 83 (2014), 1903-1913.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Eric Weisstein's World of Mathematics, Cototient

Cf. A000010, A001065 (inverse Möbius transform), A005278, A001274, A083254, A098006, A049586, A051612, A053579, A054525, A062790 (Möbius transform), A063985 (partial sums), A063986, A290087.
Records: A065385, A065386.
Number of zeros in the n-th row of triangle A054521. - Omar E. Pol, May 13 2016
Cf. A063740 (number of k such that cototient(k) = n). - M. F. Hasler, Jan 11 2018

a051953 n = n - a000010 n  -- Reinhard Zumkeller, Jan 21 2014

with(numtheory); A051953 := n->n-phi(n);

Table[n - EulerPhi[n], {n, 1, 80}] (* Carl Najafi, Aug 16 2011 *)

A051953(n) = n - eulerphi(n); \\ Michael B. Porter, Jan 28 2010

from sympy.ntheory import totient
print([i - totient(i) for i in range(1, 101)]) # Indranil Ghosh, Mar 17 2017

a(n) = n - A000010(n).
Equals Mobius transform (A054525) of A001065. - Gary W. Adamson, Jul 11 2008
a(A006881(n)) = sopf(A006881(n)) - 1; a(A000040(n)) = 1. - Wesley Ivan Hurt, May 18 2013
G.f.: sum(n>=1, A000010(n)*x^(2*n)/(1-x^n) ). - Mircea Merca, Feb 23 2014
From Ilya Gutkovskiy, Apr 13 2017: (Start)
G.f.: -Sum_{k>=2} mu(k)*x^k/(1 - x^k)^2.
Dirichlet g.f.: zeta(s-1)*(1 - 1/zeta(s)). (End)
From Antti Karttunen, Sep 05 2018 & Apr 29 2022: (Start)
Dirichlet convolution square of A317846/A046644 gives this sequence + A063524.
a(n) = A003557(n) * A318305(n).
a(n) = A000010(n) - A083254(n).
a(n) = A318325(n) - A318326(n).
a(n) = Sum_{d|n} A062790(d) = Sum_{d|n, dA007431(d)*(A000005(n/d)-1).
a(n) = A048675(A318834(n)) = A276085(A353564(n)). [These follow from the formula below]
a(n) = Sum_{d|n, dA000010(d).
a(n) = A051612(n) - A001065(n).
(End)

A051731 Triangle read by rows: T(n, k) = 1 if k divides n, T(n, k) = 0 otherwise, for 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de)

T(n, k) is the number of partitions of n into k equal parts. - Omar E. Pol, Apr 21 2018

This triangle is the lower triangular array L in the LU decomposition of the square array A003989. - Peter Bala, Oct 15 2023

			The triangle T(n, k) begins:
  n\k 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  1:  1
  2:  1  1
  3:  1  0  1
  4:  1  1  0  1
  5:  1  0  0  0  1
  6:  1  1  1  0  0  1
  7:  1  0  0  0  0  0  1
  8:  1  1  0  1  0  0  0  1
  9:  1  0  1  0  0  0  0  0  1
  10: 1  1  0  0  1  0  0  0  0  1
  11: 1  0  0  0  0  0  0  0  0  0  1
  12: 1  1  1  1  0  1  0  0  0  0  0  1
  13: 1  0  0  0  0  0  0  0  0  0  0  0  1
  14: 1  1  0  0  0  0  1  0  0  0  0  0  0  1
  15: 1  0  1  0  1  0  0  0  0  0  0  0  0  0  1
  ... Reformatted and extended. - _Wolfdieter Lang_, Nov 12 2014

Charles R Greathouse IV, Rows n = 1..100, flattened
Marc Chamberland, Factored matrices can generate combinatorial identities, Linear Algebra and its Applications, Volume 438, Issue 4, 2013, pp. 1667-1677.
Mats Granvik, Illustration.
Warren P. Johnson, An LDU Factorization in Elementary Number Theory, Mathematics Magazine, Vol. 76, No. 5 (Dec., 2003), pp. 392-394.
Jeffrey Ventrella, Divisor Plot.

Cf. A000007, A000203, A002260, A003989, A048158, A049820, A054525.
Cf. A074854, A101508, A115361, A129372, A172119, A175105.
Cf. A000005 (row sums), A032741(n+2) (diagonal sums).
Cf. A243987 (partial sums per row).
Cf. A134546 (A004736 * T, matrix multiplication).
Variants: A113704, A077049, A077051.

a051731 n k = 0 ^ mod n k
a051731_row n = a051731_tabl !! (n-1)
a051731_tabl = map (map a000007) a048158_tabl
-- Reinhard Zumkeller, Aug 13 2013

[0^(n mod k): k in [1..n], n in [1..17]]; // G. C. Greubel, Jun 22 2024

A051731 := proc(n, k) if n mod k = 0 then 1 else 0 end if end proc:
# R. J. Mathar, Jul 14 2012

Flatten[Table[If[Mod[n, k] == 0, 1, 0], {n, 20}, {k, n}]]

for(n=1,17,for(k=1,n,print1(!(n%k)", "))) \\ Charles R Greathouse IV, Mar 14 2012

from math import isqrt, comb
def A051731(n): return int(not (a:=(m:=isqrt(k:=n<<1))+(k>m*(m+1)))%(n-comb(a,2))) # Chai Wah Wu, Nov 13 2024

A051731_row = lambda n: [int(k.divides(n)) for k in (1..n)]
for n in (1..17): print(A051731_row(n)) # Peter Luschny, Jan 05 2018

{T(n, k)*k, k=1..n} setminus {0} = divisors(n).
Sum_{k=1..n} T(n, k)*k^i = sigma[i](n), where sigma[i](n) is the sum of the i-th power of the positive divisors of n.
Sum_{k=1..n} T(n, k) = A000005(n).
Sum_{k=1..n} T(n, k)*k = A000203(n).
T(n, k) = T(n-k, k) for k <= n/2, T(n, k) = 0 for n/2 < k <= n-1, T(n, n) = 1.
Rows given by A074854 converted to binary. Example: A074854(4) = 13 = 1101_2; row 4 = 1, 1, 0, 1. - Philippe Deléham, Oct 04 2003
From Paul Barry, Dec 05 2004: (Start)
Binomial transform (product by binomial matrix) is A101508.
Columns have g.f.: x^k/(1-x^(k+1)) (k >= 0). (End)
Matrix inverse of triangle A054525, where A054525(n, k) = MoebiusMu(n/k) if k|n, 0 otherwise. - Paul D. Hanna, Jan 09 2006
From Gary W. Adamson, Apr 15 2007, May 10 2007: (Start)
Equals A129372 * A115361 as infinite lower triangular matrices.
A054525 is the inverse of this triangle (as lower triangular matrix).
This triangle * [1, 2, 3, ...] = sigma(n) (A000203).
This triangle * [1/1, 1/2, 1/3, ...] = sigma(n)/n. (End)
From  Reinhard Zumkeller, Nov 01 2009: (Start)
T(n, k) = 0^(n mod k).
T(n, k) = A000007(A048158(n, k)). (End)
From Mats Granvik, Jan 26 2010, Feb 10 2010, Feb 16 2010: (Start)
T(n, k) = A172119(n) mod 2.
T(n, k) = A175105(n) mod 2.
T(n, k) = Sum_{i=1..k-1} (T(n-i, k-1) - T(n-i, k)) for k > 1 and T(n, 1) = 1.
(Jeffrey O. Shallit kindly provided a clarification along with a proof of this formula.) (End)
A049820(n) = number of zeros in n-th row. - Reinhard Zumkeller, Mar 09 2010
The determinant of this matrix where T(n, n) has been swapped with T(1,k) is equal to the n-th term of the Mobius function. - Mats Granvik, Jul 21 2012
T(n, k) = Sum_{y=1..n} Sum_{x=1..n} [GCD((x/y)*(k/n), n) = k]. - Mats Granvik, Dec 17 2023

Edited by Peter Luschny, Oct 18 2023

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

Original entry on oeis.org

1, 1, 3, 6, 15, 27, 63, 120, 252, 495, 1023, 2010, 4095, 8127, 16365, 32640, 65535, 130788, 262143, 523770, 1048509, 2096127, 4194303, 8386440, 16777200, 33550335, 67108608, 134209530, 268435455, 536854005, 1073741823, 2147450880

Offset: 1

N. J. A. Sloane

Also number of compositions of n into relatively prime parts (that is, the gcd of all the parts is 1). Also number of subsets of {1,2,..,n} containing n and consisting of relatively prime numbers. - Vladeta Jovovic, Aug 13 2003
Also number of perfect parity patterns that have exactly n columns (see A118141). - Don Knuth, May 11 2006
a(n) is odd if and only if n is squarefree (Tim Keller). - Emeric Deutsch, Apr 27 2007
a(n) is a multiple of 3 for all n>=3 (see Problem 11161 link). - Emeric Deutsch, Aug 13 2008
Row sums of triangle A143424. - Gary W. Adamson, Aug 14 2008
a(n) is the number of monic irreducible polynomials with nonzero constant coefficient in GF(2)[x] of degree n. - Michel Marcus, Oct 30 2016
a(n) is the number of aperiodic compositions of n, the number of compositions of n with relatively prime parts, and the number of compositions of n with relatively prime run-lengths. - Gus Wiseman, Dec 21 2017

			For n=4, there are 6 compositions of n into coprime parts: <3,1>, <2,1,1>, <1,3>, <1,2,1>, <1,1,2>, and <1,1,1,1>.
From _Gus Wiseman_, Dec 19 2017: (Start)
The a(6) = 27 aperiodic compositions are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1221), (1311), (2112), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
The a(6) = 27 compositions into relatively prime parts are:
  (111111),
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1212), (1221), (1311), (2112), (2121), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (51).
The a(6) = 27 compositions with relatively prime run-lengths are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1131), (1212), (1221), (1311), (2112), (2121), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
(End)

H. O. Peitgen and P. H. Richter, The Beauty of Fractals, Springer-Verlag; contribution by A. Douady, p. 165.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 1..3322 (terms 1..300 from T. D. Noe)
Hunki Baek, Sejeong Bang, Dongseok Kim, and Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014. See Table 2.
Donald Knuth, Robin Chapman and Reiner Martin, Problem 11243, Perfect Parity Patterns, Am. Math. Monthly 115 (7) (2008) p 668, function c(n).
Emeric Deutsch and Lafayette College Problem Group, Problem 11161: Compositions without Common Factors, American Mathematical Monthly, vol. 114, No. 4, 2007, p. 363.
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.
J. E. Iglesias, A formula for the number of closest packings of equal spheres having a given repeat period, Z. Krist. 155 (1981) 121-127, Table 2.
Wolfdieter Lang, Cantor's List of Real Algebraic Numbers of Heights 1 to 7, arXiv:2307.10645 [math.NT], 2023.
Nicolae Mihalache and Francois Vigneron, Factorization of the quadratic Misiurewicz-Thurston polynomials, arXiv:2506.17662 [math.DS], 2025. See p. 8.
Robert Munafo, Enumeration of Period-N Mu-Atoms
Jeffrey Shallit and N. J. A. Sloane, Correspondence 1974-1975
François Vigneron and Nicolae Mihalache, How to split a tera-polynomial, arXiv:2402.06083 [math.NA], 2024.
Index entries for sequences related to Lyndon words

Cf. A000837, A003239, A008683, A008965, A022553, A034738, A035928, A038199, A051168, A054525, A056267, A059966, A143424, A167606, A178472, A216954, A228369, A294859, A296302.
Equals A027375/2.
See A056278 for a variant.
First differences of A085945.
Column k=2 of A143325.
Row sums of A101391.

with(numtheory): a[1]:=1: a[2]:=1: for n from 3 to 32 do div:=divisors(n): a[n]:=2^(n-1)-sum(a[n/div[j]],j=2..tau(n)) od: seq(a[n],n=1..32); # Emeric Deutsch, Apr 27 2007
with(numtheory); A000740:=n-> add(mobius(n/d)*2^(d-1), d in divisors(n)); # N. J. A. Sloane, Oct 18 2012

a[n_] := Sum[ MoebiusMu[n/d]*2^(d - 1), {d, Divisors[n]}]; Table[a[n], {n, 1, 32}] (* Jean-François Alcover, Feb 03 2012, after PARI *)

a(n) = sumdiv(n,d,moebius(n/d)*2^(d-1))

from sympy import mobius, divisors
def a(n): return sum([mobius(n // d) * 2**(d - 1) for d in divisors(n)])
[a(n) for n in range(1, 101)]  # Indranil Ghosh, Jun 28 2017

a(n) = Sum_{d|n} mu(n/d)*2^(d-1), Mobius transform of A011782. Furthermore, Sum_{d|n} a(d) = 2^(n-1).
a(n) = A027375(n)/2 = A038199(n)/2.
a(n) = Sum_{k=0..n} A051168(n,k)*k. - Max Alekseyev, Apr 09 2013
Recurrence relation: a(n) = 2^(n-1) - Sum_{d|n,d>1} a(n/d). (Lafayette College Problem Group; see the Maple program and Iglesias eq (6)). - Emeric Deutsch, Apr 27 2007
G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - Ilya Gutkovskiy, Oct 24 2018
G.f. satisfies Sum_{n>=1} A( (x/(1 + 2*x))^n ) = x. - Paul D. Hanna, Apr 02 2025

Connection with Mandelbrot set discovered by Warren D. Smith and proved by Robert Munafo, Feb 06 2000

Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012

A018804 Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n).

Original entry on oeis.org

1, 3, 5, 8, 9, 15, 13, 20, 21, 27, 21, 40, 25, 39, 45, 48, 33, 63, 37, 72, 65, 63, 45, 100, 65, 75, 81, 104, 57, 135, 61, 112, 105, 99, 117, 168, 73, 111, 125, 180, 81, 195, 85, 168, 189, 135, 93, 240, 133, 195, 165, 200, 105, 243, 189, 260, 185, 171, 117, 360

Offset: 1

David W. Wilson

a(n) is the number of times the number 1 appears in the character table of the cyclic group C_n. - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 02 2001
a(n) is the number of ways to express all fractions f/g whereby each product (f/g)*n is a natural number between 1 and n (using fractions of the form f/g with 1 <= f,g <= n). For example, for n=4 there are 8 such fractions: 1/1, 1/2, 2/2, 3/3, 1/4, 2/4, 3/4 and 4/4. - Ron Lalonde (ronronronlalonde(AT)hotmail.com), Oct 03 2002
Number of non-congruent solutions to xy == 0 (mod n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 06 2003
Conjecture: n>1 divides a(n)+1 iff n is prime. - Thomas Ordowski, Oct 22 2014
The above conjecture is false, with counterexample given by n = 3*37*43*42307*116341 and a(n)+1 = 26*n. - Varun Vejalla, Jun 19 2025
a(n) is the number of 0's in the multiplication table Z/nZ (cf. A000010 for number of 1's). - Eric Desbiaux, Jun 11 2015
{a(n)} == 1, 3, 1, 0, 1, 3, 1, 0, ... (mod 4). - Isaac Saffold, Dec 30 2017
Since a(p^e) = p^(e-1)*((p-1)e+p) it follows a(p) = 2p-1 and therefore p divides a(p)+1. - Ruediger Jehn, Jun 23 2022

			G.f. = x + 3*x^2 + 5*x^3 + 8*x^4 + 9*x^5 + 15*x^6 + 13*x^7 + 20*x^8 + ...

S. S. Pillai, On an arithmetic function, J. Annamalai University 2 (1933), pp. 243-248.
J. Sándor, A generalized Pillai function, Octogon Mathematical Magazine Vol. 9, No. 2 (2001), 746-748.

Seiichi Manyama, Table of n, a(n) for n = 1..10000 (first 2000 terms from T. D. Noe)
U. Abel, W. Awan, and V. Kushnirevych, A Generalization of the Gcd-Sum Function, J. Int. Seq. 16 (2013) #13.6.7.
Antal Bege, Hadamard product of GCD matrices, Acta Univ. Sapientiae, Mathematica, 1, 1 (2009) 43-49.
Olivier Bordelles, The Composition of the gcd and Certain Arithmetic Functions, J. Int. Seq. 13 (2010) #10.7.1.
Olivier Bordelles, An Asymptotic Formula for Short Sums of Gcd-Sum Functions, Journal of Integer Sequences, Vol. 15 (2012), #12.6.8.
Olivier Bordelles, A Multidimensional Cesáro Type Identity and Applications, J. Int. Seq. 18 (2015) # 15.3.7.
Kevin A. Broughan, The gcd-sum function, Journal of Integer Sequences 4 (2001), Article 01.2.2, 19 pp.
J.-M. De Koninck and I. Kátai, Some remarks on a paper of L. Toth, JIS 13 (2010) 10.1.2.
Pentti Haukkanen and László Tóth, Menon-type identities again: Note on a paper by Li, Kim and Qiao, arXiv:1911.05411 [math.NT], 2019.
Soichi Ikeda and Kaneaki Matsuoka, On the Lcm-Sum Function, Journal of Integer Sequences, Vol. 17 (2014), Article 14.1.7.
Mathematical Reflections, Solution to Problem O364, Issue 2, 2016, p 24. [Cached copy at Wayback Machine]
Taylor McAdam, Almost-primes in horospherical flows on the space of lattices, arXiv:1802.08764 [math.DS], 2018.
Taylor McAdam, Almost-prime times in horospherical flows on the space of lattices, Journal of Modern Dynamics (2019) Vol. 15, 277-327.
J. Ransford, A Sum of Gcd’s over Friable Numbers, JIS vol 19 (2016) # 16.3.2
Jeffrey Shallit, Problem E 2821, American Mathematical Monthly 87 (1980), 220.
Jeffrey Shallit, Solution, American Mathematical Monthly, 88 (1981), 444-445.
László Tóth, A gcd-sum function over regular integers modulo n, JIS 12 (2009) 09.2.5.
László Tóth, On the Bi-Unitary Analogues of Euler's Arithmetical Function and the Gcd-Sum Function, JIS 12 (2009) 09.5.2.
László Tóth, A survey of gcd-sum functions, J. Integer Sequences 13 (2010), Article 10.8.1, 23 pp.
László Tóth, Weighted gcd-sum functions, J. Integer Sequences, 14 (2011), Article 11.7.7.
D. Zhang and W. Zhai, Mean Values of a Gcd-Sum Function Over Regular Integers Modulo n, J. Int. Seq. 13 (2010), 10.4.7.
D. Zhang and W. Zhai, Mean Values of a Class of Arithmetical Functions, J. Int. Seq. 14 (2011) #11.6.5.
D. Zhang and W. Zhai, On an Open Problem of Tóth, J. Int. Seq. 16 (2013) #13.6.5.

Column 1 of A343510 and A343516.
Cf. A080997, A080998 for rankings of the positive integers in terms of centrality, defined to be the average fraction of an integer that it shares with the other integers as a gcd, or A018804(n)/n^2, also A080999, a permutation of this sequence (A080999(n) = A018804(A080997(n))).
Cf. A185210, A010766, A054523, A127468, A050873, A078430, A095026, A227507, A000010, A344372, A272718 (partial sums), A368736 - A368741.

a018804 n = sum $ map (gcd n) [1..n]  -- Reinhard Zumkeller, Jul 16 2012

[&+[Gcd(n,k):k in [1..n]]:n in [1..60]]; // Marius A. Burtea, Nov 14 2019

a:=n->sum(igcd(n,j),j=1..n): seq(a(n), n=1..60); # Zerinvary Lajos, Nov 05 2006

f[n_] := Block[{d = Divisors[n]}, Sum[ d*EulerPhi[n/d], {d, d}]]; Table[f[n], {n, 60}] (* Robert G. Wilson v, Mar 20 2012 *)
a[ n_] := If[ n < 1, 0, n Sum[ EulerPhi[d] / d, {d, Divisors@n}]]; (* Michael Somos, Jan 07 2017 *)
f[p_, e_] := (e*(p - 1)/p + 1)*p^e; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Jul 19 2019 *)

{a(n) = direuler(p=2, n, (1 - X) / (1 - p*X)^2)[n]}; /* Michael Somos, May 31 2000 */

a(n)={ my(ct=0); for(i=0,n-1,for(j=0,n-1, ct+=(Mod(i*j,n)==0) ) ); ct; } \\ Joerg Arndt, Aug 03 2013

a(n)=my(f=factor(n)); prod(i=1,#f~,(f[i,2]*(f[i,1]-1)/f[i,1] + 1)*f[i,1]^f[i,2]) \\ Charles R Greathouse IV, Oct 28 2014

a(n) = sumdiv(n, d, n*eulerphi(d)/d); \\ Michel Marcus, Jan 07 2017

from sympy.ntheory import totient, divisors
print([sum(n*totient(d)//d for d in divisors(n)) for n in range(1, 101)]) # Indranil Ghosh, Apr 04 2017

from sympy import factorint
from math import prod
def A018804(n): return prod(p**(e-1)*((p-1)*e+p) for p, e in factorint(n).items()) # Chai Wah Wu, Nov 29 2021

a(n) = Sum_{d|n} d*phi(n/d), where phi(n) is Euler totient function (cf. A000010). - Vladeta Jovovic, Apr 04 2001
Multiplicative; for prime p, a(p^e) = p^(e-1)*((p-1)e+p).
Dirichlet g.f.: zeta(s-1)^2/zeta(s).
a(n) = Sum_{d|n} d*tau(d)*mu(n/d). - Benoit Cloitre, Oct 23 2003
Equals A054523 * [1,2,3,...]. Equals row sums of triangle A010766. - Gary W. Adamson, May 20 2007
Equals inverse Mobius transform of A029935 = A054525 * (1, 2, 4, 5, 8, 8, 12, 12, ...). - Gary W. Adamson, Aug 02 2008, corrected Feb 07 2023
Equals row sums of triangle A127478. - Gary W. Adamson, Aug 03 2008
G.f.: Sum_{k>=1} phi(k)*x^k/(1 - x^k)^2, where phi(k) is the Euler totient function. - Ilya Gutkovskiy, Jan 02 2017
a(n) = Sum_{a = 1..n} Sum_{b = 1..n} Sum_{c = 1..n} 1, for n > 1. The sum is over a,b,c such that n*c - a*b = 0. - Benedict W. J. Irwin, Apr 04 2017
Proof: Let gcd(a, n) = g and x = n/g. Define B = {x, 2*x, ..., g*x}; then for all b in B there exists a number c such that a*b = n*c. Since the set B has g elements it follows that Sum_{b=1..n} Sum_{c=1..n} 1 >= g = gcd(a, n) and therefore Sum_{a=1..n} Sum_{b=1..n} Sum_{c=1..n} 1 >= Sum_{a=1..n} gcd(a, n). On the other hand, for all b not in B there is no number c <= n such that a*b = n*c and hence Sum_{b = 1..n} Sum_{c = 1..n} 1 = g. Therefore Sum_{a=1..n} Sum_{b = 1..n} Sum_{c = 1..n} 1 = a(n). - Ruediger Jehn, Jun 23 2022
a(2*n) = a(n)*(3-A007814(n)/(A007814(n)+2)) - Velin Yanev, Jun 30 2017
Proof: Let m = A007814(m) and decompose n into n = k*2^m. We know from Chai Wah Wu's program below that a(n) = Product(p_i^(e_i-1)*((p_i-1)*e_i+p_i)) where the numbers p_i are the prime factors of n and e_i are the corresponding exponents. Hence a(2n) = 2^m*(m+3)*a(k) = 2^m*(m+3)*a(k). On the other hand, a(n) = 2^(m-1)*(m+2)*a(k). Dividing the first equation by the second yields a(2n)/a(n) = 2*(m+3)/(m+2), which equals 3 - m/(m+2). Hence a(2n) = a(n)*(3 - m/(m+2)). - Ruediger Jehn, Jun 23 2022
Sum_{k=1..n} a(k) ~ 3*n^2/Pi^2 * (log(n) - 1/2 + 2*gamma - 6*Zeta'(2)/Pi^2), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Feb 08 2019
a(n) = Sum_{k=1..n} n/gcd(n,k)*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 10 2021
log(a(n)/n) << log n log log log n/log log n; in particular, a(n) << n^(1+e) for any e > 0. See Broughan link for bounds in terms of omega(n). - Charles R Greathouse IV, Sep 08 2022
a(n) = (1/4)*Sum_{k = 1..4*n} (-1)^k * gcd(k, 4*n) = (1/4) * A344372(2*n). - Peter Bala, Jan 01 2024

A036987 Fredholm-Rueppel sequence.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane

Binary representation of the Kempner-Mahler number Sum_{k>=0} 1/2^(2^k) = A007404.
Also a(n) = A(n) mod 2 where A is any of A001700, A005573, A007854, A026641, A049027, A064063, A064088, A064090, A064092, A064325, A064327, A064329, A064331, A064613, A076026, A105523, A123273, A126694, A126930, A126931, A126982, A126983, A126987, A127016, A127053, A127358, A127360, A127361, A127363. - Philippe Deléham, May 26 2007
a(n) = (product of digits of n; n in binary notation) mod 2. This sequence is a transformation of the Thue-Morse sequence (A010060), since there exists a function f such that f(sum of digits of n) = (product of digits of n). - Ctibor O. Zizka, Feb 12 2008
a(n-1), n >= 1, the characteristic sequence for powers of 2, A000079, is the unique solution of the following formal product and formal power series identity: Product_{j>=1} (1 + a(j-1)*x^j) = 1 + Sum_{k>=1} x^k = 1/(1-x). The product is therefore Product_{l>=1} (1 + x^(2^l)). Proof. Compare coefficients of x^n and use the binary representation of n. Uniqueness follows from the recurrence relation given for the general case under A147542. - Wolfdieter Lang, Mar 05 2009
a(n) is also the number of orbits of length n for the map x -> 1-cx^2 on [-1,1] at the Feigenbaum critical value c=1.401155... . - Thomas Ward, Apr 08 2009
A054525 (Mobius transform) * A001511 = A036987 = A047999^(-1) * A001511 = the inverse of Sierpiński's gasket * the ruler sequence. - Gary W. Adamson, Oct 26 2009 [Of course this is only vaguely correct depending on how the fuzzy indexing in these formulas is made concrete. - R. J. Mathar, Jun 20 2014]
Characteristic function of A000225. - Reinhard Zumkeller, Mar 06 2012
Also parity of the Catalan numbers A000108. - Omar E. Pol, Jan 17 2012
For n >= 2, also the largest exponent k >= 0 such that n^k in binary notation does not contain both 0 and 1. Unlike for the decimal version of this sequence, A062518, where the terms are only conjectural, for this sequence the values of a(n) can be proved to be the characteristic function of A000225, as follows: n^k will contain both 0 and 1 unless n^k = 2^r-1 for some r. But this is a special case of Catalan's equation x^p = y^q-1, which was proved by Preda Mihăilescu to have no nontrivial solution except 2^3 = 3^2 - 1. - Christopher J. Smyth, Aug 22 2014
Image, under the coding a,b -> 1; c -> 0, of the fixed point, starting with a, of the morphism a -> ab, b -> cb, c -> cc. - Jeffrey Shallit, May 14 2016
Number of nonisomorphic Boolean algebras of order n+1. - Jianing Song, Jan 23 2020

			G.f. = 1 + x + x^3 + x^7 + x^15 + x^31 + x^63 + x^127 + x^255 + x^511 + ...
a(7) = 1 since 7 = 2^3 - 1, while a(10) = 0 since 10 is not of the form 2^k - 1 for any integer k.

Antti Karttunen, Table of n, a(n) for n = 0..65537
D. Bailey et al., On the binary expansions of algebraic numbers, Journal de Théorie des Nombres de Bordeaux 16 (2004), 487-518.
Paul Barry, Some observations on the Rueppel sequence and associated Hankel determinants, arXiv:2005.04066 [math.CO], 2020.
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
Mats Granvik, Mathematica program for computing Fredholm Rueppel sequences
D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions, in Sequences and their Applications, C. Ding, T. Helleseth, and H. Niederreiter, eds., Proceedings of SETA'98 (Singapore, 1998), 308-317, 1999.
Preda Mihăilescu, Primary Cyclotomic Units and a Proof of Catalan's Conjecture, J. Reine angew. Math. 572 (2004): 167-195. doi:10.1515/crll.2004.048. MR 2076124.
H. Niederreiter and M. Vielhaber, Tree Complexity and a Doubly Exponential Gap between Structured and Random Sequences, J. Complexity, 12 (1996), 187-198.
Apisit Pakapongpun and Thomas Ward, Functorial orbit counting, Journal of Integer Sequences, 12 (2009) Article 09.2.4. [From _Thomas Ward_, Apr 08 2009]
Eric Rowland and Reem Yassawi, Profinite automata, arXiv:1403.7659 [math.DS], 2014. See p. 8.
E. Sheppard, net.math post (1985)
Stephen Wolfram, [Page 1092] A New Kind of Science | Online.
Index entries for characteristic functions

Cf. A007404, A043545, A062518, A078885, A078585, A078886, A078887, A078888, A078889, A078890.
The first row of A073346. Occurs for first time in A073202 as row 6 (and again as row 8).
Congruent to any of the sequences A000108, A007460, A007461, A007463, A007464, A061922, A068068 reduced modulo 2. Characteristic function of A000225.
If interpreted with offset=1 instead of 0 (i.e., a(1)=1, a(2)=1, a(3)=0, a(4)=1, ...) then this is the characteristic function of 2^n (A000079) and as such occurs as the first row of A073265. Also, in that case the INVERT transform will produce A023359.
This is Guy Steele's sequence GS(1, 3), also GS(3, 1) (see A135416).
Cf. A054525, A047999. - Gary W. Adamson, Oct 26 2009
Cf. A043529, A127802.

a036987 n = ibp (n+1) where
   ibp 1 = 1
   ibp n = if r > 0 then 0 else ibp n' where (n',r) = divMod n 2
a036987_list = 1 : f [0,1] where f (x:y:xs) = y : f (x:xs ++ [x,x+y])
-- Same list generator function as for a091090_list, cf. A091090.
-- Reinhard Zumkeller, May 19 2015, Apr 13 2013, Mar 13 2013

A036987:= n-> `if`(2^ilog2(n+1) = n+1, 1, 0):
seq(A036987(n), n=0..128);

RealDigits[ N[ Sum[1/10^(2^n), {n, 0, Infinity}], 110]][[1]]
(* Recurrence: *)
t[n_, 1] = 1; t[1, k_] = 1;
t[n_, k_] := t[n, k] =
  If[n < k, If[n > 1 && k > 1, -Sum[t[k - i, n], {i, 1, n - 1}], 0],
   If[n > 1 && k > 1, Sum[t[n - i, k], {i, 1, k - 1}], 0]];
Table[t[n, k], {k, n, n}, {n, 104}]
(* Mats Granvik, Jun 03 2011 *)
mb2d[n_]:=1 - Module[{n2 = IntegerDigits[n, 2]}, Max[n2] - Min[n2]]; Array[mb2d, 120, 0] (* Vincenzo Librandi, Jul 19 2019 *)
Table[PadRight[{1},2^k,0],{k,0,7}]//Flatten (* Harvey P. Dale, Apr 23 2022 *)

{a(n) =( n++) == 2^valuation(n, 2)}; /* Michael Somos, Aug 25 2003 */

a(n) = !bitand(n, n+1); \\ Ruud H.G. van Tol, Apr 05 2023

from sympy import catalan
def a(n): return catalan(n)%2 # Indranil Ghosh, May 25 2017

def A036987(n): return int(not(n&(n+1))) # Chai Wah Wu, Jul 06 2022

1 followed by a string of 2^k - 1 0's. Also a(n)=1 iff n = 2^m - 1.
a(n) = a(floor(n/2)) * (n mod 2) for n>0 with a(0)=1. - Reinhard Zumkeller, Aug 02 2002 [Corrected by Mikhail Kurkov, Jul 16 2019]
Sum_{n>=0} 1/10^(2^n) = 0.110100010000000100000000000000010...
1 if n=0, floor(log_2(n+1)) - floor(log_2(n)) otherwise. G.f.: (1/x) * Sum_{k>=0} x^(2^k) = Sum_{k>=0} x^(2^k-1). - Ralf Stephan, Apr 28 2003
a(n) = 1 - A043545(n). - Michael Somos, Aug 25 2003
a(n) = -Sum_{d|n+1} mu(2*d). - Benoit Cloitre, Oct 24 2003
Dirichlet g.f. for right-shifted sequence: 2^(-s)/(1-2^(-s)).
a(n) = A000108(n) mod 2 = A001405(n) mod 2. - Paul Barry, Nov 22 2004
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*Sum_{j=0..k} binomial(k, 2^j-1). - Paul Barry, Jun 01 2006
A000523(n+1) = Sum_{k=1..n} a(k). - Mitch Harris, Jul 22 2011
a(n) = A209229(n+1). - Reinhard Zumkeller, Mar 07 2012
a(n) = Sum_{k=1..n} A191898(n,k)*cos(Pi*(n-1)*(k-1))/n; (conjecture). - Mats Granvik, Mar 04 2013
a(n) = A000035(A000108(n)). - Omar E. Pol, Aug 06 2013
a(n) = 1 iff n=2^k-1 for some k, 0 otherwise. - M. F. Hasler, Jun 20 2014
a(n) = ceiling(log_2(n+2)) - ceiling(log_2(n+1)). - Gionata Neri, Sep 06 2015
From John M. Campbell, Jul 21 2016: (Start)
a(n) = (A000168(n-1) mod 2).
a(n) = (A000531(n+1) mod 2).
a(n) = (A000699(n+1) mod 2).
a(n) = (A000891(n) mod 2).
a(n) = (A000913(n-1) mod 2), for n>1.
a(n) = (A000917(n-1) mod 2), for n>0.
a(n) = (A001142(n) mod 2).
a(n) = (A001246(n) mod 2).
a(n) = (A001246(n) mod 4).
a(n) = (A002057(n-2) mod 2), for n>1.
a(n) = (A002430(n+1) mod 2). (End)
a(n) = 2 - A043529(n). - Antti Karttunen, Nov 19 2017
a(n) = floor(1+log(n+1)/log(2)) - floor(log(2n+1)/log(2)). - Adriano Caroli, Sep 22 2019
This is also the decimal expansion of -Sum_{k>=1} mu(2*k)/(10^k - 1), where mu is the Möbius function (A008683). - Amiram Eldar, Jul 12 2020

Edited by M. F. Hasler, Jun 20 2014

A054523 Triangle read by rows: T(n,k) = phi(n/k) if k divides n, T(n,k)=0 otherwise (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 2, 0, 1, 2, 1, 0, 1, 4, 0, 0, 0, 1, 2, 2, 1, 0, 0, 1, 6, 0, 0, 0, 0, 0, 1, 4, 2, 0, 1, 0, 0, 0, 1, 6, 0, 2, 0, 0, 0, 0, 0, 1, 4, 4, 0, 0, 1, 0, 0, 0, 0, 1, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 2, 2, 2, 0, 1, 0, 0, 0, 0, 0, 1, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 6

Offset: 1

N. J. A. Sloane, Apr 09 2000

From Gary W. Adamson, Jan 08 2007: (Start)
Let H be this lower triangular matrix. Then:
H * A051731 = A126988,
H * [1, 2, 3, ...] = 1, 3, 5, 8, 9, 15, ... = A018804,
H * sigma(n) = A038040 = d(n) * n = 1, 4, 6, 12, 10, ... where sigma(n) = A000203,
H * d(n) (A000005) = sigma(n) = A000203,
Row sums are A000027 (corrected by Werner Schulte, Sep 06 2020, see comment of Gary W. Adamson, Aug 03 2008),
H^2 * d(n) = d(n)*n, H^2 = A127192,
H * mu(n) (A008683) = A007431(n) (corrected by Werner Schulte, Sep 06 2020),
H^2 row sums = A018804. (End)
The Möbius inversion principle of Richard Dedekind and Joseph Liouville (1857), cf. "Concrete Mathematics", p. 136, is equivalent to the statement that row sums are the row index n. - Gary W. Adamson, Aug 03 2008
The multivariable row polynomials give n times the cycle index for the cyclic group C_n, called Z(C_n) (see the MathWorld link with the Harary reference): n*Z(C_n) = Sum_{k=1..n} T(n,k)*(y_{n/k})^k, n >= 1. E.g., 6*Z(C_6) = 2*(y_6)^1 + 2*(y_3)^2 + 1*(y_2)^3 + 1*(y_1)^6. - Wolfdieter Lang, May 22 2012
See A102190 (no 0's, rows reversed). - Wolfdieter Lang, May 29 2012
This is the number of permutations in the n-th cyclic group which are the product of k disjoint cycles. - Robert A. Beeler, Aug 09 2013

			Triangle begins
   1;
   1, 1;
   2, 0, 1;
   2, 1, 0, 1;
   4, 0, 0, 0, 1;
   2, 2, 1, 0, 0, 1;
   6, 0, 0, 0, 0, 0, 1;
   4, 2, 0, 1, 0, 0, 0, 1;
   6, 0, 2, 0, 0, 0, 0, 0, 1;
   4, 4, 0, 0, 1, 0, 0, 0, 0, 1;
  10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
   4, 2, 2, 2, 0, 1, 0, 0, 0, 0, 0, 1;

Ronald L. Graham, D. E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, p. 136.

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
Eric Weisstein's World of Mathematics, Cycle Index.

Cf. A000005, A000007, A000010, A000012, A000203, A007431, A008683.
Cf. A038040, A051731, A054521, A054525, A102190, A126988.
Sums incliude: A029935, A069097, A092843 (diagonal), A209295.
Sums of the form Sum_{k} k^p * T(n, k): A000027 (p=0), A018804 (p=1), A069097 (p=2), A343497 (p=3), A343498 (p=4), A343499 (p=5).

a054523 n k = a054523_tabl !! (n-1) !! (k-1)
a054523_row n = a054523_tabl !! (n-1)
a054523_tabl = map (map (\x -> if x == 0 then 0 else a000010 x)) a126988_tabl
-- Reinhard Zumkeller, Jan 20 2014

A054523:= func< n,k | k eq n select 1 else (n mod k) eq 0 select EulerPhi(Floor(n/k)) else 0 >;
[A054523(n,k): k in [1..n], n in [1..15]]; // G. C. Greubel, Jun 24 2024

A054523 := proc(n,k) if n mod k = 0 then numtheory[phi](n/k) ; else 0; end if; end proc: # R. J. Mathar, Apr 11 2011

T[n_, k_]:= If[k==n,1,If[Divisible[n, k], EulerPhi[n/k], 0]];
Table[T[n,k], {n,15}, {k,n}]//Flatten (* G. C. Greubel, Dec 15 2017 *)

for(n=1, 10, for(k=1, n, print1(if(!(n % k), eulerphi(n/k), 0), ", "))) \\ G. C. Greubel, Dec 15 2017

def A054523(n,k):
    if (k==n): return 1
    elif (n%k)==0: return euler_phi(int(n//k))
    else: return 0
flatten([[A054523(n,k) for k in range(1,n+1)] for n in range(1,16)]) # G. C. Greubel, Jun 24 2024

Sum_{k=1..n} k * T(n, k) = A018804(n). - Gary W. Adamson, Jan 08 2007
Equals A054525 * A126988 as infinite lower triangular matrices. - Gary W. Adamson, Aug 03 2008
From Werner Schulte, Sep 06 2020: (Start)
Sum_{k=1..n} T(n,k) * A000010(k) = A029935(n) for n > 0.
Sum_{k=1..n} k^2 * T(n,k) = A069097(n) for n > 0. (End)
From G. C. Greubel, Jun 24 2024: (Start)
T(2*n-1, n) = A000007(n-1), n >= 1.
T(2*n, n) = A000012(n), n >= 1.
Sum_{k=1..n} (-1)^(k-1)*T(n, k) = (1 - (-1)^n)*n/2.
Sum_{k=1..floor(n+1)/2} T(n-k+1, k) = A092843(n+1).
Sum_{k=1..n} (k+1)*T(n, k) = A209295(n).
Sum_{k=1..n} k^3 * T(n, k) = A343497(n).
Sum_{k=1..n} k^4 * T(n, k) = A343498(n).
Sum_{k=1..n} k^5 * T(n, k) = A343499(n). (End)

A127473 a(n) = phi(n)^2.

Original entry on oeis.org

1, 1, 4, 4, 16, 4, 36, 16, 36, 16, 100, 16, 144, 36, 64, 64, 256, 36, 324, 64, 144, 100, 484, 64, 400, 144, 324, 144, 784, 64, 900, 256, 400, 256, 576, 144, 1296, 324, 576, 256, 1600, 144, 1764, 400, 576, 484, 2116, 256, 1764, 400, 1024, 576, 2704, 324, 1600

Offset: 1

Gary W. Adamson, Jan 15 2007

Number of maps of the form j |--> m*j + d with gcd(m, n) = 1 and gcd(d, n) = 1 from [1, 2, ..., n] to itself. - Joerg Arndt, Aug 29 2014
Right border of A127474.
Equals the Mobius transform (A054525) of A029939. - Gary W. Adamson, Aug 20 2008
From Jianing Song, Apr 14 2019: (Start)
a(n) is the number of solutions to gcd(xy, n) = 1 with x, y in [0, n-1].
Let Z_n be the ring of integers modulo n, then a(n) is the number of invertible elements in the ring Z_n[x]/(x^2 - x) (or equivalently, Z_n[x]/(x^2 + x)) with discriminant d = 1 (that is, a(n) is the size of the group G(n) = (Z_n[x]/(x^2 - x))*). Actually, G(n) is isomorphic to (Z_n)* X (Z_n)*. (End)

			a(5) = 16 since phi(5) = 4.

Jens Kruse Andersen, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence).

Cf. A000010, A057434, A065464, A109695, A127474, A358714, A361148, A008683.

Similar sequences: A082953 (size of (Z_n[x]/(x^2 - 1))*, d = 4), A002618 ((Z_n[x]/(x^2))*, d = 0), A079458 ((Z_n[x]/(x^2 + 1))*, d = -4), A319445 ((Z_n[x]/(x^2 - x + 1))* or (Z_n[x]/(x^2 + x + 1))*, d = -3).

[(EulerPhi(n))^2: n in [1..180]]; // Vincenzo Librandi, Apr 04 2011

A127473 := proc(n) numtheory[phi](n)^2 ; end proc:
seq(A127473(n),n=1..40) ; # R. J. Mathar, Apr 04 2011

Table[EulerPhi[n]^2,{n,100}] (* Vladimir Joseph Stephan Orlovsky, Feb 02 2012 *)

a(n) = eulerphi(n)^2; \\ Michel Marcus, Oct 16 2018

a(n) = A000010(n)^2.
Multiplicative with a(p^e) = (p-1)^2*p^(2e-2), e >= 1. Dirichlet g.f. zeta(s-2)*Product_{primes p} (1 - 2/p^(s-1) + 1/p^s). - R. J. Mathar, Apr 04 2011
Sum_{k>=1} 1/a(k) = A109695. - Vaclav Kotesovec, Sep 20 2020
Sum_{k>=1} (-1)^k/a(k) = (1/7) * A109695. - Amiram Eldar, Nov 11 2020
Sum_{k=1..n} a(k) ~ c * n^3, where c = (1/3) * Product_{p prime}(1 - (2*p-1)/p^3) = A065464 / 3 = 0.142749... . - Amiram Eldar, Oct 25 2022
a(n) = Sum_{d|n} mu(n/d)*phi(n*d). - Ridouane Oudra, Jul 23 2025

A143324 Table T(n,k) by antidiagonals. T(n,k) is the number of length n primitive (=aperiodic or period n) k-ary words (n,k >= 1).

Original entry on oeis.org

1, 2, 0, 3, 2, 0, 4, 6, 6, 0, 5, 12, 24, 12, 0, 6, 20, 60, 72, 30, 0, 7, 30, 120, 240, 240, 54, 0, 8, 42, 210, 600, 1020, 696, 126, 0, 9, 56, 336, 1260, 3120, 4020, 2184, 240, 0, 10, 72, 504, 2352, 7770, 15480, 16380, 6480, 504, 0, 11, 90, 720, 4032, 16800, 46410, 78120, 65280, 19656, 990, 0

Offset: 1

Alois P. Heinz, Aug 07 2008

Column k is Dirichlet convolution of mu(n) with k^n.

The coefficients of the polynomial of row n are given by the n-th row of triangle A054525; for example row 4 has polynomial -k^2+k^4.

			T(2,3)=6, because there are 6 primitive words of length 2 over 3-letter alphabet {a,b,c}: ab, ac, ba, bc, ca, cb; note that the non-primitive words aa, bb and cc don't belong to the list; secondly note that the words in the list need not be Lyndon words, for example ba can be derived from ab by a cyclic rotation of the positions.
Table begins:
  1,  2,   3,    4,    5, ...
  0,  2,   6,   12,   20, ...
  0,  6,  24,   60,  120, ...
  0, 12,  72,  240,  600, ...
  0, 30, 240, 1020, 3120, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
C. J. Smyth, A coloring proof of a generalisation of Fermat's little theorem, Amer. Math. Monthly 93, No. 6 (1986), pp. 469-471.
Lucas Vieira Barbosa, Nonclassical Temporal Correlations Under Finite-Memory Constraints, Doctoral Thesis, Univ. Wien (Austria 2024). See p. 35.
Index entries for sequences related to Lyndon words

Columns k=1-10 give: A000007(n-1), A027375, A054718, A054719, A054720, A054721, A218124, A218125, A218126, A218127.
Rows n=1-10 give: A000027, A002378(k-1), A007531(k+1), A047928(k+1), A061167, A218130, A133499, A218131, A218132, A218133.
Main diagonal gives A252764.
Cf. A074650, A143325, A008683, A054525.

with(numtheory): f0:= proc(n) option remember; unapply(k^n-add(f0(d)(k), d=divisors(n)minus{n}), k) end; T:= (n,k)-> f0(n)(k); seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

f0[n_] := f0[n] = Function [k, k^n - Sum[f0[d][k], {d, Complement[Divisors[n], {n}]}]]; t[n_, k_] := f0[n][k]; Table[Table[t[n, 1 + d - n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Dec 12 2013, translated from Maple *)

T(n,k) = Sum_{d|n} k^d * mu(n/d).

T(n,k) = k^n - Sum_{d

T(n,k) = A143325(n,k) * k.

T(n,k) = A074650(n,k) * n.

So Sum_{d|n} k^d * mu(n/d) == 0 (mod n), this is a generalization of Fermat's little theorem k^p - k == 0 (mod p) for primes p to an arbitrary modulus n (see the Smyth link). - Franz Vrabec, Feb 09 2021

A112467 Riordan array ((1-2x)/(1-x), x/(1-x)).

Original entry on oeis.org

1, -1, 1, -1, 0, 1, -1, -1, 1, 1, -1, -2, 0, 2, 1, -1, -3, -2, 2, 3, 1, -1, -4, -5, 0, 5, 4, 1, -1, -5, -9, -5, 5, 9, 5, 1, -1, -6, -14, -14, 0, 14, 14, 6, 1, -1, -7, -20, -28, -14, 14, 28, 20, 7, 1, -1, -8, -27, -48, -42, 0, 42, 48, 27, 8, 1, -1, -9, -35, -75, -90, -42, 42, 90, 75, 35, 9, 1, -1, -10, -44, -110, -165, -132, 0, 132, 165, 110

Offset: 0

Paul Barry, Sep 06 2005

Row sums are A000007. Diagonal sums are -F(n-2). Inverse is A112468. T(2n,n)=0.
(-1,1)-Pascal triangle. - Philippe Deléham, Aug 07 2006
Apart from initial term, same as A008482. - Philippe Deléham, Nov 07 2006
Each column equals the cumulative sum of the previous column. - Mats Granvik, Mar 15 2010
Reading along antidiagonals generates in essence rows of A192174. - Paul Curtz, Oct 02 2011
Triangle T(n,k), read by rows, given by (-1,2,0,0,0,0,0,0,0,...) DELTA (1,0,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 01 2011

			Triangle starts:
    1;
   -1,  1;
   -1,  0,   1;
   -1, -1,   1,   1;
   -1, -2,   0,   2,   1;
   -1, -3,  -2,   2,   3,   1;
   -1, -4,  -5,   0,   5,   4,  1;
   -1, -5,  -9,  -5,   5,   9,  5,  1;
   -1, -6, -14, -14,   0,  14, 14,  6,  1;
   -1, -7, -20, -28, -14,  14, 28, 20,  7,  1;
   -1, -8, -27, -48, -42,   0, 42, 48, 27,  8, 1;
   -1, -9, -35, -75, -90, -42, 42, 90, 75, 35, 9, 1;
  ...
From _Paul Barry_, Apr 08 2011: (Start)
Production matrix begins:
   1,  1,
  -2, -1,  1,
   2,  0, -1,  1,
  -2,  0,  0, -1,  1,
   2,  0,  0,  0, -1,  1,
  -2,  0,  0,  0,  0, -1,  1,
   2,  0,  0,  0,  0,  0, -1,  1
  ... (End)

G. C. Greubel, Rows n = 0..100 of triangle, flattened
Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, Restricting Dyck Paths and 312-avoiding Permutations, arXiv:2307.02837 [math.CO], 2023. Mentions this sequence.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Emeric Deutsch, L. Ferrari and S. Rinaldi, Production Matrices, Advances in Mathematics, 34 (2005) pp. 101-122.
D. Foata and G.-N. Han, The doubloon polynomial triangle, Ram. J. 23 (2010), 107-126.
Jack Ramsay, On Arithmetical Triangles, The Pulse of Long Island, June 1965. [Mentions application to design of antenna arrays. Annotated scan.]

Same first 3 rows as in A054525.

Cf. A008482, A037012, A080232, A112466, A112467, A174293, A174294, A174295, A174296, A174297.

[n eq 0 select 1 else (2*k-n)*Binomial(n,k)/n: k in [0..n], n in [0..10]]; // G. C. Greubel, Dec 04 2019

seq(seq( `if`(n=0, 1, (2*k-n)*binomial(n,k)/n), k=0..n), n=0..10); # G. C. Greubel, Dec 04 2019

T[n_, k_]= If[n==0, 1, ((2*k-n)/n)*Binomial[n, k]]; Table[T[n, k], {n, 0, 10}, {k, 0, n}]//Flatten (* Roger L. Bagula, Feb 16 2009; modified by G. C. Greubel, Dec 04 2019 *)

T(n, k) = if(n==0, 1, (2*k-n)*binomial(n,k)/n ); \\ G. C. Greubel, Dec 04 2019

def T(n, k):
    if (n==0): return 1
    else: return (2*k-n)*binomial(n,k)/n
[[T(n, k) for k in (0..n)] for n in (0..10)] # G. C. Greubel, Dec 04 2019

Number triangle T(n, k) = binomial(n, n-k) - 2*binomial(n-1, n-k-1).
Sum_{k=0..n} T(n, k)*x^k = (x-1)*(x+1)^(n-1). - Philippe Deléham, Oct 03 2005
T(n,k) = ((2*k-n)/n)*binomial(n, k), with T(0,0)=1. - Roger L. Bagula, Feb 16 2009; modified by G. C. Greubel, Dec 04 2019
T(n,k) = T(n-1,k-1) + T(n-1,k) with T(0,0)=1, T(1,0)=-1, T(n,k)=0 for k>n or for n<0. - Philippe Deléham, Nov 01 2011
G.f.: (1-2x)/(1-(1+y)*x). - Philippe Deléham, Dec 15 2011
Sum_{k=0..n} T(n,k)*x^k = A000007(n), A133494(n), A081294(n), A005053(n), A067411(n), A199661(n), A083233(n) for x = 1, 2, 3, 4, 5, 6, 7, respectively. - Philippe Deléham, Dec 15 2011
exp(x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)*(-1 - x + x^2/2! + x^3/3!) = -1 - 2*x - 2*x^2/2! + 5*x^4/4! + 14*x^5/5! + .... The same property holds more generally for Riordan arrays of the form ( f(x), x/(1 - x) ). - Peter Bala, Dec 21 2014
Sum_{k=0..n} T(n,k) = 0^n = A000007(n). - G. C. Greubel, Dec 04 2019

A143325 Table T(n,k) by antidiagonals. T(n,k) is the number of length n primitive (=aperiodic or period n) k-ary words (n,k >= 1) which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 3, 8, 6, 0, 1, 4, 15, 24, 15, 0, 1, 5, 24, 60, 80, 27, 0, 1, 6, 35, 120, 255, 232, 63, 0, 1, 7, 48, 210, 624, 1005, 728, 120, 0, 1, 8, 63, 336, 1295, 3096, 4095, 2160, 252, 0, 1, 9, 80, 504, 2400, 7735, 15624, 16320, 6552, 495, 0, 1, 10, 99

Offset: 1

Alois P. Heinz, Aug 07 2008

Column k is Dirichlet convolution of mu(n) with k^(n-1). The coefficients of the polynomial of row n are given by the n-th row of triangle A054525; for example row 4 has polynomial -k+k^3.

			T(4,2)=6, because 6 words of length 4 over 2-letter alphabet {a,b} are primitive and earlier than others derived by cyclic shifts of the alphabet: aaab, aaba, aabb, abaa, abba, abbb; note that aaaa and abab are not primitive and words beginning with b can be derived by shifts of the alphabet from words in the list; secondly note that the words in the list need not be Lyndon words, for example aaba can be derived from aaab by a cyclic rotation of the positions.
Table begins:
  1,   1,    1,     1,     1,      1,      1,       1, ...
  0,   1,    2,     3,     4,      5,      6,       7, ...
  0,   3,    8,    15,    24,     35,     48,      63, ...
  0,   6,   24,    60,   120,    210,    336,     504, ...
  0,  15,   80,   255,   624,   1295,   2400,    4095, ...
  0,  27,  232,  1005,  3096,   7735,  16752,   32697, ...
  0,  63,  728,  4095, 15624,  46655, 117648,  262143, ...
  0, 120, 2160, 16320, 78000, 279720, 823200, 2096640, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Index entries for sequences related to Lyndon words

Columns k=1-10 give: A063524, A000740, A034741, A295505, A295506, A320071, A320072, A320073, A320074, A320075.
Rows n=1-5, 7 give: A000012, A001477, A005563, A007531, A123865, A123866.
Main diagonal gives A075147.
Cf. A074650, A143324, A008683, A054525.

with(numtheory):
f1:= proc(n) option remember;
       unapply(k^(n-1)-add(f1(d)(k), d=divisors(n)minus{n}), k)
     end;
T:= (n,k)-> f1(n)(k);
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

t[n_, k_] := Sum[k^(d-1)*MoebiusMu[n/d], {d, Divisors[n]}]; Table[t[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jan 21 2014, from first formula *)

T(n,k) = Sum_{d|n} k^(d-1) * mu(n/d).

T(n,k) = k^(n-1) - Sum_{d

T(n,k) = A074650(n,k) * n/k.

T(n,k) = A143324(n,k) / k.

Previous Showing 51-60 of 99 results. Next

cp's OEIS Frontend

A051953 Cototient(n) := n - phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A051731 Triangle read by rows: T(n, k) = 1 if k divides n, T(n, k) = 0 otherwise, for 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A018804 Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Formula

A036987 Fredholm-Rueppel sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs