A061468 -id:A061468 - cp's OEIS frontend

A062355 a(n) = d(n) * phi(n), where d(n) is the number of divisors function.

1, 2, 4, 6, 8, 8, 12, 16, 18, 16, 20, 24, 24, 24, 32, 40, 32, 36, 36, 48, 48, 40, 44, 64, 60, 48, 72, 72, 56, 64, 60, 96, 80, 64, 96, 108, 72, 72, 96, 128, 80, 96, 84, 120, 144, 88, 92, 160, 126, 120, 128, 144, 104, 144, 160, 192, 144, 112, 116, 192, 120, 120, 216, 224

Offset: 1

Jason Earls, Jul 06 2001

a(n) = sum of gcd(k-1,n) for 1 <= k <= n and gcd(k,n)=1 (Menon's identity).
For n = 2^(4*k^2 - 1), k >= 1, the terms of the sequence are square and for n = 2^((3*k + 2)^3 - 1), k >= 1, the terms of the sequence are cubes. - Marius A. Burtea, Nov 14 2019
Sum_{k>=1} 1/a(k) diverges. - Vaclav Kotesovec, Sep 20 2020

D. M. Burton, Elementary Number Theory, Allyn and Bacon Inc., Boston MA, 1976, Prob. 7.2 12, p. 141.
P. K. Menon, On the sum gcd(a-1,n) [(a,n)=1], J. Indian Math. Soc. (N.S.), 29 (1965), 155-163.
József Sándor, On Dedekind's arithmetical function, Seminarul de teoria structurilor (in Romanian), No. 51, Univ. Timișoara, 1988, pp. 1-15. See p. 11.
József Sándor, Some diophantine equations for particular arithmetic functions (in Romanian), Seminarul de teoria structurilor, No. 53, Univ. Timișoara, 1989, pp. 1-10. See p. 8.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (terms 1..1000 from Harry J. Smith)
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.
Vaclav Kotesovec, Graph - the asymptotic ratio (250000000 terms)
R. J. Mathar, Survey of Dirichlet series of multiplicative arithmetic functions, arXiv:1106.4038 [math.NT], 2011-2012, Section 3.15.
R. Sivaramakrishnan, Problem E 1962, Elementary Problems, The American Mathematical Monthly, Vol. 74, No. 2 (1967), p. 198; Solution, ibid., Vol. 75, No. 5 (1968), p. 550.
Marius Tarnauceanu, A generalization of the Menon's identity, arXiv:1109.2198 [math.GR], 2011-2012.
Laszlo Toth, Menon's identity and arithmetical sums representing functions of several variables, Rend. Sem. Mat. Univ. Politec. Torino, 69 (2011), 97-110.
Wikipedia, Arithmetic function (Menon's identity).

Cf. A003557, A173557, A061468, A062816, A079535, A062949 (inverse Mobius transform), A304408, A318519, A327169 (number of times n occurs in this sequence).

Cf. A062354, A064840.

[NumberOfDivisors(n)*EulerPhi(n):n in [1..65]]; // Marius A. Burtea, Nov 14 2019

seq(tau(n)*phi(n), n=1..64); # Zerinvary Lajos, Jan 22 2007

Table[EulerPhi[n] DivisorSigma[0, n], {n, 80}] (* Carl Najafi, Aug 16 2011 *)
f[p_, e_] := (e+1)*(p-1)*p^(e-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 21 2020 *)

a(n)=numdiv(n)*eulerphi(n); vector(150,n,a(n))

{ for (n=1, 1000, write("b062355.txt", n, " ", numdiv(n)*eulerphi(n)) ) } \\ Harry J. Smith, Aug 05 2009

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

Dirichlet convolution of A047994 and A000010. - R. J. Mathar, Apr 15 2011
a(n) = A000005(n)*A000010(n). Multiplicative with a(p^e) = (e+1)*(p-1)*p^(e-1). - R. J. Mathar, Jun 23 2018
a(n) = A173557(n) * A318519(n) = A003557(n) * A304408(n). - Antti Karttunen, Sep 16 2018 & Sep 20 2019
From Vaclav Kotesovec, Jun 15 2020: (Start)
Let f(s) = Product_{primes p} (1 - 2*p^(-s) + p^(1-2*s)).
Dirichlet g.f.: zeta(s-1)^2 * f(s).
Sum_{k=1..n} a(k) ~ n^2 * (f(2)*(log(n)/2 + gamma - 1/4) + f'(2)/2), where f(2) = A065464 = Product_{primes p} (1 - 2/p^2 + 1/p^3) = 0.42824950567709444...,
f'(2) = 2 * A065464 * A335707 = f(2) * Sum_{primes p} 2*log(p) / (p^2 + p - 1) = 0.35866545223424232469545420783620795... and gamma is the Euler-Mascheroni constant A001620. (End)
From Amiram Eldar, Mar 02 2021: (Start)
a(n) >= n (Sivaramakrishnan, 1967).
a(n) >= sigma(n), for odd n (Sándor, 1988).
a(n) >= phi(n) + n - 1 (Sándor, 1989) (End)
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} uphi(gcd(n,k)), where uphi(n) = A047994(n).
a(n) = Sum_{k=1..n} uphi(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)

A286160 Compound filter: a(n) = T(A000010(n), A046523(n)), where T(n,k) is sequence A000027 used as a pairing function.

Original entry on oeis.org

1, 2, 5, 12, 14, 23, 27, 59, 42, 40, 65, 109, 90, 61, 86, 261, 152, 142, 189, 179, 148, 115, 275, 473, 273, 148, 318, 265, 434, 674, 495, 1097, 320, 226, 430, 1093, 702, 271, 430, 757, 860, 832, 945, 485, 619, 373, 1127, 1969, 1032, 485, 698, 619, 1430, 838, 1030, 1105, 856, 556, 1769, 2791, 1890, 625, 1117, 4497, 1426, 1196, 2277, 935, 1220

Offset: 1

Antti Karttunen, May 04 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
MathWorld, Pairing Function

Cf. A000010, A000027, A046523, A286161, A286162, A286163, A286164.

Cf. for example A061468 (one of the sequences this matches with).

A000010(n) = eulerphi(n);
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ This function from Charles R Greathouse IV, Aug 17 2011
A286160(n) = (2 + ((A000010(n)+A046523(n))^2) - A000010(n) - 3*A046523(n))/2;
for(n=1, 10000, write("b286160.txt", n, " ", A286160(n)));

from sympy import factorint, totient
def T(n, m): return ((n + m)**2 - n - 3*m + 2)/2
def P(n):
    f = factorint(n)
    return sorted([f[i] for i in f])
def a046523(n):
    x=1
    while True:
        if P(n) == P(x): return x
        else: x+=1
def a(n): return T(totient(n), a046523(n)) # Indranil Ghosh, May 06 2017

(define (A286160 n) (* (/ 1 2) (+ (expt (+ (A000010 n) (A046523 n)) 2) (- (A000010 n)) (- (* 3 (A046523 n))) 2)))

a(n) = (1/2)*(2 + ((A000010(n)+A046523(n))^2) - A000010(n) - 3*A046523(n)).

A318893 Filter sequence combining the prime signature of n (A046523) with Euler totient function (A000010).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Sep 16 2018

nonn

Restricted growth sequence transform of A286160.

For all i, j: a(i) = a(j) => A062355(i) = A062355(j).

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

Cf. A000010, A046523, A286160, A318839, A318892.

Cf. also A061468, A062355.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ From A046523
A318893aux(n) = [eulerphi(n), A046523(n)];
v318893 = rgs_transform(vector(up_to,n,A318893aux(n)));
A318893(n) = v318893[n];

A357916 Primes p that can be written as phi(k) + d(k) for some k, where phi(k) = A000010(k) is Euler's totient function and d(k) = A000005(k) is the number of divisors of k.

Original entry on oeis.org

2, 3, 5, 13, 23, 59, 113, 137, 229, 457, 509, 523, 661, 1021, 2063, 3541, 3923, 4973, 5449, 5521, 9949, 10103, 10273, 12659, 14107, 15601, 16249, 17033, 22063, 25321, 29759, 32507, 34843, 36293, 37273, 52501, 54059, 62753, 68449, 68909, 89329, 99409, 103963, 111347, 125509, 139297, 146309, 157231

Offset: 1

J. M. Bergot and Robert Israel, Oct 19 2022

nonn

Does any prime have more than one representation as phi(k) + d(k)?

			a(4) = 13 is a term because 13 is prime and for k = 16, phi(k) + d(k) = 8 + 5 = 13.

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

Cf. A000005, A000010, A061468, A357917.

N:= 10^6: # to allow k <= N
pmax:=  evalf(N/(exp(gamma)*log(log(N))+3/log(log(N)))): # lower bound for phi(k), k<=N
P:= {3}:
for k from 1 to sqrt(N) do
  n:= k^2;
  v:= numtheory:-phi(n)+numtheory:-tau(n);
  if v <= pmax and isprime(v) then
     P:= P union {v};
  fi
od:
sort(convert(P,list));

Select[Table[EulerPhi[n]+DivisorSigma[0,n],{n,400000}],PrimeQ]//Sort (* Harvey P. Dale, Feb 29 2024 *)

A259496 Numbers n such that phi(n) + d(n) = phi(n+1) + d(n+1), where phi(n) is the Euler totient function of n and d(n) the number of divisors of n.

Original entry on oeis.org

5, 7, 104, 105, 1754, 3255, 16215, 22935, 67431, 93074, 983775, 1025504, 2200694, 2619705, 3365438, 4163355, 4447064, 4695704, 6372794, 7838265, 9718904, 11903775, 23992215, 26879684, 29357475, 37239735, 40588485, 41207144, 48615735, 56424555, 76466985, 81591194, 83864055

Offset: 1

Paolo P. Lava, Jun 29 2015

nonn

So far, less than 10^9, except for 7, 67431 & 3365438, all terms have been congruent to 5 or 4 (mod 10). - Robert G. Wilson v, Jul 06 2015

			phi(5) + d(5) = 4 + 2 = 6 and phi(6) + d(6) = 2 + 4 = 6.
phi(7) + d(7) = 6 + 2 = 8 and phi(8) + d(8) = 4 + 4 = 8.

Giovanni Resta, Table of n, a(n) for n = 1..600 (first 65 terms from Robert G. Wilson v)

Cf. A000005, A000010, A061468, A054004, A145749, A259495.

[n: n in [1..6*10^6] | EulerPhi(n) + NumberOfDivisors(n) eq EulerPhi(n+1) + NumberOfDivisors(n+1)]; // Vincenzo Librandi, Jun 30 2015

with(numtheory): P:=proc(q) local n; for n from 1 to q do
if phi(n)+tau(n)=phi(n+1)+tau(n+1) then print(n); fi;
od; end: P(10^9);

a = k = 2; lst = {}; While[k < 100000001, b = EulerPhi[k] + DivisorSigma[0, k]; If[a == b, AppendTo[lst, k - 1]]; k++; a = b]; lst

a(23)-a(33) from Robert G. Wilson v, Jul 05 2015

A357917 a(n) is the least k such that phi(k) + d(k) = A357916(n), where phi(k) = A000010(k) is Euler's totient function, and d(k) = A000005(k) is the number of divisors of k.

Original entry on oeis.org

1, 2, 4, 16, 25, 81, 121, 256, 484, 1296, 529, 1024, 1600, 2116, 2401, 7744, 11664, 5041, 7225, 11236, 20164, 10201, 25600, 12769, 30976, 46656, 21025, 17161, 44944, 51076, 29929, 84100, 73984, 36481, 75076, 107584, 54289, 63001, 87025, 69169, 101761, 126025, 215296, 256036, 252004, 295936

Offset: 1

J. M. Bergot and Robert Israel, Oct 19 2022

nonn

Numbers k such that A061468(k) = phi(k) + d(k) is prime, and no smaller number gives the same value of A061468, sorted in order of the prime values.
All terms except 2 are squares, because if k > 2, phi(k) is even, and if d(k) is odd, k must be a square.
All numbers in this sequence are elements of A225983. For an example, this excludes all numbers of the form (6*m)^2 but only if m is not divisible by 6. - Thomas Scheuerle, Oct 20 2022

			a(4) = 16 because phi(16) + d(16) = 8 + 5 = 13 = A357916(4), and no smaller number than 16 works.

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

Cf. A000005, A000010, A061468, A225983, A357916.

N:= 10^6:
pmax:=  evalf(N/(exp(gamma)*log(log(N))+3/log(log(N))));
V:= 'V': P:= {3}: V[3]:= 2:
for k from 1 to sqrt(N) do
  n:= k^2;
  v:= numtheory:-phi(n)+numtheory:-tau(n);
  if v <= pmax and isprime(v) and not member(v,P) then
    P:= P union {v}; V[v]:= n;
  fi
od:
P:= sort(convert(P,list)):
seq(V[p], p=P);

A061468(a(n)) = A000010(a(n)) + A000005(a(n)) = A357916(n).

A324059 Numbers n such that sigma(n)/(phi(n) + tau(n)) is a record.

Original entry on oeis.org

1, 2, 4, 6, 10, 12, 18, 24, 30, 42, 60, 84, 90, 120, 180, 210, 360, 420, 840, 1260, 1680, 2520, 4620, 7560, 9240, 13860, 18480, 27720, 55440, 110880, 120120, 180180, 240240, 360360, 720720, 1441440, 2162160, 3603600, 4084080, 4324320, 6126120, 12252240, 24504480

Offset: 1

Robert G. Wilson v, Feb 13 2019

nonn

sigma(a(69))/(phi(a(69)) + tau(a(69))) = 857304000/23950081 ~= 35.7955.
Number of terms =< 10^k, k=0,1,2,3: 1, 5, 13, 19, 25, 29, 35, 41, 46, 50, 56, 63, 69, ..., .
All terms so far except 10, 18, 42, 84, 90 are in A025487. - David A. Corneth, Feb 14 2019

			a(7) = 18 since it is the first number greater than a(6) such that sigma(18)/(phi(18) + tau(18)) = 13/4 > 14/5 =  sigma(12)/(phi(12) + tau(12)).

Robert G. Wilson v, Table of n, a(n) for n = 1..70

Cf. A000010, A000005, A000203, A061468, A324060, A025487.

Res:= NULL: mx:= 0: count:= 0:
for n from 1 while count < 60 do
  v:= numtheory:-sigma(n)/(numtheory:-phi(n)+numtheory:-tau(n));
  if v > mx then
    mx:= v;
    count:= count+1;
    Res:= Res, n;
  fi
od:
Res; # Robert Israel, Feb 13 2019

k = 1; mx = 0; lst = {}; While[k < 25000000, If[ DivisorSigma[1, k] > mx (EulerPhi[k] + DivisorSigma[0, k]), mx = DivisorSigma[1, k]/(EulerPhi[k] + DivisorSigma[0, k]); AppendTo[lst, k]]; k ++]; lst
DeleteDuplicates[Table[{n,DivisorSigma[1,n]/(EulerPhi[n]+DivisorSigma[0,n])},{n,2451*10^4}],GreaterEqual[#1[[2]],#2[[2]]]&][[All,1]] (* Harvey P. Dale, Jun 08 2022 *)

lista(nn) = {my(m=0, newm); for (n=1, nn, newm = sigma(n)/(eulerphi(n) + numdiv(n)); if (newm > m, print1(n, ", "); m = newm););} \\ Michel Marcus, Feb 13 2019

A357898 a(n) is the least k such that phi(k) + d(k) = 2^n, or -1 if there is no such k, where phi(k) = A000010(k) is Euler's totient function and d(k) = A000005(k) is the number of divisors of k.

Original entry on oeis.org

1, 3, 7, 21, 31, 77, 127, 301, 783, 1133, 3399, 4781, 8191, 16637, 37367, 101601, 131071, 305837, 524287, 1073581, 3220743, 4201133, 8544103, 18404669, 34012327, 67139117, 135255431, 300528877, 824583699, 1073862029, 2147483647, 4295564381, 8603449703, 25807607829

Offset: 1

J. M. Bergot and Robert Israel, Oct 19 2022

nonn

All primes in this sequence are primes of the form 2^n - 1. This is true because phi(p) = 2^n - 2 if p = 2^n - 1 is a Mersenne prime. - Thomas Scheuerle, Oct 19 2022
274878976349 = a(38) < a(37) = 274881227398. - Martin Ehrenstein, Oct 24 2022
d(k) <= A070319(2^n). - David A. Corneth, Oct 25 2022

			a(3) = 7 because phi(7)+d(7) = 6+2 = 2^3, and 7 is the least number that works.

Max Alekseyev, Table of n, a(n) for n = 1..160 (a(35)..a(38) from Martin Ehrenstein; a(39)..a(49) from David A. Corneth)

Cf. A000005, A000010, A061468, A070319, A073757.

V:= Array(0..23): count:= 0:
for n from 1 while count < 23 do
  s:= phi(n)+tau(n);
  t:= padic:-ordp(s,2);
  if V[t] = 0 and s = 2^t then
     V[t]:= n; count:= count+1;
  fi
od:
convert(V,list)[2..-1];

a(27)-a(33) from Giorgos Kalogeropoulos, Oct 22 2022

a(34) from Martin Ehrenstein, Oct 24 2022

A357918 Odd numbers that can be written as phi(k) + d(k) for more than one k, where phi(k) = A000010(k) is Euler's totient function and d(k) = A000005(k) is the number of divisors of k.

Original entry on oeis.org

2061, 4131, 36981, 78765, 14054589, 889978059, 110543990589

Offset: 1

J. M. Bergot and Robert Israel, Oct 19 2022

For phi(k) + d(k) to be odd, k must be a square.

			a(1) = 2061 = phi(57^2) + d(57^2) = phi(64^2) + d(64^2) = phi(84^2) + d(84^2).
a(2) = 4131 = phi(98^2) + d(98^2) = phi(114^2) + d(114^2).
a(3) = 36981 = phi(237^2) + d(237^2) = phi(342^2) + d(342^2).
a(4) = 78765 = phi(486^2) + d(486^2) = phi(492^2) + d(492^2).
a(5) = 14054589 = phi(4593^2) + d(4593^2) = phi(7320^2) + d(7320^2).
a(6) = 889978059 = phi(29833^2) + d(29833^2) = phi(45668^2) + d(45668^2).
a(7) = 110543990589 = phi(337993^2) + d(337993^2) = phi(423891^2) + d(423891^2).

Cf. A000005, A000010, A061468, A357916

N:= 10^12: vmax:= evalf(N/(exp(gamma)*log(log(N))+3/log(log(N)))):
Q:= [seq(numtheory:-phi(k^2)+numtheory:-tau(k^2),k=1..sqrt(N))]:
QN := select(`<`,Q,vmax):
QS:= sort(QN):
K:= select(t -> QS[t+1]=QS[t], [$1..nops(QS)-1]):
convert(QS[K],set);

cp's OEIS Frontend

A062355 a(n) = d(n) * phi(n), where d(n) is the number of divisors function.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Formula

A286160 Compound filter: a(n) = T(A000010(n), A046523(n)), where T(n,k) is sequence A000027 used as a pairing function.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Scheme

Formula

A318893 Filter sequence combining the prime signature of n (A046523) with Euler totient function (A000010).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A357916 Primes p that can be written as phi(k) + d(k) for some k, where phi(k) = A000010(k) is Euler's totient function and d(k) = A000005(k) is the number of divisors of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A259496 Numbers n such that phi(n) + d(n) = phi(n+1) + d(n+1), where phi(n) is the Euler totient function of n and d(n) the number of divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Extensions

A357917 a(n) is the least k such that phi(k) + d(k) = A357916(n), where phi(k) = A000010(k) is Euler's totient function, and d(k) = A000005(k) is the number of divisors of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A324059 Numbers n such that sigma(n)/(phi(n) + tau(n)) is a record.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs