A002618 -id:A002618 - cp's OEIS frontend

A327170 Number of divisors d of n such that A327171(d) (= phi(d)*core(d)) is equal to n.

1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 2, 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, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Antti Karttunen, Sep 28 2019

nonn

From any solution (*) to A327171(d) = d*phi(d) = n, we obtain a solution for core(d')*phi(d') = n by forming a "pumped up" version d' of d, by replacing each exponent e_i in the prime factorization of d = p_1^e_1 * p_2^e_2 * ... * p_k^e_k, with exponent 2*e_i - 1 so that d' = p_1^(2*e_1 - 1) * p_2^(2*e_2 - 1)* ... * p_k^(2*e_k - 1) = A102631(d) = d*A003557(d), and this d' is also a divisor of n, as n = d' * A173557(d). Generally, any product m = p_1^(2*e_1 - x) * p_2^(2*e_2 - y)* ... * p_k^(2*e_k - z), where each x, y, ..., z is either 0 or 1 gives a solution for core(m)*phi(m) = n, thus every nonzero term in this sequence is a power of 2, even though not all such m's might be divisors of n.
  (* by necessity unique, see Franz Vrabec's Dec 12 2012 comment in A002618).
On the other hand, if we have any solution d for core(d)*phi(d) = n, we can find the unique such divisor e of d that e*phi(e) = n by setting e = A019554(d).
Thus, it follows that the nonzero terms in this sequence occur exactly at positions given by A082473.
Records (1, 2, 4, 8, 16, ...) occur at n = 1, 12, 504, 223200, 50097600, ...

			For n = 504 = 2^3 * 3^2 * 7, it has 24 divisors, out of which four divisors: 42 (= 2^1 * 3^1 * 7^1), 84 (= 2^2 * 3^1 * 7^1), 126 (= 2^1 * 3^2 * 7^1), 252 (= 2^2 * 3^2 * 7^1) are such that A007913(d)*A000010(d) = 504, thus a(504) = 4.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A002618, A003557, A007913, A019554, A082473, A102631, A173557, A194507, A327171.

Cf. also A327153, A327166, A327169.

With[{s = Array[EulerPhi[#] (Sqrt@ # /. (c_: 1) a_^(b_: 0) :> (c a^b)^2) &, 120]}, Table[DivisorSum[n, 1 &, s[[#]] == n &], {n, Length@ s}]] (* Michael De Vlieger, Sep 29 2019, after Bill Gosper at A007913 *)

A327170(n) = sumdiv(n,d,eulerphi(d)*core(d) == n);

a(n) = Sum_{d|n} [A000010(d)*A007913(d) == n], where [ ] is the Iverson bracket.

A327171 a(n) = phi(n) * core(n), where phi is Euler totient function, and core gives the squarefree part of n.

Original entry on oeis.org

1, 2, 6, 2, 20, 12, 42, 8, 6, 40, 110, 12, 156, 84, 120, 8, 272, 12, 342, 40, 252, 220, 506, 48, 20, 312, 54, 84, 812, 240, 930, 32, 660, 544, 840, 12, 1332, 684, 936, 160, 1640, 504, 1806, 220, 120, 1012, 2162, 48, 42, 40, 1632, 312, 2756, 108, 2200, 336, 2052, 1624, 3422, 240, 3660, 1860, 252, 32, 3120, 1320

Offset: 1

Antti Karttunen, Sep 28 2019

Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 161.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Chantal David and Francesco Pappalardi, Average Frobenius distributions of elliptic curves, International Mathematics Research Notices, Vol. 1999, No. 4 (1999), pp. 165-183, alternative link.

Cf. A082473 (gives the terms in ascending order, with duplicates removed).
Cf. A000010, A007913, A053143, A248003, A327170, A327172.
Cf. also A002618, A062355.

[EulerPhi(n)*Squarefree(n): n in [1..100]]; // G. C. Greubel, Jul 13 2024

Array[EulerPhi[#] (Sqrt@ # /. (c_: 1) a_^(b_: 0) :> (c a^b)^2) &, 66] (* Michael De Vlieger, Sep 29 2019, after Bill Gosper at A007913 *)

PARI
```
A327171(n) = eulerphi(n)*core(n);
```

A327171(n) = { my(f=factor(n)); prod (i=1, #f~, (f[i, 1]-1)*(f[i, 1]^(-1 + f[i, 2] + (f[i, 2]%2)))); };

from sympy.ntheory.factor_ import totient, core
def A327171(n):
    return totient(n)*core(n) # Chai Wah Wu, Sep 29 2019

[euler_phi(n)*squarefree_part(n) for n in range(1,101)] # G. C. Greubel, Jul 13 2024

a(n) = A000010(n) * A007913(n).
Multiplicative with a(p^k) = (p-1) * p^((k-1)+(k mod 2)).
Sum_{n>=1} 1/a(n) = (Pi^2/6) * Product_{p prime} (1 + (p+1)/(p^2*(p-1))) = 3.96555686901754604330... - Amiram Eldar, Oct 16 2020
Sum_{k=1..n} a(k) ~ c * n^3, where c = (Pi^2/45) * Product_{p prime} (1 - 1/p^2 + 1/p^3 - 1/p^4) = 0.1500809164... . - Amiram Eldar, Dec 05 2022
a(n) = A000010(A053143(n)). - Amiram Eldar, Sep 15 2023

A327173 Inverse permutation to A194507.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 9, 7, 11, 8, 14, 10, 17, 12, 15, 16, 23, 13, 26, 18, 22, 20, 31, 19, 29, 24, 28, 25, 38, 21, 41, 32, 35, 33, 39, 27, 50, 36, 42, 34, 54, 30, 57, 40, 47, 46, 65, 37, 63, 45, 53, 48, 72, 44, 67, 51, 62, 52, 79, 43, 82, 58, 68, 61, 76, 49, 92, 66, 74, 55, 96, 56, 99, 70, 73, 71, 94, 59, 108, 69, 90, 78

Offset: 1

Antti Karttunen, Sep 28 2019

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
Index entries for sequences that are permutations of the natural numbers

Cf. A000010, A002618, A082473, A194507 (inverse permutation).

A082473(a(n)) = A002618(n).

A332049 a(n) = (1/2) * Sum_{d|n, d > 1} d * phi(d).

Original entry on oeis.org

0, 1, 3, 5, 10, 10, 21, 21, 30, 31, 55, 38, 78, 64, 73, 85, 136, 91, 171, 115, 150, 166, 253, 150, 260, 235, 273, 236, 406, 220, 465, 341, 388, 409, 451, 335, 666, 514, 549, 451, 820, 451, 903, 610, 640, 760, 1081, 598, 1050, 781, 955, 863, 1378, 820, 1165

Offset: 1

Ilya Gutkovskiy, Feb 06 2020

Sum of numerators of the reduced fractions 1/n, ..., (n-1)/n. Note that if n is a prime p this is p*(p-1)/2 as all fractions are already reduced. For 1/n, ..., n/n, see A057661.

			For n = 5, fractions are 1/5, 2/5, 3/5, 4/5, sum of numerators is 10.
For n = 8, fractions are 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8, sum of numerators is 21.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000010, A002618, A006579, A023896, A057660, A057661.

toNums a = fmap (numerator . (% a))
toNumList a = toNums a [1..(a-1)]
sumList = sum . toNumList <$> [2..200]

[0] cat [(1/2)*&+[ d*EulerPhi(d):d in Set(Divisors(n)) diff {1}]:n in [2..60]]; // Marius A. Burtea, Feb 07 2020

N:= 100: # for a(1)..a(N)
V:= Vector(N):
for d from 2 to N do
  v:= d*numtheory:-phi(d)/2;
  R:= [seq(i,i=d..N,d)];
  V[R]:= V[R] +~ v
od:
convert(V,list); # Robert Israel, Feb 07 2020

Table[(1/2) Sum[If[d > 1, d EulerPhi[d], 0], {d, Divisors[n]}], {n, 1, 55}]
nmax = 55; CoefficientList[Series[(1/2) Sum[EulerPhi[k^2] x^k/(1 - x^k), {k, 2, nmax}], {x, 0, nmax}], x] // Rest
Table[Sum[k/GCD[n, k], {k, 1, n - 1}], {n, 1, 55}]
Table[(DivisorSigma[2, n^2] - DivisorSigma[1, n^2])/(2 DivisorSigma[1, n^2]), {n, 1, 55}]

a(n) = sumdiv(n, d, if (d>1, d*eulerphi(d)))/2; \\ Michel Marcus, Feb 07 2020

G.f.: (1/2) * Sum_{k>=2} phi(k^2) * x^k / (1 - x^k).
a(n) = Sum_{k=1..n-1} k / gcd(n,k).
a(n) = (sigma_2(n^2) - sigma_1(n^2)) / (2 * sigma_1(n^2)).
a(n) = Sum_{d|n, d > 1} A023896(d).
a(n) = A057661(n) - 1 = (A057660(n) - 1) / 2.

A046062 Primes of the form n*phi(n)+1 where phi(n) is the Euler function.

Original entry on oeis.org

2, 3, 7, 13, 43, 41, 157, 109, 193, 313, 487, 337, 241, 661, 433, 937, 641, 881, 1013, 769, 1249, 2053, 1861, 2269, 3121, 1321, 4423, 3037, 3001, 4621, 1873, 6163, 2017, 5441, 3613, 2161, 6553, 4049, 5581

Offset: 1

Felice Russo

Listed in order of increasing n.

			7 because 3*phi(3)+1 = 7 is prime.

T. D. Noe, Table of n, a(n) for n=1..1000

Cf. A002618, A046078.

Select[Array[# EulerPhi[#]+1&,500],PrimeQ] (* Harvey P. Dale, Apr 21 2012 *)

A047919 Triangular array read by rows: a(n,k) = Sum_{d|k} mu(d)*U(n,k/d)/n if k|n else 0, where U(n,k) = A047916(n,k) (1<=k<=n).

Original entry on oeis.org

1, 1, 0, 2, 0, 0, 2, 0, 0, 4, 4, 0, 0, 0, 20, 2, 4, 6, 0, 0, 108, 6, 0, 0, 0, 0, 0, 714, 4, 4, 0, 40, 0, 0, 0, 4992, 6, 0, 30, 0, 0, 0, 0, 0, 40284, 4, 16, 0, 0, 380, 0, 0, 0, 0, 362480, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3628790, 4, 8, 60, 312, 0, 3768, 0, 0, 0, 0

Offset: 1

N. J. A. Sloane

J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
C. L. Mallows and N. J. A. Sloane, Notes on A002618, A002619, etc.
N. J. A. Sloane, Notes on A002618, A002619, etc.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61. [Annotated scanned copy. Note that the scanned pages are out of order]

Divide n-th row of array A047918 by n.

Cf. A002024.

a047919 n k = a047919_tabl !! (n-1) !! (k-1)
a047919_row n = a047919_tabl !! (n-1)
a047919_tabl = zipWith (zipWith div) a047918_tabl a002024_tabl
-- Reinhard Zumkeller, Mar 19 2014

U[n_, k_] := If[Divisible[n, k], EulerPhi[n/k]*(n/k)^k*k!, 0]; a[n_, k_] := Sum[If[Divisible[n, k], MoebiusMu[d]*U[n, k/d], 0], {d, Divisors[k]}]; row[n_] := Table[a[n, k], {k, 1, n}]/n; Table[row[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Nov 21 2012, after A047918 *)

Offset corrected by Reinhard Zumkeller, Mar 19 2014

A053198 Totients of consecutive pure powers of primes.

Original entry on oeis.org

2, 4, 6, 8, 20, 18, 16, 42, 32, 54, 110, 100, 64, 156, 162, 128, 272, 294, 342, 256, 506, 500, 486, 812, 930, 512, 1210, 1332, 1640, 1806, 1024, 1458, 2028, 2162, 2058, 2756, 2500, 3422, 3660, 2048, 4422, 4624, 4970, 5256, 6162, 4374, 6498, 6806, 7832, 4096

Offset: 1

Labos Elemer, Mar 03 2000

nonn

Totients of prime powers are prime powers only for powers of 2.

			The 10th pure power of prime (but not a prime) is 81, so a(10) = EulerPhi(81) = 54.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A051953, A001248, A002618, A036689, A053650, A053191, A053192, A086242.

EulerPhi[Select[Range[2^13], CompositeQ[#] && PrimePowerQ[#] &]] (* Amiram Eldar, Dec 21 2020 *)

a(n) = A000010(A025475(n+1)).
Numbers of the form phi(p^k) = (p-1)*p^(k-1), where p is prime and k > 1.
Sum_{n>=1} 1/a(n) = Sum_{p prime} 1/(p-1)^2 = A086242 = 1.3750649947... - Amiram Eldar, Dec 21 2020

A053211 Cototients of consecutive pure powers of primes.

Original entry on oeis.org

2, 4, 3, 8, 5, 9, 16, 7, 32, 27, 11, 25, 64, 13, 81, 128, 17, 49, 19, 256, 23, 125, 243, 29, 31, 512, 121, 37, 41, 43, 1024, 729, 169, 47, 343, 53, 625, 59, 61, 2048, 67, 289, 71, 73, 79, 2187, 361, 83, 89, 4096, 97, 101, 103, 107, 109, 529, 113, 1331, 3125, 127

Offset: 1

Labos Elemer, Mar 03 2000

nonn

Cototients of prime powers do not remain always prime powers, but are primes if their exponent is 2.

			The 10th pure power of prime (but not a prime) is 81, so a(10) = 81 - EulerPhi(81) = 81 - 54 = 27. For n=p^2, a(n)=p.

Michael De Vlieger, Table of n, a(n) for n = 1..16384
Michael De Vlieger, Log log scatterplot of a(n) n = 1..2^20, showing even a(n) in blue, 3 | a(n) in green, and prime a(n) in red, else black.

Cf. A000010, A051953, A001248, A002618, A036689, A053650, A053191, A053192, A246547.

Map[# - EulerPhi@ # &, Select[Range[16200], And[! PrimeQ@ #, PrimePowerQ@ #] &]] (* Michael De Vlieger, Jun 11 2018 *)
With[{nn = 2^14}, Map[Times @@ Map[#1^(#2 - 1) & @@ FactorInteger[#][[1]]] &, Select[Union@ Flatten@ Table[a^2*b^3, {b, nn^(1/3)}, {a, Sqrt[nn/b^3]}], PrimePowerQ] ] ] (* Michael De Vlieger, Mar 11 2023 *)

a(n) = A051953(A025475(n+1)) = cototient(p^k) = p^(k-1).

A057789 a(n) = Sum_{k = 1..n, gcd(k,n)=1} k*(n-k).

Original entry on oeis.org

0, 1, 4, 6, 20, 10, 56, 44, 84, 60, 220, 92, 364, 182, 280, 344, 816, 318, 1140, 520, 840, 770, 2024, 760, 2100, 1300, 2196, 1540, 4060, 1240, 4960, 2736, 3520, 2992, 4760, 2580, 8436, 4218, 5928, 4240, 11480, 3612, 13244, 6380, 8040, 7590, 17296, 6128

Offset: 1

Leroy Quet, Nov 04 2000

Equal to convolution sum over positive integers, k, where k<=n and gcd(k,n)=1, except in first term, where the convolution sum is 1 instead of 0.

			Since 1, 3, 5 and 7 are relatively prime to 8 and are <= 8, a(8) = 1*(8-1) +3*(8-3) +5*(8-5) +7*(8-7) = 44.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000292, A023896, A053818, A053819, A002618, A053191, A023900.

f:= proc(n) local i;
  2*add(`if`(igcd(i,n)=1, i*(n-i),0),i=1..n/2)
end proc:
f(2):= 1:
map(f, [$1..100]); # Robert Israel, Sep 29 2019

a[n_] := 2 Sum[Boole[CoprimeQ[k, n]] k (n - k), {k, 1, n/2}];
a[2] = 1;
Array[a, 100] (* Jean-François Alcover, Aug 16 2020, after Maple *)

a(n) = sum(k=1, n, if (gcd(n,k)==1, k*(n-k))); \\ Michel Marcus, Sep 29 2019

From Robert Israel, Sep 29 2019: (Start)
If n is prime, a(n) = A000292(n-1).
If n/2 is an odd prime, a(n) =  A000292(n-2)/2.
If n/3 is a prime other than 3, a(n) = A000292(n-3)*2*n/(3*(n-2)). (End)
From Ridouane Oudra, Mar 21 2024: (Start)
a(n) = n*A023896(n) - A053818(n) ;
a(n) = (2/3)*(n*A023896(n) - A053819(n)/n) ;
a(n) = (n/6)*(A002618(n) - A023900(n)) ;
a(n) = (1/6)*(A053191(n) - n*A023900(n)). (End)
Sum_{k=1..n} a(k) ~ n^4 / (4*Pi^2). - Amiram Eldar, Apr 11 2024

A064400 Number of ordered pairs a,b of elements in the dihedral group D_2n such that the subgroup generated by the pair a,b is the entire group D_2n.

Original entry on oeis.org

3, 6, 18, 24, 60, 36, 126, 96, 162, 120, 330, 144, 468, 252, 360, 384, 816, 324, 1026, 480, 756, 660, 1518, 576, 1500, 936, 1458, 1008, 2436, 720, 2790, 1536, 1980, 1632, 2520, 1296, 3996, 2052, 2808, 1920, 4920, 1512, 5418, 2640, 3240, 3036, 6486, 2304, 6174, 3000, 4896, 3744, 8268

Offset: 1

Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Sep 28 2001

nonn

Kenneth G. Hawes, Table of n, a(n) for n = 1..10000

Cf. A002618, A064279.

Table[a=GroupElements[DihedralGroup[n]];Count[Flatten[Table[Table[GroupOrder[PermutationGroup[{a[[i]],a[[j]]}]],{i,1,2*n}],{j,1,2*n}]],2*n],{n,1,20}]  (* Geoffrey Critzer, Apr 14 2013 *)

a(n) = 3 * n * eulerphi(n); /* Joerg Arndt, Apr 14 2013 */

a(n) = 3 * A002618(n) = 3 * n * phi(n).

More terms from Geoffrey Critzer, Apr 14 2013

cp's OEIS Frontend

A327170 Number of divisors d of n such that A327171(d) (= phi(d)*core(d)) is equal to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A327171 a(n) = phi(n) * core(n), where phi is Euler totient function, and core gives the squarefree part of n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Python

SageMath

Formula

A327173 Inverse permutation to A194507.

Views

Author

Keywords

Links

Crossrefs

Formula

A332049 a(n) = (1/2) * Sum_{d|n, d > 1} d * phi(d).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

A046062 Primes of the form n*phi(n)+1 where phi(n) is the Euler function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A047919 Triangular array read by rows: a(n,k) = Sum_{d|k} mu(d)*U(n,k/d)/n if k|n else 0, where U(n,k) = A047916(n,k) (1<=k<=n).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Mathematica

Extensions

A053198 Totients of consecutive pure powers of primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs