A051953 -id:A051953 - cp's OEIS frontend

A053287 Euler totient function (A000010) of 2^n - 1.

1, 2, 6, 8, 30, 36, 126, 128, 432, 600, 1936, 1728, 8190, 10584, 27000, 32768, 131070, 139968, 524286, 480000, 1778112, 2640704, 8210080, 6635520, 32400000, 44717400, 113467392, 132765696, 533826432, 534600000, 2147483646, 2147483648, 6963536448, 11452896600

Offset: 1

Labos Elemer, Mar 03 2000

Number of elements of multiplicative order 2^n - 1 in GF(2^n).
n divides a(n) because 2^a(n) mod 2^n - 1 is 1, 2^n mod 2^n - 1 is 1, so n | a(n). A011260(n) = a(n)/n. - Jinyuan Wang, Oct 31 2018
The set {a(n)/(2^n-1)} is dense in [0, 1] (Luca, 2003). - Amiram Eldar, Mar 04 2021

Amiram Eldar, Table of n, a(n) for n = 1..1206 (terms 1..100 from T. D. Noe, terms 101..250 from Jianing Song, terms 251..400 from Michel Marcus)
Florian Luca, On the sum of divisors of the Mersenne numbers, Mathematica Slovaca, Vol. 53. No. 5 (2003), pp. 457-466.

Cf. A000010, A000225, A051953, A057764, A011260.

List([1..35],n->Phi(2^n-1)); # Muniru A Asiru, Oct 31 2018

[EulerPhi(2^n-1): n in [1..40]]; // Vincenzo Librandi, Jul 15 2015

a := n -> numtheory:-phi(2^n - 1): seq(a(n), n=1..32); # Zerinvary Lajos, Oct 05 2007

EulerPhi[2^Range[25] - 1] (* Giovanni Resta, Sep 06 2019 *)

a(n) = eulerphi(2^n-1) \\ Michael B. Porter, Oct 06 2009

a(n) = A000010(A000225(n)).
a(A000079(n-1)) = A058891(n).
a(n) = A000010(2^n-1) or also a(n) = A062401(2^(n-1)) = phi(sigma(2^(n-1))). - Labos Elemer, Jul 19 2004

A051709 a(n) = sigma(n) + phi(n) - 2n.

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 0, 3, 1, 2, 0, 8, 0, 2, 2, 7, 0, 9, 0, 10, 2, 2, 0, 20, 1, 2, 4, 12, 0, 20, 0, 15, 2, 2, 2, 31, 0, 2, 2, 26, 0, 24, 0, 16, 12, 2, 0, 44, 1, 13, 2, 18, 0, 30, 2, 32, 2, 2, 0, 64, 0, 2, 14, 31, 2, 32, 0, 22, 2, 28, 0, 75, 0, 2, 14, 24, 2, 36, 0

Offset: 1

Jud McCranie and Carlos Rivera

nonn

Sigma is the sum of divisors (A000203), and phi is the Euler totient function (A000010). - Michael B. Porter, Jul 05 2013
Because sigma and phi are multiplicative functions, it is easy to show that (1) if a(n)=0, then n is prime or 1 and (2) if a(n)=2, then n is the product of two distinct prime numbers. Note that a(n) is the n-th term of the Dirichlet series whose generating function is given below. Using the generating function, it is theoretically possible to compute a(n). Hence a(n)=0 could be used as a primality test and a(n)=2 could be used as a test for membership in P2 (A006881). - T. D. Noe, Aug 01 2002
It appears that a(n) - A002033(n) = zeta(s-1) * (zeta(s) - 2 + 1/zeta(s)) + 1/(zeta(s)-2). - Eric Desbiaux, Jul 04 2013
a(n) = 1 if and only if n = prime(k)^2 (n is in A001248). It seems that a(n) = k has only finitely many solutions for k >= 3. - Jianing Song, Jun 27 2021

			a(5) = sigma(5) + phi(5) - 2*5 = 6 + 4 - 10 = 0.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (First 1000 terms from T. D. Noe.)
Carlos Rivera, Puzzle 76. z(n)=sigma(n) + phi(n) - 2n, The Prime Puzzles and Problems Connection.

Cf. A000010, A000203, A001065, A001248, A005843, A006881, A051612, A051953, A065387, A072780, A228498 (= a(n^2)), A297159, A324048, A344994, A344995, A344996, A345048, A345054.
Cf. A278373 (range of this sequence), A056996 (numbers not present).
Cf. also A344753, A345001 (analogous sequences).

Table[DivisorSigma[1,n]+EulerPhi[n]-2n,{n,80}] (* Harvey P. Dale, Apr 08 2015 *)

a(n)=sigma(n)+eulerphi(n)-2*n \\ Charles R Greathouse IV, Jul 05 2013

A051709(n) = -sumdiv(n,d,(dAntti Karttunen, Mar 02 2018

Dirichlet g.f.: zeta(s-1) * (zeta(s) - 2 + 1/zeta(s)). - T. D. Noe, Aug 01 2002
From Antti Karttunen, Mar 02 2018: (Start)
a(n) = A001065(n) - A051953(n).  [Difference between the sum of proper divisors of n and their Moebius-transform.]
a(n) = -Sum_{d|n, dA008683(n/d)*A001065(d). (End)
Sum_{k=1..n} a(k) = (3/(Pi^2) + Pi^2/12 - 1) * n^2 + O(n*log(n)). - Amiram Eldar, Dec 03 2023

A121998 Table, n-th row gives numbers between 1 and n that have a common factor with n.

Original entry on oeis.org

2, 3, 2, 4, 5, 2, 3, 4, 6, 7, 2, 4, 6, 8, 3, 6, 9, 2, 4, 5, 6, 8, 10, 11, 2, 3, 4, 6, 8, 9, 10, 12, 13, 2, 4, 6, 7, 8, 10, 12, 14, 3, 5, 6, 9, 10, 12, 15, 2, 4, 6, 8, 10, 12, 14, 16, 17, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 19, 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20, 3, 6, 7, 9, 12, 14, 15

Offset: 2

Franklin T. Adams-Watters, Sep 11 2006

Row n contains numbers m <= n such that gcd(m,n) > 1, i.e., numbers m in the cototient of n. - Michael De Vlieger, Mar 13 2018

			2;
3;
2,4;
5;
2,3,4,6;
7;
...

Michael De Vlieger, Table of n, a(n) for n = 2..12949 (rows 2 <= n <= 256).

Cf. A051953 (row lengths), A038566, A081520, A133995 (nondivisors in the cototient of n).

Table[Select[Range@ n, ! CoprimeQ[#, n] &], {n, 20}] // Flatten (* Michael De Vlieger, Mar 13 2018 *)

A319340 Sum of Euler totient function and its Dirichlet inverse: a(n) = A000010(n) + A023900(n).

Original entry on oeis.org

2, 0, 0, 1, 0, 4, 0, 3, 4, 8, 0, 6, 0, 12, 16, 7, 0, 8, 0, 12, 24, 20, 0, 10, 16, 24, 16, 18, 0, 0, 0, 15, 40, 32, 48, 14, 0, 36, 48, 20, 0, 0, 0, 30, 32, 44, 0, 18, 36, 24, 64, 36, 0, 20, 80, 30, 72, 56, 0, 8, 0, 60, 48, 31, 96, 0, 0, 48, 88, 0, 0, 26, 0, 72, 48, 54, 120, 0, 0, 36, 52, 80, 0, 12, 128, 84, 112, 50, 0, 16

Offset: 1

Antti Karttunen, Sep 17 2018

nonn

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

Cf. A000010, A023900, A051953, A318833, A319341.

A023900(n) = factorback(apply(p -> 1-p, factor(n)[, 1]));
A319340(n) = (eulerphi(n)+A023900(n));

a(n) = A000010(n) + A023900(n).

a(n) = A318833(n) - A051953(n).

A050384 Nonprimes such that n and phi(n) are relatively prime.

Original entry on oeis.org

1, 15, 33, 35, 51, 65, 69, 77, 85, 87, 91, 95, 115, 119, 123, 133, 141, 143, 145, 159, 161, 177, 185, 187, 209, 213, 215, 217, 221, 235, 247, 249, 255, 259, 265, 267, 287, 295, 299, 303, 319, 321, 323, 329, 335, 339, 341, 345, 365, 371, 377, 391, 393, 395, 403

Offset: 1

Christian G. Bower, Nov 15 1999

nonn

Also nonprimes n such that there is only one group of order n, i.e., A000001(n) = 1.
Intersection of A018252 and A003277.
Also numbers n such that n and A051953(n) are relatively prime. - Labos Elemer
Apart from the first term, this is a subsequence of A024556. - Charles R Greathouse IV, Apr 15 2015
Every Carmichael number and each of its nonprime divisors is in this sequence. - Emmanuel Vantieghem, Apr 20 2015
An alternative definition (excluding the 1): k is strongly prime to n <=> k is prime to n and k does not divide n - 1 (cf. A181830). n is cyclic if n is prime to phi(n). n is strongly cyclic if phi(n) is strongly prime to n. The a(n) are the strongly cyclic numbers apart from a(1). - Peter Luschny, Nov 14 2018

T. D. Noe, Table of n, a(n) for n = 1..10000
Joel E. Cohen, Conjectures about Primes and Cyclic Numbers, arXiv:2508.08335 [math.NT], 2025. See pp. 2, 6.
Peter Luschny, Strong coprimality, 2011.

If the primes are included we get A003277. Cf. A000001, A000010 (phi), A181830, A181837.

isStrongPrimeTo := (n, k) -> (igcd(n, k) = 1) and not (irem(n-1, k) = 0):
isStrongCyclic := n -> isStrongPrimeTo(n, numtheory:-phi(n)):
[1, op(select(isStrongCyclic, [$(2..404)]))]; # Peter Luschny, Dec 13 2021

Select[Range[450], !PrimeQ[#] && GCD[#, EulerPhi[#]] == 1&] (* Harvey P. Dale, Jan 31 2011 *)

is(n)=!isprime(n) && gcd(eulerphi(n),n)==1 \\ Charles R Greathouse IV, Apr 15 2015

def isStrongPrimeTo(n, m): return gcd(n, m) == 1 and not m.divides(n-1)
def isStrongCyclic(n): return isStrongPrimeTo(n, euler_phi(n))
[1] + [n for n in (1..403) if isStrongCyclic(n)] # Peter Luschny, Nov 14 2018

A053285 Totient of 2^n+1.

Original entry on oeis.org

1, 2, 4, 6, 16, 20, 48, 84, 256, 324, 800, 1364, 3840, 5460, 12544, 19800, 65536, 87380, 186624, 349524, 986880, 1365336, 3345408, 5592404, 16515072, 20250000, 52306176, 84768120, 252645120, 351847488, 760320000, 1431655764, 4288266240, 5632621632, 13628740608

Offset: 0

Labos Elemer, Mar 03 2000

nonn

			It is a power of 2 iff n is a Fermat prime.

Max Alekseyev, Table of n, a(n) for n = 0..1128 (terms 0..300 from Robert Israel; terms 301..1062 from Amiram Eldar)

Cf. A000010, A000225, A002587, A000051, A046798, A046799, A049479, A051953, A054992.

[EulerPhi(2^n+1) : n in [1..40]]; // Vincenzo Librandi, Aug 12 2015

seq(numtheory:-phi(2^n+1), n=0..50); # Robert Israel, Aug 12 2015

Table[EulerPhi[2^n + 1], {n, 35}] (* Vincenzo Librandi, Aug 12 2015 *)

vector(40, n, eulerphi(2^n+1)) \\ Michel Marcus, Aug 12 2015

a(n) = A000010(A000051(n)).

a(0)=1 prepended by Alois P. Heinz, Aug 12 2015

A063528 Smallest number such that it and its successor are both divisible by an n-th power larger than 1.

Original entry on oeis.org

2, 8, 80, 80, 1215, 16767, 76544, 636416, 3995648, 24151040, 36315135, 689278976, 1487503359, 1487503359, 155240824832, 785129144319, 4857090670592, 45922887663615, 157197025673216, 1375916505694208, 2280241934368767, 2280241934368767, 2280241934368767

Offset: 1

Erich Friedman, Aug 01 2001

nonn

Lesser of the smallest pair of consecutive numbers divisible by an n-th power.
To get a(j), max exponent[=A051953(n)] of a(j) and 1+a(j) should exceed (j-1).
One can find a solution for primes p and q by solving p^n*i + 1 = q^n*j; then p^n*i is a solution. This solution will be less than (p*q)^n but greater than max(p,q)^n. Thus finding the solutions for 2, 3 (p=2,q=3 and p=3,q=2), one need at most also look at 2, 5 and 3, 5. It appears that the solution with 2, 3 is always optimal. - Franklin T. Adams-Watters, May 27 2011

			a(4) = 80 since 2^4 = 16 divides 80 and 3^4 = 81 divides 81.

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 242, p. 67, Ellipses, Paris 2008.

Franklin T. Adams-Watters, Table of n, a(n) for n = 1..100

We need A051903(a[n]) > n-1 and A051903(a[n]+1) > n-1.
Cf. A068780, A068781, A068140, A068782, A068783, A068784.
Cf. A045330, A059737.

k = 4; Do[k = k - 2; a = b = 0; While[ b = Max[ Transpose[ FactorInteger[k]] [[2]]]; a <= n || b <= n, k++; a = b]; Print[k - 1], {n, 0, 19} ]

b(n,p=2,q=3)=local(i);i=Mod(p,q^n)^-n; min(p^n*lift(i)-1,p^n*lift(-i))
a(n)=local(r);r=b(n);if(r>5^n,r=min(r,min(b(n,2,5),b(n,3,5))));r /* Franklin T. Adams-Watters, May 27 2011 */

More terms from Jud McCranie, Aug 06 2001

A063740 Number of integers k such that cototient(k) = n.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 3, 2, 0, 2, 3, 2, 1, 2, 3, 3, 1, 3, 1, 3, 1, 4, 4, 3, 0, 4, 1, 4, 3, 3, 4, 3, 0, 5, 2, 2, 1, 4, 1, 5, 1, 4, 2, 4, 2, 6, 5, 5, 0, 3, 0, 6, 2, 4, 2, 5, 0, 7, 4, 3, 1, 8, 4, 6, 1, 3, 1, 5, 2, 7, 3, 5, 1, 7, 1, 8, 1, 5, 2, 6, 1, 9, 2, 6, 0, 4, 2, 10, 2, 4, 2, 5, 2, 7, 5, 4, 1, 8, 0, 9, 1, 6, 1, 7

Offset: 2

Labos Elemer, Aug 13 2001

nonn

Note that a(0) is also well-defined to be 1 because the only solution to x - phi(x) = 0 is x = 1. - Jianing Song, Dec 25 2018

			Cototient(x) = 101 for x in {485, 1157, 1577, 1817, 2117, 2201, 2501, 2537, 10201}, with a(101) = 8 terms; e.g. 485 - phi(485) = 485 - 384 = 101. Cototient(x) = 102 only for x = 202 so a(102) = 1.

T. D. Noe, Table of n, a(n) for n = 2..10000

Cf. A000010, A051953, A063507.
Cf. A063748 (greatest solution to x-phi(x)=n).
Cf. A005278, A063741, A131825.

Table[Count[Range[n^2], k_ /; k - EulerPhi@ k == n], {n, 2, 105}] (* Michael De Vlieger, Mar 17 2017 *)

first(n)=my(v=vector(n),t); forcomposite(k=4,n^2, t=k-eulerphi(k); if(t<=n, v[t]++)); v[2..n] \\ Charles R Greathouse IV, Mar 17 2017

From Amiram Eldar, Apr 08 2023 (Start)
a(A005278(n)) = 0.
a(A131825(n)) = 1.
a(A063741(n)) = n. (End)

Name edited by Charles R Greathouse IV, Mar 17 2017

A079277 Largest integer k < n such that any prime factor of k is also a prime factor of n.

Original entry on oeis.org

1, 1, 2, 1, 4, 1, 4, 3, 8, 1, 9, 1, 8, 9, 8, 1, 16, 1, 16, 9, 16, 1, 18, 5, 16, 9, 16, 1, 27, 1, 16, 27, 32, 25, 32, 1, 32, 27, 32, 1, 36, 1, 32, 27, 32, 1, 36, 7, 40, 27, 32, 1, 48, 25, 49, 27, 32, 1, 54, 1, 32, 49, 32, 25, 64, 1, 64, 27, 64, 1, 64, 1, 64, 45, 64, 49, 72, 1, 64, 27

Offset: 2

Istvan Beck (istbe(AT)online.no), Feb 07 2003

The function a(n) complements Euler's phi-function: 1) a(n)+phi(n) = n if n is a power of a prime (actually, in A285710). 2) It seems also that a(n)+phi(n) >= n for "almost all numbers" (see A285709, A208815). 3) a(2n) = n+1 if and only if n is a Mersenne prime. 4) Lim a(n^k)/n^k =1 if n has at least two prime factors and k goes to infinity.
From Michael De Vlieger, Apr 26 2017: (Start)
In other words, largest integer k < n such that k | n^e with integer e >= 0.
Penultimate term of row n in A162306. (The last term of row n in A162306 is n.)
For prime p, a(p) = 1. More generally, for n with omega(n) = 1, that is, a prime power p^e with e > 0, a(p^e) = p^(e - 1).
For n with omega(n) > 1, a(n) does not divide n. If n = pq with q = p + 2, then p^2 < n though p^2 does not divide n, yet p^2 | n^e with e > 1. If n has more than 2 distinct prime divisors p, powers p^m of these divisors will appear in the range (1..n-1) such that p^m > n/lpf(n) (lpf(n) = A020639(n)). Since a(n) is the largest of these, a(n) is not a divisor of n.
If a(n) does not divide n, then a(n) appears last in row n of A272618.
(End)

			a(10)=8 since 8 is the largest integer< 10 that can be written using only the primes 2 and 5. a(78)=72 since 72 is the largest number less than 78 that can be written using only the primes 2, 3 and 13. (78=2*3*13).

David W. Wilson, Table of n, a(n) for n = 2..10000
Aled Walker and Alexander Walker, Arithmetic Progressions with Restricted Digits, arXiv:1809.02430 [math.NT], 2018.

Cf. A000010, A007947, A051953, A162306, A208815, A272618, A285328, A285699, A285707, A285709, A285710, A285711.

Table[If[n == 2, 1, Module[{k = n - 2, e = Floor@ Log2@ n}, While[PowerMod[n, e, k] != 0, k--]; k]], {n, 2, 81}] (* Michael De Vlieger, Apr 26 2017 *)

a(n) = {forstep(k = n - 1, 2, -1, f = factor(k); okk = 1; for (i=1, #f~, if ((n % f[i,1]) != 0, okk = 0; break;)); if (okk, return (k));); return (1);} \\ Michel Marcus, Jun 11 2013

A007947(n) = factorback(factorint(n)[, 1]); \\ Andrew Lelechenko, May 09 2014
A079277(n) = { my(r); if((n > 1 && !bitand(n,(n-1))), (n/2), r=A007947(n); if(1==n,0,k = n-1; while(A007947(k*n) <> r, k = k-1); k)); }; \\ Antti Karttunen, Apr 26 2017

from sympy import divisors
from sympy.ntheory.factor_ import core
def a007947(n): return max(d for d in divisors(n) if core(d) == d)
def a(n):
    k=n - 1
    while True:
        if a007947(k*n) == a007947(n): return k
        else: k-=1
print([a(n) for n in range(2, 101)]) # Indranil Ghosh, Apr 26 2017

Largest k < n with rad(kn) = rad(n), where rad = A007947.

A300833 Filter sequence combining A300830(n), A300831(n) and A300832(n), three products formed from such proper divisors d of n for which mu(n/d) = 0, +1 or -1 respectively, where mu is Möbius mu function (A008683).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Mar 16 2018

nonn

Restricted growth sequence transform of triple [A300830(n), A300831(n), A300832(n)].
For all i, j:
  a(i) = a(j) => A293215(i) = A293215(j) => A001065(i) = A001065(j).
  a(i) = a(j) => A051953(i) = A051953(j).
  a(i) = a(j) => A295885(i) = A295885(j).
Apparently this is also the restricted growth sequence transform of ordered pair [A300831(n), A300832(n)], which is true if it holds that whenever we have A300831(i) = A300831(j) and A300832(i) = A300832(j) for any i, j, then also A300830(i) = A300830(j). This has been checked for the first 65537 terms.

			a(39) = a(55) (= 28) as A300830(39) = A300830(55) = 1, A300831(39) = A300831(55) = 2 and A300832(39) = A300832(55) = 420.

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

Cf. A019565, A051953, A300831, A300832.

Cf. also A293214, A293215, A293226, A295885, A300825.

allocatemem(2^30);
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; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A019565(n) = {my(j,v); factorback(Mat(vector(if(n, #n=vecextract(binary(n), "-1..1")), j, [prime(j), n[j]])~))}; \\ From A019565
A300830(n) = { my(m=1); fordiv(n,d,if(!moebius(n/d),m *= A019565(d))); m; };
A300831(n) = { my(m=1); fordiv(n,d,if((d < n)&&(1==moebius(n/d)), m *= A019565(d))); m; };
A300832(n) = { my(m=1); fordiv(n,d,if(-1==moebius(n/d), m *= A019565(d))); m; };
Aux300833(n) = [A300830(n), A300831(n), A300832(n)];
write_to_bfile(1,rgs_transform(vector(up_to,n,Aux300833(n))),"b300833.txt");

cp's OEIS Frontend

A053287 Euler totient function (A000010) of 2^n - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Formula

A051709 a(n) = sigma(n) + phi(n) - 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A121998 Table, n-th row gives numbers between 1 and n that have a common factor with n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A319340 Sum of Euler totient function and its Dirichlet inverse: a(n) = A000010(n) + A023900(n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A050384 Nonprimes such that n and phi(n) are relatively prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

A053285 Totient of 2^n+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A063528 Smallest number such that it and its successor are both divisible by an n-th power larger than 1.

Views

Author

Keywords

Comments

Examples

References