A005278 -id:A005278 - cp's OEIS frontend

A386572 Numbers that are not of the form k - Omega(k), where Omega(k) is the number of prime factors of k counted with multiplicity.

3, 11, 14, 21, 26, 29, 34, 35, 38, 45, 48, 51, 54, 57, 59, 61, 62, 64, 68, 69, 71, 74, 76, 79, 81, 87, 94, 97, 98, 101, 105, 110, 118, 123, 124, 125, 129, 133, 134, 137, 142, 147, 149, 155, 158, 160, 165, 170, 173, 174, 177, 182, 184, 186, 188, 189, 191, 193, 197

Offset: 1

Amiram Eldar, Jul 26 2025

nonn

Luca (2005) proved that this sequence is infinite, and Kátai (2006) proved that it has a positive lower density.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Imre Kátai, A remark on a paper of Luca, Acta Mathematica Hungarica, Vol. 113, No. 4 (2006), pp. 313-318.
Florian Luca, On numbers not of the form n-omega(n), Acta Mathematica Hungarica, Vol. 106, No. 1 (2005), pp. 117-135.

Cf. A001222, A069345.

Numbers not of the form k-f(k): A005278 (phi), A045765 (d), A386571 (omega), this sequence (Omega).

seq[lim_] := Complement[Range[lim], Table[k - PrimeOmega[k], {k, 1, lim + Log2[lim]}]]; seq[200]

list(lim) = setminus(vector(lim, i, i), Set(vector(lim + logint(lim, 2), i, i - bigomega(i))));

A053196 Cototients of even numbers.

Original entry on oeis.org

1, 2, 4, 4, 6, 8, 8, 8, 12, 12, 12, 16, 14, 16, 22, 16, 18, 24, 20, 24, 30, 24, 24, 32, 30, 28, 36, 32, 30, 44, 32, 32, 46, 36, 46, 48, 38, 40, 54, 48, 42, 60, 44, 48, 66, 48, 48, 64, 56, 60, 70, 56, 54, 72, 70, 64, 78, 60, 60, 88, 62, 64, 90, 64, 82, 92, 68, 72, 94, 92, 72, 96

Offset: 1

Labos Elemer, Mar 02 2000

Not all even numbers arise as cototient values: see A005278.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A000010, A051953, A005278.

[2*n-EulerPhi(2*n): n in [1..80]]; // Vincenzo Librandi, Jul 28 2013

Table[(2 n - EulerPhi[2 n]), {n, 1, 80}] (* Vincenzo Librandi, Jul 27 2013 *)

a(n) = 2*n - eulerphi(2*n) \\ Michel Marcus, Jul 26 2013

a(n) = 2n - phi(2n) = A051953(2n).

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = 2 - 8/Pi^2 = 1.1894305... . - Amiram Eldar, Dec 21 2023

A058825 Numbers which are both totients and cototients.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46, 48, 54, 56, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96, 102, 104, 106, 108, 110, 112, 120, 126, 128, 132, 136, 138, 140, 144, 148, 150, 156, 160, 162, 164, 166, 168, 176, 178, 180, 184, 190

Offset: 1

Labos Elemer, Jan 04 2001

nonn

			24 is here because 24 = phi(72) = 44-phi(44) = 44-20 = cototient(44).

Donovan Johnson, Table of n, a(n) for n = 1..10000

Cf. A000010, A051953, A005277, A005278, A002020, A058763.

Intersection(A002202, A051953).

Offset corrected by Donovan Johnson, Nov 17 2013

A058826 Even cototient numbers which are nontotients.

Original entry on oeis.org

14, 38, 62, 68, 74, 76, 90, 94, 98, 114, 118, 124, 142, 152, 158, 174, 182, 188, 194, 214, 230, 234, 236, 242, 246, 248, 254, 258, 278, 284, 286, 302, 304, 308, 314, 318, 322, 334, 338, 350, 354, 364, 370, 374, 376, 390, 398, 402, 406, 410, 414, 422, 426

Offset: 1

Labos Elemer, Jan 04 2001

nonn

			14 is a nontotient number but it is cototient of 26: 14 = 26 - phi(26).

Donovan Johnson, Table of n, a(n) for n = 1..10000

Cf. A000010, A051953, A005277, A005278, A002020, A058763, A058817.

Intersection(A058817, A005277).

A058827 Totients which are not cototients.

Original entry on oeis.org

10, 52, 58, 100, 116, 130, 172, 222, 232, 260, 268, 292, 310, 344, 346, 366, 372, 466, 490, 520, 536, 546, 562, 580, 584, 652, 688, 732, 772, 786, 808, 906, 932, 940, 980, 1018, 1038, 1068, 1072, 1108, 1160, 1168, 1192, 1210, 1300, 1332, 1360, 1372, 1376

Offset: 1

Labos Elemer, Jan 04 2001

nonn

			10, the smallest noncototient number, is the totient of 11.

Donovan Johnson, Table of n, a(n) for n = 1..10000

Cf. A000010, A051953, A005277, A005278, A002020, A058763.

Intersection(noncototients=A005278, A002202=totients).

More terms from Don Reble, Nov 28 2001

Offset corrected by Donovan Johnson, Nov 17 2013

A263958 Prime Riesel numbers p that are not Mersenne primes such that 2*p is a noncototient.

Original entry on oeis.org

509203, 2554843, 9203917, 9545351, 10645867, 11942443, 14608183, 15627133, 15811777, 16413457, 21013423, 21465637, 25792993, 30622663, 30932729, 32126257, 37996753, 40672237, 41641181, 43099781, 43773809, 47775613, 48400783, 52518187, 52992283

Offset: 1

Arkadiusz Wesolowski, Oct 30 2015

nonn

Each of the numbers 2^k*a(n), where k >= 1, is a noncototient.

J. Browkin and A. Schinzel, On integers not of the form n - phi(n), Colloq. Math. 68 (1995), pp. 55-58.
A. Flammenkamp and F. Luca, Infinite families of noncototients, Colloq. Math. 86 (2000), pp. 37-41.

Cf. A005278, A182296.

A063830 a(n+1) is the smallest odd m whose cototient equals a(n).

Original entry on oeis.org

1, 3, 9, 21, 45, 117, 297, 585, 1521, 3105, 6993, 14553, 43653, 90885, 185925, 397125, 847125, 1813125, 3238725, 7556829, 17253789, 36910365, 94571997, 220301277, 475043037, 47979336637, 183450404605, 525019294077

Offset: 1

Labos Elemer, Aug 21 2001

nonn

			a(5)=45, cototient(45) = 45 - Phi(45) = 45 - 24 = 21 = a(4). This iteration with even numbers might stop, like {1,2,4,6,10} does if the last computed number has no inverse cototient, like 10 which is a non-cototient number.

Cf. A005278, A051953.

a(n) = Min{x, odd : A051953[ a(n-1) ]=a(n)}; a(1)=1; a(2)=3, least odd prime; a(n) = Min[ Select[ Range[ a, b ], Equal[ #-EulerPhi[ # ], a(n-1) ]& ] ].

More terms from David Wasserman, Jul 23 2002

a(26)-a(28) from Donovan Johnson, Feb 06 2010

A276674 Numbers n such that x - lambda(x) = n has no solution, where lambda(x) = A002322(x).

Original entry on oeis.org

21, 28, 45, 46, 51, 64, 65, 77, 82, 85, 91, 106, 111, 126, 129, 133, 136, 148, 155, 166, 172, 175, 185, 189, 205, 208, 209, 217, 221, 225, 231, 232, 235, 237, 244, 247, 267, 273, 274, 276, 286, 291, 298, 305, 316, 319, 326, 333, 339, 341, 358, 362, 364, 365, 371

Offset: 1

Thomas Ordowski, Oct 03 2016

nonn

Problem: are there infinitely many such numbers?
Note that all these numbers are composite, because p - lambda(p) = 1 and p^2 - lambda(p^2) = p prime.
If x - lambda(x) = n > 1, then x <= n^2.
Conjecture: if x - lambda(x) = 2*m > 0, then x <= 4*m.
Noncototients among these numbers are 172, 232, 244, 274, 298, 326, 362, ...

Cf. A002322, A005278 (see links). Complement of A277127.

lista(nn) = {v = vecsort(vector(nn^2, n, n - lcm(znstar(n)[2])), ,8); for (n=1, nn, if (! vecsearch(v, n), print1(n, ", ")););} \\ Michel Marcus, Oct 03 2016

use ntheory ":all"; sub A { my $l=shift; my %C; undef $C{$-carmichael_lambda($)} for 1..$l*$l; my @R = grep { !exists $C{$} } 1..$l; @R; } say for A(500); # _Dana Jacobsen, Apr 27 2017

More terms from Michel Marcus, Oct 03 2016

A290242 The number of noncototient numbers <= 10^n.

Original entry on oeis.org

1, 8, 98, 963, 10527, 110786, 1128160, 11355049, 113482572, 1129598504

Offset: 1

Amiram Eldar, Jul 24 2017

a(5)-a(8) were taken from the paper by Pomerance and Yang.

a(9)-a(10) were taken from the paper Pollack and Pomerance.

Carl Pomerance and Hee-Sung Yang, Variant of a theorem of Erdős on the sum-of-proper-divisors function, Mathematics of Computation, Vol. 83, No. 288 (2014), pp. 1903-1913.
Paul Pollack and Carl Pomerance, Some problems of Erdős on the sum-of-divisors function, Transactions of the American Mathematical Society, Series B Vol. 3, No. 1 (2016), pp. 1-26.

Cf. A005278.

A333102 Numbers k such that both k and k + 2 are both nontotients and noncototients (A058763).

Original entry on oeis.org

532, 722, 872, 962, 1394, 1586, 1682, 1922, 2072, 2116, 2262, 2314, 2316, 2534, 2822, 2946, 3026, 3052, 3112, 3172, 3174, 3176, 3426, 3474, 3486, 3626, 3686, 3892, 4082, 4146, 4184, 4234, 4292, 4526, 4528, 4578, 4610, 4628, 5066, 5250, 5252, 5546, 5962, 5964, 6104

Offset: 1

Amiram Eldar, Mar 07 2020

nonn

			532 is a term since both 532 and 534 are both nontotients and noncototients.

Eric Weisstein's World of Mathematics, Noncototient.
Eric Weisstein's World of Mathematics, Nontotient.
Wikipedia, Noncototient.
Wikipedia, Nontotient.

Intersection of A333100 and A333101.

Cf. A005277, A005278, A058763, A063512, A072296.

cp's OEIS Frontend

A386572 Numbers that are not of the form k - Omega(k), where Omega(k) is the number of prime factors of k counted with multiplicity.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A053196 Cototients of even numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A058825 Numbers which are both totients and cototients.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A058826 Even cototient numbers which are nontotients.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A058827 Totients which are not cototients.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A263958 Prime Riesel numbers p that are not Mersenne primes such that 2*p is a noncototient.

Views

Author

Keywords

Comments

Links

Crossrefs

A063830 a(n+1) is the smallest odd m whose cototient equals a(n).

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

A276674 Numbers n such that x - lambda(x) = n has no solution, where lambda(x) = A002322(x).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Perl

Extensions

A290242 The number of noncototient numbers <= 10^n.

Views

Author

Keywords

Comments

Links