A005278 -id:A005278 - cp's OEIS frontend

A063748 Greatest x that is a solution to x-phi(x)=n or zero if there is no solution, where phi(x) is Euler's totient function.

4, 9, 8, 25, 10, 49, 16, 27, 0, 121, 22, 169, 26, 55, 32, 289, 34, 361, 38, 85, 30, 529, 46, 133, 0, 187, 52, 841, 58, 961, 64, 253, 0, 323, 68, 1369, 74, 391, 76, 1681, 82, 1849, 86, 493, 70, 2209, 94, 589, 0, 667, 0, 2809, 106, 703, 104, 697, 0, 3481, 118, 3721, 122

Offset: 2

Labos Elemer, Aug 13 2001

nonn

See A051953 for x-phi(x), the cototient function. Note that a(n)=0 for n in A005278. Also note that n=1 has an infinite number of solutions. If n is prime, then a(n)=n^2. If n is even, then a(n)<=2n. In particular, if n=p+1 for a prime p, then a(n)=2n-2. Also, if n=2^k, then a(n)=2n. If n>9 is odd and composite, then a(n)=pq, with p>q odd primes with p+q=n+1 and p-q minimal. We can take p=A078496((n+1)/2) and q=A078587((n+1)/2).

			For n=15, the solutions are x=39 and x=55, so a(15)=55. Note that 55=5*11 and 5+11=n+1.

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

Cf. A000010, A051953.

Cf. A063507 (least solution to x-phi(x)=n), A063740 (number of solutions to x-phi(x)=n).

nn=10^4; lim=Floor[Sqrt[nn]]; mx=Table[0,{lim}]; Do[c=n-EulerPhi[n]; If[0T. D. Noe *)
Table[Module[{k = n^2}, While[And[k - EulerPhi@ k != n, k > 0], k--];
k], {n, 2, 62}] (* Michael De Vlieger, Mar 17 2017 *)

a(n)=Max{x : A051953(x)=n} if the inverse set is not empty; a(n)=0 if no inverse exists.

Corrected and edited by T. D. Noe, Oct 30 2006

A362486 Infinitary nontotient numbers: values not in the range of the infinitary totient function iphi (A091732).

Original entry on oeis.org

5, 7, 9, 11, 13, 14, 17, 19, 21, 23, 25, 26, 27, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 47, 49, 50, 51, 53, 55, 57, 59, 61, 62, 63, 65, 67, 68, 69, 71, 73, 74, 75, 76, 77, 79, 81, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 98, 99, 101, 103, 105, 107, 109, 110, 111

Offset: 1

Amiram Eldar, Apr 22 2023

nonn

Numbers k such that A091732(x) = k has no solution, i.e., A362485(k) = 0.

Most of the odd numbers are in this sequence. Odd numbers that are not here are 1, 3, 15, 45, 255, 765, 3825, 11475, 65535, 196605, 983025, ..., which are the values of iphi at powers of 2.

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

Cf. A091732, A362484, A362485.

Similar sequences: A005277, A005278, A347771, A362182.

Select[Range[120], Length[invIPhi[#]] == 0 &] (* using the function invIPhi from A362484 *)

A362485(a(n)) = 0.

A058811 Number of nodes at the n-th level of the Inverse-Totient-Tree (ITT) with the root at 1, and edges connecting number m to all numbers k such that phi(k) = m.

Original entry on oeis.org

1, 1, 3, 8, 17, 41, 92, 215, 487, 1126, 2583, 5981, 13698, 31647, 72678, 167474, 385021, 887133, 2041375, 4700526, 10817997, 24908164, 57334111, 131995229

Offset: 0

Labos Elemer, Jan 03 2001

Level 0 is the set {1}, and level k>=1 is the set of numbers t such that phi(t) is in the set of level k; a(n) is the cardinality of the set in level n. - Joerg Arndt, Jan 07 2015
The 3rd level is {5, 8, 10, 12, 7, 9, 14, 18} and a(3)=8. Generate invphi(5)={}, .., invphi(12)={13, 21, 26, 28, 36, 42}, ..., invphi(14)={}, .. The union of these inverses gives the 4th Floor ={15, 16, 20, 24, 30, 11, 22, 13, 21, 26, 28, 36, 42, 19, 27, 38, 54}, which has 17 terms. So a(4)=17. Each level-set may have entries either from A007617, A005278 (initial nodes of the tree) or from A000010 (invphi-continuable numbers).
Results of Shapiro show that largest number in the n-th level is 2*3^(n-1). The Mathematica code first computes A003434(k) for k <= 2*3^(n-1); then it gives the number of numbers k for which A003434(k) = n. - T. D. Noe, Mar 08 2004
Also, a(n) is the number of m such that phi^n(m) = 1, but phi^(n-1)(m) != 1. - Max Alekseyev, Jan 16 2025

			The 0th, 1st, 2nd and 3rd levels are {1}, {2}, {3, 4, 6}, {5, 7, 8, 9, 10, 12, 14, 18} with a(0) = 1, a(1) = 1, a(2) = 3, and a(3) = 8 elements, respectively.

Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A000010, A007617, A005278.

Cf. A003434 (iterations of phi(n) needed to reach 1).

Table[ Length[ Select[ Range[ 1, 1050000 ], Equal[ flo[ # ], k ]& ] ], {k, 1, 20} ], where flo[ x_ ] := Length[ Delete[ FixedPointList[ EulerPhi, x ], -1 ] ]
nMax=16; kMax=2*3^(nMax-1); a=Table[0, {kMax}]; Do[e=EulerPhi[k]; a[[k]]=1+a[[e]], {k, 2, kMax}]; Table[Count[a, _?(#==n &)], {n, 0, nMax}]

lista(nn) = {my(v = [1]); print1(#v, ", "); for (n=1, nn, my(nv = []); for (i=1, #v, nv = Set(concat(nv, invphi(v[i])));); nv = setminus(nv, v); print1(#nv, ", "); v = nv;);} \\ Michel Marcus, Sep 02 2019

a(n) = Cardinality[Floor(n)], where Floor(0) = {1}, Floor(n+1) = Union_{i=1..a(n)} invphi(t(i, n)), where t(i, n) is the i-th integer in Floor(n), ordered by size or lexicographically.

a(13)-a(16) from T. D. Noe, Mar 08 2004
a(17)-a(23) from Sean A. Irvine, Aug 28 2022
Edited by Max Alekseyev, Jan 16 2025

A362182 Unitary noncototient numbers: numbers k such that A323410(x) = k has no solution.

Original entry on oeis.org

2, 3, 5, 330, 1206, 1210, 1656, 1718, 1806, 1866, 1926, 2376, 2982, 3162, 3186, 3342, 4012, 4062, 4194, 4326, 4502, 4662, 4810, 5322, 5466, 6172, 6402, 6462, 6534, 6546, 6672, 6756, 7266, 7430, 7866, 8030, 8140, 8286, 8386, 8562, 8586, 8860, 9114, 9370, 9516, 9906

Offset: 1

Amiram Eldar, Apr 10 2023

nonn

Numbers k such that A362181(k) = 0.

Are 3 and 5 the only odd terms? There are no other odd terms below 10^5.

Amiram Eldar, Table of n, a(n) for n = 1..534 (terms below 10^5)

Cf. A323410, A362181.
The unitary version of A005278.
Similar sequences: A007617, A347771.

ucototient[n_] := n - Times @@ (Power @@@ FactorInteger[n] - 1); ucototient[1] = 0; With[{max = 2000}, Complement[Range[max], Table[ucototient[n], {n, 1, max^2}]]]

A362213 Irregular table read by rows in which the n-th row consists of all the numbers m such that cototient(m) = n, where cototient is A051953.

Original entry on oeis.org

4, 9, 6, 8, 25, 10, 15, 49, 12, 14, 16, 21, 27, 35, 121, 18, 20, 22, 33, 169, 26, 39, 55, 24, 28, 32, 65, 77, 289, 34, 51, 91, 361, 38, 45, 57, 85, 30, 95, 119, 143, 529, 36, 40, 44, 46, 69, 125, 133, 63, 81, 115, 187, 52, 161, 209, 221, 841, 42, 50, 58, 87, 247, 961

Offset: 2

Amiram Eldar, Apr 11 2023

The offset is 2 since cototient(p) = 1 for all primes p.

The 0th row consists of one term, 1, since 1 is the only solution to cototient(x) = 0.

			The table begins:
  n   n-th row
  --  -----------
   2  4;
   3  9;
   4  6, 8;
   5  25;
   6  10;
   7  15, 49;
   8  12, 14, 16;
   9  21, 27;
  10
  11  35, 121;
  12  18, 20, 22;

Amiram Eldar, Table of n, a(n) for n = 2..9674 (rows 2..1000)

Cf. A005278, A051953, A063507, A063740 (row lengths), A063741, A063742, A063748, A100827, A101373, A131825, A131826.

Similar sequences: A032447, A361966, A362180.

With[{max = 50}, cot = Table[n - EulerPhi[n], {n, 1, max^2}]; row[n_] := Position[cot, n] // Flatten; Table[row[n], {n, 2, max}] // Flatten]

A053194 a(n) is the smallest number k such that cototient(k) = 2n - 1.

Original entry on oeis.org

2, 9, 25, 15, 21, 35, 33, 39, 65, 51, 45, 95, 69, 63, 161, 87, 93, 75, 217, 99, 185, 123, 117, 215, 141, 235, 329, 159, 105, 371, 177, 135, 305, 427, 201, 335, 213, 207, 245, 511, 189, 395, 165, 415, 581, 267, 261, 623, 1501, 195, 485, 303, 225, 515, 321, 231

Offset: 1

Labos Elemer, Mar 02 2000

nonn

If the Goldbach conjecture holds, then for all odd numbers InvCot[2s-1] is nonempty.
All terms except a(1)=2 are odd numbers. All InvCototient[odd] sets seems to be nonempty, which does not hold for similar inverses of even numbers (see A005278).
Are there infinitely many semiprimes in the sequence? - Thomas Ordowski, Oct 07 2016

			n=18, a(18)=75, phi(75)=40, cototient(75) = 75-40 = 35 = 2*18-1.
n=12, a(12)=95 is the smallest in set {95, 119, 143, 529, ...} to the terms of which cototient(95) = cototient(119) = cototient(143) = cototient(529) = 95 - 72 = 119 - 96 = 143 - 120 = 529 - 506 = 23 = 2*12 - 1.

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

Cf. A005278, A051953.

N:= 1000: # to get a(1) .. a(N)
V:= Vector(N):
V[1]:= 2:
count:= 1:
for k from 3 to 10^7 by 2 while count < N do
  v:= k - numtheory:-phi(k);
  if v::odd  and v <= 2*N-1 and V[(v+1)/2] = 0 then
    count:= count+1;
    V[(v+1)/2]:= k;
  fi;
od:
convert(V,list); # Robert Israel, Oct 10 2016

Table[k = 1; While[k - EulerPhi@ k != 2 n - 1, k++]; k, {n, 120}] (* Michael De Vlieger, Oct 10 2016 *)

a(n) = k = 1; while (k - eulerphi(k) != 2*n - 1, k++); k

a(n) = Min{x : A051953(x)=2n-1}.

a(n) < (2n-1)^2 for n > 3 (if the Goldbach conjecture holds). - Thomas Ordowski, Oct 07 2016

Name corrected by Thomas Ordowski, Oct 07 2016

A058817 Even cototient numbers.

Original entry on oeis.org

0, 2, 4, 6, 8, 12, 14, 16, 18, 20, 22, 24, 28, 30, 32, 36, 38, 40, 42, 44, 46, 48, 54, 56, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 88, 90, 92, 94, 96, 98, 102, 104, 106, 108, 110, 112, 114, 118, 120, 124, 126, 128, 132, 136, 138, 140, 142, 144, 148, 150, 152

Offset: 1

Labos Elemer, Jan 04 2001

nonn

			88 is here because it is the cototient of 120: 88 = 120-phi(120) = 120-32 = 88.

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

Cf. A000010, A051953, A063742, A005277, A005278, A002202, A058763.

With[{max = 300}, Union@ Select[Table[n - EulerPhi[n], {n, 1, max^2}], # < max && EvenQ[#] &]] (* Amiram Eldar, Jan 12 2024 *)

Even terms of A063742.

Offset corrected by Donovan Johnson, Nov 17 2013

a(1) = 0 inserted by Amiram Eldar, Jan 12 2024

A072296 Least number starting a chain of exactly n consecutive even integers that do not have cototient-inverses.

Original entry on oeis.org

10, 50, 532, 2314, 4628, 22578, 115024, 221960, 478302, 3340304, 22527850, 117335136, 1118736102, 1564578508, 6121287812, 7515991946

Offset: 1

Robert G. Wilson v, Jul 12 2002

If the strong Goldbach conjecture (every even number>6 is the sum of at least 2 distinct primes p and q) is true, sequence contains only even values. Since p*q-phi(p*q)=p+q-1 and then every odd number can be expressed as x-phi(x). - Benoit Cloitre, Mar 03 2002.

			Neither 50 nor 52 have cototient-inverses and since 50 is the first of the two and the least number with this property, a(2) = 50.

Cf. A005278, A051953, A063512, A063740.

a = Table[0, {5*10^7}]; Do[b = n - EulerPhi[n]; If[ b < 5*10^7 + 1, a[[b/2]]++ ], {n, 2, 615437100}] (* used to find a(7) *) Do[ If[ a[[n]] == a[[n + 1]] == a[[n + 2]] == a[[n + 3]] == a[[n + 4]] == a[[n + 5]] == a[[n + 6]] == 0, Print[n]], {n, 1, 10^6}]

a(12)-a(14) from Donovan Johnson, Jun 23 2010

a(15)-a(16) from Donovan Johnson, Jun 03 2013

A083235 First differences of A063742, the possible values for cototients.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Labos Elemer, May 20 2003

nonn

Differences between consecutive numbers in the range of A051853.

			First missing number in A063742 is 10=A005278[1], so a[10]=2 is the first difference here > 1.

t0[x_] := Table[j, {j, 1, x}] t=Table[w-EulerPhi[w], {w, 1, 10000}]; u=Union[%]; Delete[u-RotateRight[u], 1]

a(n) = A063742(n+1) - A063742(n).

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 23 2007

A386571 Numbers that are not of the form k - omega(k), where omega(k) is the number of distinct primes dividing k.

Original entry on oeis.org

5, 9, 11, 14, 17, 21, 23, 25, 29, 35, 41, 45, 47, 51, 59, 62, 64, 65, 68, 69, 71, 76, 77, 79, 95, 101, 103, 105, 118, 119, 125, 128, 149, 152, 154, 155, 161, 163, 184, 188, 189, 191, 193, 197, 202, 208, 209, 218, 220, 221, 229, 236, 239, 241, 244, 253, 254, 258

Offset: 1

Amiram Eldar, Jul 26 2025

nonn

Luca (2005) proved that this sequence is infinite.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Florian Luca, On numbers not of the form n-omega(n), Acta Mathematica Hungarica, Vol. 106, No. 1 (2005), pp. 117-135.

Cf. A001221, A378993.

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

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

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

cp's OEIS Frontend

A063748 Greatest x that is a solution to x-phi(x)=n or zero if there is no solution, where phi(x) is Euler's totient function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A362486 Infinitary nontotient numbers: values not in the range of the infinitary totient function iphi (A091732).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A058811 Number of nodes at the n-th level of the Inverse-Totient-Tree (ITT) with the root at 1, and edges connecting number m to all numbers k such that phi(k) = m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A362182 Unitary noncototient numbers: numbers k such that A323410(x) = k has no solution.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A362213 Irregular table read by rows in which the n-th row consists of all the numbers m such that cototient(m) = n, where cototient is A051953.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A053194 a(n) is the smallest number k such that cototient(k) = 2n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A058817 Even cototient numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions