A176003 -id:A176003 - cp's OEIS frontend

A062380 a(n) = Sum_{i|n,j|n} phi(i)*phi(j)/phi(gcd(i,j)), where phi is Euler totient function.

1, 4, 7, 14, 13, 28, 19, 42, 37, 52, 31, 98, 37, 76, 91, 114, 49, 148, 55, 182, 133, 124, 67, 294, 113, 148, 163, 266, 85, 364, 91, 290, 217, 196, 247, 518, 109, 220, 259, 546, 121, 532, 127, 434, 481, 268, 139, 798, 229, 452, 343, 518, 157, 652, 403, 798, 385

Offset: 1

Vladeta Jovovic, Jul 07 2001

A176003 is a subsequence. - Peter Luschny, Sep 12 2012

			Let p be a prime then a(p) = phi(1)*tau(1)+phi(p)*tau(p^2) = 1+(p-1)*3 = 3*p-2. - _Peter Luschny_, Sep 12 2012

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000005, A000010, A060648, A062949.

with(numtheory):
a:= n->  add(phi(d)*tau(d^2), d=divisors(n)):
seq(a(n), n=1..60);  # Alois P. Heinz, Sep 12 2012

a[n_] := DivisorSum[n, EulerPhi[#] DivisorSigma[0, #^2]&]; Array[a, 60] (* Jean-François Alcover, Dec 05 2015 *)
f[p_, e_] := ((2*e+1)*p^(e+1) - (2*e+3)*p^e + 2)/(p-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Apr 30 2023 *)

a(n)=sumdiv(n,i,eulerphi(i)*sumdiv(n,j,eulerphi(j)/eulerphi(gcd(i,j)))) \\ Charles R Greathouse IV, Sep 12 2012

def A062380(n) :
    d = divisors(n); cp = cartesian_product([d, d])
    return reduce(lambda x,y: x+y, map(euler_phi, map(lcm, cp)))
[A062380(n) for n in (1..57)]  # Peter Luschny, Sep 10 2012

a(n) = Sum_{d|n} phi(d)*tau(d^2).
Multiplicative with a(p^e) = 1 + Sum_{k=1..e} (2k+1)(p^k-p^{k-1}) = ((2e+1)p^(e+1) - (2e+3)p^e+2)/(p-1). - Mitch Harris, May 24 2005
a(n) = Sum_{c|n,d|n} phi(lcm(c,d)). - Peter Luschny, Sep 10 2012
a(n) = Sum_{k=1..n} tau( (n/gcd(k,n))^2 ). - Seiichi Manyama, May 19 2024

A213382 Numbers n such that n^n mod (n + 2) = n.

Original entry on oeis.org

1, 4, 7, 13, 16, 19, 31, 37, 49, 55, 61, 67, 85, 91, 109, 121, 127, 139, 157, 175, 181, 193, 196, 199, 211, 217, 235, 247, 265, 289, 301, 307, 313, 319, 325, 337, 379, 391, 397, 409, 415, 445, 451, 469, 487, 499, 517, 535, 541, 571, 577, 589, 595, 631, 667, 679

Offset: 1

Alex Ratushnyak, Jun 10 2012

nonn

Equivalently, numbers n such that (n^n+2)/(n+2) is an integer. Derek Orr, May 23 2014
It was conjectured that A176003 is a subsequence.
Terms that do not appear in A176003: 16, 61, 193, 196, 313, 397, 691, 729, 769 ...
The conjecture is correct: verify the cases 1 and 3, then it suffices to show that (3p-2)^(3p-2) = 3p-2 mod 3 and mod p. Mod 3 the congruence is 1^(3p-2) = 1, and mod p the congruence is (-2)^(3p-2) = -2 which is true by Fermat's little theorem. - Charles R Greathouse IV, Sep 12 2012
a(62) = 729 is the first number not congruent to 1 mod 3. - Derek Orr, May 23 2014

			A213381(n) = 7^7 mod 9 = 7, so 7 is in the sequence.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A213381 : a(n) = n^n mod (n+2).

Cf. A176003.

Select[Range[700],PowerMod[#,#,#+2]==#&] (* Harvey P. Dale, Oct 03 2015 *)

is(n)=Mod(n,n+2)^n==n \\ Charles R Greathouse IV, Sep 12 2012

for n in range(999):
    x = n**n % (n+2)
    if x==n:
        print(n, end=", ")

A213381 a(n) = n^n mod (n+2).

Original entry on oeis.org

1, 1, 0, 2, 4, 3, 0, 7, 6, 5, 4, 6, 8, 13, 0, 8, 16, 9, 4, 19, 12, 11, 16, 17, 14, 7, 4, 14, 16, 15, 0, 31, 18, 13, 16, 18, 20, 37, 24, 20, 16, 21, 4, 7, 24, 23, 16, 17, 6, 49, 4, 26, 34, 3, 8, 55, 30, 29, 4, 30, 32, 61, 0, 57, 16, 33, 4, 67, 46, 35, 16, 36, 38

Offset: 0

Alex Ratushnyak, Jun 10 2012

nonn

Conjectures:
1. Indices of zeros: 2^(x+2)-2, x >= 0.
2. a(n)=n if n is in A176003.
3. Every integer k >= 0 appears in a(n) at least once.
4. Every k >= 0 appears in a(n) infinitely many times.
From Robert Israel, May 05 2015: (Start)
Conjecture 1) is true: with m = n+2, a(n) = (-2)^(m-2) mod m = 0 iff m divides 2^(m-2), i.e., m = 2^k for some k with k <= m-2 (which is true for k >= 2).
Conjecture 2) is true: if n = 3*p-2 where p is prime, then n == 1 (mod 3) so n^n == n (mod 3), and n^(p-1) == 1 (mod p) so n^n == n (mod p), and therefore (if p <> 3) n^n == n (mod 3*p).  A separate computation verifies the case p=3.
If p is an odd prime, then a(p+2) = (p-1)/2. (End)

			a(5) = 5^5 mod 7 = 3125 mod 7 = 3.

Paolo P. Lava, Table of n, a(n) for n = 0..1000

Cf. A000312.

a[n_] := PowerMod[-2, n, n+2];
a /@ Range[0, 100] (* Jean-François Alcover, Jun 04 2020 *)
Table[PowerMod[n,n,n+2],{n,0,80}] (* Harvey P. Dale, Oct 23 2024 *)

a(n) = lift(Mod(n, n+2)^n); \\ Michel Marcus, Jun 04 2020

a(n) = (n^n) mod (n+2).

a(n) = (-2)^n mod (n+2). - Robert Israel, May 05 2015

cp's OEIS Frontend

A062380 a(n) = Sum_{i|n,j|n} phi(i)*phi(j)/phi(gcd(i,j)), where phi is Euler totient function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A213382 Numbers n such that n^n mod (n + 2) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

A213381 a(n) = n^n mod (n+2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula