A036798 -id:A036798 - cp's OEIS frontend

A083254 a(n) = 2*phi(n) - n.

1, 0, 1, 0, 3, -2, 5, 0, 3, -2, 9, -4, 11, -2, 1, 0, 15, -6, 17, -4, 3, -2, 21, -8, 15, -2, 9, -4, 27, -14, 29, 0, 7, -2, 13, -12, 35, -2, 9, -8, 39, -18, 41, -4, 3, -2, 45, -16, 35, -10, 13, -4, 51, -18, 25, -8, 15, -2, 57, -28, 59, -2, 9, 0, 31, -26, 65, -4, 19, -22, 69, -24, 71, -2, 5, -4, 43, -30, 77, -16, 27, -2, 81, -36, 43, -2, 25

Offset: 1

Labos Elemer, May 08 2003

Möbius transform of A033879, deficiency of n. - Antti Karttunen, Dec 26 2017

			Case 1# - totient(x)-cototient[x] = 0 if x is a power of 2;
Case 2# - totient(x)>cototient[x] gives odd primes and also A067800, (= A014076 except probably A036798); e.g. n = 33: a(33) = 2.20-33 = 7; n = p prime: a(p) = p-2;
Case 3# - totient(x)<cototient[x] gives even numbers without powers of 2 and most probably A036798; e.g. n = 20: a(20) = -4; n = 105: a(105) = 2.48-105 = 96-105 = -9.

R. J. Mathar, Table of n, a(n) for n = 1..10000

Cf. A000010, A051953, A000079, A014076, A033879, A067800, A036798, A083255, A115405, A293516, A297114, A297115, A297153, A297154.

A083254 := proc(n)
    2*numtheory[phi](n)-n ;
end proc: # R. J. Mathar, Jan 13 2014

Mathematica
```
Table[2*EulerPhi[w]-w, {w, 1, 1000}]
```

a(n)=2*eulerphi(n)-n \\ Charles R Greathouse IV, Feb 21 2013

a(n) = totient(n) - cototient(n) = A000010(n) - A051953(n).
From Antti Karttunen, Dec 26 2017: (Start)
a(n) = A065620(A297153(n)) = A117966(A297154(n)).
a(n) = A297114(n) + A297115(n).
a(2n) = A297114(2n).
For all n >= 1, -a(A000010(n)) = A293516(n).
(End)
Sum_{k=1..n} a(k) ~ c * n^2, where  c = 6/Pi^2 - 1/2 = 0.107927... . - Amiram Eldar, Sep 07 2023

A054741 Numbers m such that totient(m) < cototient(m).

Original entry on oeis.org

6, 10, 12, 14, 18, 20, 22, 24, 26, 28, 30, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 105, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 130, 132, 134, 136

Offset: 1

Labos Elemer, Apr 26 2000

nonn

For powers of 2, the two function values are equal.
Numbers m such that m/phi(m) > 2. - Charles R Greathouse IV, Sep 13 2013
Numbers m such that A173557(m)/A007947(m) < 1/2. - Antti Karttunen, Jan 05 2019
Numbers m such that there are powers of m that are abundant. This follows from abundancy and totient being multiplicative, with the abundancy for prime p of p^k being asymptotically p/(p-1) as k -> oo; given that p/(p-1) = p^k/phi(p^k) for k >= 1. - Peter Munn, Nov 24 2020

			For m = 20, phi(20) = 8, cototient(20) = 20 - phi(20) = 12, 8 = phi(20) < 20-phi(20) = 12; for m = 21, the opposite holds: phi = 12, 21-phi = 8.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Mitsuo Kobayashi, A generalization of a series for the density of abundant numbers, International Journal of Number Theory, Vol. 12, No. 3 (2016), pp. 671-677.

A177712 is a subsequence. Complement: A115405.
Positions of negative terms in A083254.
Cf. A000010, A007947, A051953, A005408, A036798, A089684, A173557.
Cf. A323170 (characteristic function).
Complement of A000079\{1} within A119432.

Select[ Range[300], 2EulerPhi[ # ] < # &] (* Robert G. Wilson v, Jan 10 2004 *)

is(n)=n>2*eulerphi(n) \\ Charles R Greathouse IV, Sep 13 2013

m such that A000010(m) < A051953(m).

a(n) seems to be asymptotic to c*n with c=1.9566...... - Benoit Cloitre, Oct 20 2002 [It is an old theorem that a(n) ~ cn for some c, for any sequence of the form "m/phi(m) > k". - Charles R Greathouse IV, May 28 2015] [c is in the interval (1.9540, 1.9562) (Kobayashi, 2016). - Amiram Eldar, Feb 14 2021]

Erroneous comment removed by Antti Karttunen, Jan 05 2019

A083255 Odd composite numbers k such that cototient(k) - phi(k) = k - 2*phi(k) is an odd prime.

Original entry on oeis.org

165, 195, 5187, 5865, 7395, 10005, 15045, 16215, 21165, 22695, 27285, 37995, 42585, 44115, 50235, 57885, 59415, 60945, 64005, 310845, 346035, 347565, 486795, 635205, 707115, 890445, 979455, 994755, 1049835, 1070535, 1078815, 1083585, 1121745

Offset: 1

Labos Elemer, May 08 2003

nonn

Quite a number of terms are divisible by 3*5*17 = 255.

			m = 17425605 = 3*5*23*53*953 is a term since cototient(m) - phi(m) = 9712901 - 8712704 = 197 is an odd prime.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..369 from R. J. Mathar)

Cf. A000010, A051953, A036798, A067800, A083254.

Do[s=EulerPhi[n]; c=n-s; If[Greater[c, s]&&PrimeQ[c-s]&&OddQ[c-s]&&!PrimeQ[n], Print[{n, c-s, n/255}]], {n, 1, 10000000}]

A067800 Nonprime numbers k such that phi(k) > k/2.

Original entry on oeis.org

1, 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 111, 115, 117, 119, 121, 123, 125, 129, 133, 135, 141, 143, 145, 147, 153, 155, 159, 161, 169, 171, 175, 177, 183, 185, 187, 189, 201, 203, 205, 207, 209, 213, 215

Offset: 1

Benoit Cloitre, Feb 07 2002

nonn

Sequence is similar to A014076(n) giving odd nonprimes. Only 3 terms = 105, 165, 195 are not in the sequence among 59 terms < 210.
Cototient(m) > totient(m) equivalent to 2*phi(m) < m; the missing terms mentioned here seem to form A036798. - Labos Elemer, May 08 2003
The number 9075 is not in this sequence, is in A014076 and is not in A036798, which means that the missing terms mentioned here do not form A036798 (cf. A118700). - R. J. Mathar, Aug 08 2007

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

Cf. A000010 (phi), A014076, A036798, A051953, A083254, A118700.

Select[Range[250],!PrimeQ[#]&&EulerPhi[#]>#/2&] (* Harvey P. Dale, Aug 29 2021 *)

isok(k) = !isprime(k) && eulerphi(k) > k/2; \\ Amiram Eldar, May 08 2025

A089684 Numbers k such that 2*phi(k) > k.

Original entry on oeis.org

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127

Offset: 1

Benoit Cloitre, Jan 16 2004

Amiram Eldar, Table of n, a(n) for n = 1..10000
Amiram Eldar, Plot of a(n)/n for n = 2^(20..34).
Mitsuo Kobayashi, A generalization of a series for the density of abundant numbers, International Journal of Number Theory, Vol. 12, No. 3 (2016), pp. 671-677.
Vaclav Kotesovec, Plot of a(n)/n for n = 1..1000000.

Cf. A000010, A036798, A067800 (nonprime n such that phi(n) > n/2).
Cf. A036798, the missing odd numbers.
Complement of A119432.

lst={}; Do[If[2*EulerPhi[n]>n, AppendTo[lst, n]], {n, 200}]; lst (* T. D. Noe *)
Select[ Range[130], 2EulerPhi[ # ] > # &] (* Robert G. Wilson v, Jan 16 2004 *)

is(k) = 2*eulerphi(k) > k; \\ Amiram Eldar, Dec 01 2024

Asymptotic to c*n with c = 2.045...

2.04582 < c < 2.04818 (from the bounds on the asymptotic density of A119432 given by Kobayashi, 2016). - Amiram Eldar, Dec 01 2024

A118700 Odd n such that 2*phi(n) < n, but there does not exist an even k < n with phi(k) = phi(n).

Original entry on oeis.org

9075, 11985, 19965, 21165, 22515, 22815, 34935, 35445, 44505, 45315, 59415, 67431, 67545, 108927, 135945, 143451, 180999, 286425, 295659, 359499, 360315, 372945, 449445, 463845, 521157, 563295, 576045, 606879, 607905, 684411, 736695, 753225, 762105, 780549, 800565

Offset: 1

Franklin T. Adams-Watters, May 20 2006

nonn

			105 is the smallest odd number such that 2*phi(n) < n, but phi(105) = 48 = phi(104), so 105 is not in the sequence.

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

Members of A119434 not in A036798.

evenphimatch(n)=local(ph,i,r);ph=eulerphi(n);r=0;forstep(i=2*ph,n-1,2,if(eulerphi(i)==ph,r=i;break));r
nextoddlowphi(n)=while(2*eulerphi(n)>n,n+=2);n
i=1;while(i<1000000,i=nextoddlowphi(i+2);if(evenphimatch(i)==0,print(i)))

A326141 Odd numbers n for which A318879(n) is not zero and A318879(n) divides A318878(n); odd numbers such that A326140(n) = A318879(n).

Original entry on oeis.org

105, 195, 4785, 22515, 56865, 228285, 237315, 484245, 671853, 1838145, 1946955, 3446895, 4522695, 12955245, 37730865, 52475055, 53568885, 87612975

Offset: 1

Antti Karttunen, Jun 09 2019

Not a subsequence of A036798, even though many terms are members.

Questions: Are all terms multiples of three? Multiples of 3^(2k+1) but not of 3^(2k)? Are any of the terms included in A228058, A326137?

Index entries for sequences where any odd perfect numbers must occur

Cf. A033879, A083254, A036798, A228058, A318878, A318879, A326137, A326140.

Cf. also A325981, A326131.

isA326141(n) = if(!(n%2),0, my(t=0, u=0); fordiv(n,d, d -= 2*eulerphi(d); if(d<0, t -= d, u += d)); (gcd(t,u)==u));

A062356 a(n) = floor(n/phi(n)).

Original entry on oeis.org

1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 2

Offset: 1

Jason Earls, Jul 07 2001

Reference does not include the floor function.

See A007694 for the numbers for which n/phi(n) is an integer, and A049237 for the ratios.

D. M. Burton, Elementary Number Theory, Allyn and Bacon Inc. Boston MA, 1976, Prob. 7-4 3, p. 152.

Harry J. Smith, Table of n, a(n) for n=1,...,2000

Cf. A000010, A007694, A049237.

Table[Floor[n/EulerPhi@ n], {n, 120}] (* Michael De Vlieger, Jul 02 2016 *)

(a(n)=n\eulerphi(n)); vector(250,n,a(n)) \\ Edited by M. F. Hasler, Jul 02 2016

{ for (n=1, 2000, write("b062356.txt", n, " ", floor(n/eulerphi(n))) ) } \\ Harry J. Smith, Aug 05 2009; irrelevant realprecision(...) deleted by M. F. Hasler, Jul 02 2016

From M. F. Hasler, Jul 02 2016: (Start)
A062356(n = 2k+1) = 1 except for n in A036798.
A062356(n = 6k+2) = 2 except for n in 70*{11, 17, 23, 26, 29, 38, 44, 62, 65, 68, 77, 92, 95, 104, 110, ...} or n in 10*{2717, 4199, 4301, 4433, 4862, 5291, 5423, 6149, 6578, 7106, 8294, 8723, 9581, 9614, ...} or n = 646646, 874874, ....
A062356(n = 6k+4) = 2 except for n in 70*{13, 19, 22, 31, 34, 46, 52, 55, 58, 76, 85, 88, 91, 115, 121, ...} or n in 10*{2431, 3289, 3553, 4147, 4807, 5083, 5434, 5797, 5863, 6061, 6721, 6919, 7579, 8398, 8437, 8602, 8866, 9724, ...} or n = 782782, 986986, ....
A062356(n = 6k) = 3 except for n in 30*{7, 11, 13, 14, 21, 22, 26, 28, 33, 35, 39, 42, 44, 49, 52, 55, 56, 63, 65, 66, 70, 77, 78, 84, 88, 91, 98, 99, ...} or n in 42*{143, 187, 209, 221, 247, 253, 286, 374, 418, 429, 442, 494, 506, 561, 572, 627, 663, 741, 748, 759, 836, 858, 884,...} or n = 277134, 554268, 831402, .... (End)

A119434 Odd n such that 2*phi(n) < n.

Original entry on oeis.org

105, 165, 195, 315, 495, 525, 585, 735, 825, 945, 975, 1155, 1365, 1485, 1575, 1755, 1785, 1815, 1995, 2145, 2205, 2415, 2475, 2535, 2625, 2805, 2835, 2925, 3003, 3045, 3135, 3255, 3315, 3465, 3675, 3705, 3795, 3885, 3927, 4095, 4125, 4305, 4389, 4455

Offset: 1

Franklin T. Adams-Watters, May 19 2006

nonn

Obviously 2*phi(n) = n is impossible for odd n. Odd elements of A054741 and A119432. This is not the same as A036798. 684411 = 3*7*13*23*109 is in this sequence but not in A036798. (This is may not be the smallest such value.) The primitive elements of this sequence are A119433, excluding the initial 2
If n is in the sequence, then so is every odd multiple of n. - Robert Israel, Jan 06 2017
The asymptotic density of this sequence is in the interval (0.01120, 0.01176) (Kobayashi, 2016). It is 1/2 less than the asymptotic density of A119432. The number of terms below 10^k for k = 3, 4, ... are 11, 109, 1152, 11076, 111927, 1124091, 11224403, 112074112, ... - Amiram Eldar, Oct 15 2020

Robert Israel, Table of n, a(n) for n = 1..10000
Mitsuo Kobayashi, A generalization of a series for the density of abundant numbers, International Journal of Number Theory, Vol. 12, No. 3 (2016), pp. 671-677.

Cf. A000010, A036798, A054741, A118700, A119432, A119433, A299174.

select(t -> numtheory:-phi(t) < t/2, [seq(t,t=1..10000,2)]);

Select[Range[1, 10^4, 2], 2 EulerPhi[#] < #&] (* Jean-François Alcover, Apr 12 2019 *)

lista(nn) = forstep (n=1, nn, 2, if (n > 2*eulerphi(n), print1(n, ", "))) \\ Michel Marcus, Jul 04 2015

A036798 UNION A118700. - R. J. Mathar, Aug 08 2007

A119432 \ A299174. - Amiram Eldar, Oct 15 2020

A091495 Odd squarefree numbers k such that k/phi(k) > 2, where phi is Euler's totient function.

Original entry on oeis.org

105, 165, 195, 1155, 1365, 1785, 1995, 2145, 2415, 2805, 3003, 3045, 3135, 3255, 3315, 3705, 3795, 3885, 3927, 4305, 4389, 4485, 4515, 4641, 4785, 4845, 4935, 5115, 5187, 5313, 5565, 5655, 5865, 6045, 6105, 6195, 6405, 6555, 6765, 7035, 7095, 7215

Offset: 1

T. D. Noe, Jan 15 2004

nonn

Apparently the squarefree members of the sequence A036798. Note that 105, 165 and 195 are the only terms having 3 prime factors. Also note that all the numbers listed above have 3 as a factor. The smallest number of this form not divisible by 3 is 37182145 = 5*7*11*13*17*19*23.
From Amiram Eldar, Nov 21 2024: (Start)
If k is term and m is an odd squarefree number coprime to k, then k*m is also a term.
The numbers of terms that do not exceed 10^k, for k = 3, 4, ..., are 3, 58, 513, 5108, 52365, 523975, 5214831, 52103339, 521507571, ... . Apparently, the asymptotic density of this sequence exists and equals 0.00521... . (End)

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)

Cf. A000010, A036798, A056911, A118700.

lst={}; Do[f=FactorInteger[n]; s=Times@@Last/@f; If[s==1&&Times@@(1-1/(First/@f))<1/2, AppendTo[lst, n]], {n, 3, 10000, 2}]; lst
Select[Range[1,7301,2],SquareFreeQ[#]&&#/EulerPhi[#]>2&] (* Harvey P. Dale, Jul 10 2017 *)

is(k) = if(!(k%2), 0, my(f=factor(k)); issquarefree(f) && k / eulerphi(f) > 2); \\ Amiram Eldar, Nov 21 2024

cp's OEIS Frontend

A083254 a(n) = 2*phi(n) - n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A054741 Numbers m such that totient(m) < cototient(m).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A083255 Odd composite numbers k such that cototient(k) - phi(k) = k - 2*phi(k) is an odd prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A067800 Nonprime numbers k such that phi(k) > k/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A089684 Numbers k such that 2*phi(k) > k.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A118700 Odd n such that 2*phi(n) < n, but there does not exist an even k < n with phi(k) = phi(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A326141 Odd numbers n for which A318879(n) is not zero and A318879(n) divides A318878(n); odd numbers such that A326140(n) = A318879(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A062356 a(n) = floor(n/phi(n)).

Views

Author

Keywords

Comments