A051953 -id:A051953 - cp's OEIS frontend

A063507 Least k such that k - phi(k) = n, or 0 if no such k exists.

2, 4, 9, 6, 25, 10, 15, 12, 21, 0, 35, 18, 33, 26, 39, 24, 65, 34, 51, 38, 45, 30, 95, 36, 69, 0, 63, 52, 161, 42, 87, 48, 93, 0, 75, 54, 217, 74, 99, 76, 185, 82, 123, 60, 117, 66, 215, 72, 141, 0, 235, 0, 329, 78, 159, 98, 105, 0, 371, 84, 177, 122, 135, 96, 305, 90, 427

Offset: 1

Labos Elemer, Aug 09 2001

nonn

Inverse cototient (A051953) sets represented by their minimum, as in A002181 for totient function. Impossible values (A005278) are replaced by zero.

If a(n) > 0, then it appears that a(n) > 1.26n. - T. D. Noe, Dec 06 2006

			x = InvCototient[24] = {36, 40, 44, 46}; Phi[x] = Phi[{36, 40, 44, 46}] = {12, 16, 20, 22}; x-Phi[x] = {24, 24, 24, 24}, so a(24) = Min[InvCototient[24]]; a(10) = 0 because 10 is in A005278.

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

Cf. A051953, A000010, A002181, A005277, A005278.
Cf. A063748 (greatest solution to x-phi(x)=n).
Cf. A063740 (number of k such that cototient(k) = n).

Table[SelectFirst[Range[n^2 + 1], # - EulerPhi[#] == n &] /. k_ /; ! IntegerQ@ k -> 0, {n, 67}] (* Michael De Vlieger, Jan 11 2018 *)

a(n)-A051953(a(n)) = n if possible and a(n)=0 if n belongs to A005278.

Edited by N. J. A. Sloane, Oct 25 2008 at the suggestion of R. J. Mathar

A068418 Composite numbers k such that k - phi(k) divides sigma(k) - k.

Original entry on oeis.org

12, 56, 260, 992, 1320, 1976, 2156, 2754, 3696, 5520, 13800, 16256, 19872, 22560, 23688, 25232, 41072, 87000, 89964, 133984, 145888, 366720, 785808, 851760, 1100864, 1235052, 1270208, 1439552, 1470720, 2129400, 2237888, 4729664

Offset: 1

Benoit Cloitre, Mar 03 2002

If 2^p - 1 is prime (a Mersenne prime) then k = 2^p*(2^p - 1) is in the sequence because 3*k - 2*phi(k) = sigma(k) (see Comments at A068414) so sigma(k) - k = 2*(k - phi(k)) hence k - phi(k) divides sigma(k) - k. - Farideh Firoozbakht, Dec 31 2005

Also if 3*2^m - 1 is a prime greater than 5 then k = 15*2^(m+1)*(3*2^m - 1) is in the sequence because 4*k - 3*phi(k) = 4*15*2^(m+1)*(3*2^m - 1) - 3*2^(m+3)*(3*2^m - 2) = 24*(3*2^m)*(2^(m+2) - 1) = sigma(15)*sigma(3*2^m - 1)*sigma(2^(m+1)) = sigma(15*(3*2^m - 1)*2^(m+1)) = sigma(k) hence sigma(k) - k = 3*(k - phi(k)) and k - phi(k) divides sigma(k) - k. - Farideh Firoozbakht, Dec 31 2005

Donovan Johnson, Table of n, a(n) for n = 1..68 (terms < 10^11)

A068414 is the subsequence telling when the quotient is 2.

Cf. A068414, A051953, A000203, A000668.

Do[s=(DivisorSigma[1, n]-n)/(n-EulerPhi[n]); If[ !PrimeQ[n]&&IntegerQ[s], Print[n]], {n, 2, 10000000}]

for(n=1,300000, if((sigma(n)-n)%(n-eulerphi(n))==isprime(n),print1(n,",")))

More terms from Labos Elemer, Apr 02 2002

A306927 a(n) = A001615(n) - n.

Original entry on oeis.org

0, 1, 1, 2, 1, 6, 1, 4, 3, 8, 1, 12, 1, 10, 9, 8, 1, 18, 1, 16, 11, 14, 1, 24, 5, 16, 9, 20, 1, 42, 1, 16, 15, 20, 13, 36, 1, 22, 17, 32, 1, 54, 1, 28, 27, 26, 1, 48, 7, 40, 21, 32, 1, 54, 17, 40, 23, 32, 1, 84, 1, 34, 33, 32, 19, 78, 1, 40, 27, 74, 1, 72

Offset: 1

Torlach Rush, Mar 16 2019

Analogous to A051953.
a(n) = A051953(n) if n is an element of A000961.
a(n) > A051953(n) if n is an element of A024619.
The sum of the proper divisors d of n such that n/d is squarefree. - Amiram Eldar, Sep 06 2019

			0 is a term because A001615(1) - 1 = 0.
1 is a term because A001615(2) - 2 = 1.
3 is a term because A001615(9) - 9 = 3.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Wikipedia, Dedekind psi function.

Cf. A000961, A001615, A024619, A051953, A082020.

a[1] = 0; a[n_] := n * (Times @@ (1 + 1/FactorInteger[n][[;; , 1]]) - 1); Array[a, 100] (* Amiram Eldar, Sep 06 2019 *)

a(n) = n*(sumdivmult(n, d, issquarefree(d)/d) - 1); \\ Michel Marcus, Mar 18 2019

a(n) = A001615(n) - n.
a(n) = Sum_{d|n, dAmiram Eldar, Sep 06 2019
Sum_{k=1..n} a(k) = c * n^2 / 2 + O(n*log(n)), where c = 15/Pi^2 - 1 = 0.519817... . - Amiram Eldar, Dec 08 2023

A070556 a(n) = cototient(totient(n)).

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 4, 2, 4, 2, 6, 2, 8, 4, 4, 4, 8, 4, 12, 4, 8, 6, 12, 4, 12, 8, 12, 8, 16, 4, 22, 8, 12, 8, 16, 8, 24, 12, 16, 8, 24, 8, 30, 12, 16, 12, 24, 8, 30, 12, 16, 16, 28, 12, 24, 16, 24, 16, 30, 8, 44, 22, 24, 16, 32, 12, 46, 16, 24, 16, 46, 16, 48

Offset: 1

N. J. A. Sloane, May 06 2002

G. C. Greubel, Table of n, a(n) for n = 1..10000

Cf. A000010, A051953, A054571.

[EulerPhi(n)-EulerPhi(EulerPhi(n)): n in [1..100]]; // Vincenzo Librandi, Aug 06 2015

A051953 := proc(n)
        n-numtheory[phi](n) ;
end proc:
A070556 := proc(n)
        A051953(numtheory[phi](n)) ;
end proc: # R. J. Mathar, Oct 13 2011

Table[EulerPhi[n] - EulerPhi[EulerPhi[n]], {n, 80}] (* Vincenzo Librandi, Aug 06 2015 *)

a(n) = A051953(A000010(n)).

A098006 (p-1)/2 - phi(p-1) as p runs through the odd primes.

Original entry on oeis.org

0, 0, 1, 1, 2, 0, 3, 1, 2, 7, 6, 4, 9, 1, 2, 1, 14, 13, 11, 12, 15, 1, 4, 16, 10, 19, 1, 18, 8, 27, 17, 4, 25, 2, 35, 30, 27, 1, 2, 1, 42, 23, 32, 14, 39, 57, 39, 1, 42, 4, 23, 56, 25, 0, 1, 2, 63, 50, 44, 49, 2, 57, 35, 60, 2, 85, 72, 1, 62, 16, 1, 63, 66, 81, 1, 2, 78, 40, 76, 29, 114, 47

Offset: 2

N. J. A. Sloane, Sep 08 2004

In the Luca-Walsh paper it is shown that there are infinitely many numbers not in this sequence. See A098047.

a(n)=0 for Fermat primes (A019434). a(n)=1 for safe primes (A005385). a(n)=2 for A090866. The least prime p for which (p-1)/2-phi(p-1)=n or 0 if there is no such prime is given by A134765(n). Sequence A134854(k) gives the least prime for which a(n)=2^(k-1). For k not a power of 2, it can be shown that if k is in this sequence, then it appears for a prime p <= 1+k^2. - T. D. Noe, Nov 13 2007

J. Browkin and A. Schinzel, On integers not of the form n-phi(n), Colloq. Math., 68 (1995), 55-58.
F. Luca and P. G. Walsh, On the number of nonquadratic residues which are not primitive roots, Colloq. Math., 100 (2004), 91-93.

T. D. Noe, Table of n, a(n) for n = 2..10000
T. D. Noe, Finding primes p for which (p-1)/2 - phi(p-1) = k

Cf. A000010, A051953, A098047, A176095 (p runs through the odd numbers).

a098006 n = a005097 (n-1) - a000010 (a006093 n)
-- Reinhard Zumkeller, Mar 26 2013

[(NthPrime(n)-1)/2 - EulerPhi(NthPrime(n)-1): n in [2..100]]; // Vincenzo Librandi, Jan 10 2017

A098006 := proc(n)
    local p;
    p := ithprime(n+1) ;
    (p-1)/2-numtheory[phi](p-1) ;
end proc:
seq(A098006(n),n=1..30) ; # R. J. Mathar, Jan 09 2017

Table[(Prime[n] - 1)/2 - EulerPhi[Prime[n] - 1], {n, 2, 85}] (* Robert G. Wilson v, Sep 09 2004 *)
Table[(n-1)/2-EulerPhi[n-1],{n,Prime[Range[2,100]]}] (* Harvey P. Dale, Oct 23 2016 *)

forprime(p=3,1e3,print1(p\2-eulerphi(p-1)", ")) \\ Charles R Greathouse IV, Feb 04 2013

a(n) = A005097(n-1) - A000010(A006093(n)); a(A159611(n)) = 0. - Reinhard Zumkeller, Mar 26 2013

A181833 The number of positive integers <= n that are not strongly prime to n.

Original entry on oeis.org

0, 0, 2, 3, 4, 4, 6, 5, 6, 7, 9, 5, 10, 7, 10, 11, 12, 6, 14, 7, 14, 15, 16, 5, 18, 13, 17, 13, 20, 7, 24, 9, 18, 19, 22, 15, 28, 10, 22, 19, 28, 9, 32, 9, 26, 27, 30, 5, 34, 17, 33, 25, 32, 7, 38, 23, 36, 29, 34, 5, 46

Offset: 0

Peter Luschny, Nov 17 2010

nonn

k is strongly prime to n iff k is relatively prime to n and k does not divide n-1.
a(n) = n - phi(n) + tau(n-1) if n > 0 and a(0) = 0.
Here phi(n) = A000010(n) and tau(n) = A000005(n).

			a(11) = 11 - card({3,4,6,7,8,9}) = 5.

Peter Luschny, Strong coprimality.

Cf. A181830, A181831, A181832, A181834, A181835, A181836, A051953.

with(numtheory):
A181833 := n -> `if`(n=0,0,n-phi(n)+tau(n-1));
A181833a := n -> n - A181830(n);

a[n_] := Select[Range[n], Not[CoprimeQ[#, n] && !Divisible[n-1, #]] &] // Length; a[1] = 0; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Jun 28 2013 *)

A051487 Numbers k such that phi(k) = phi(k - phi(k)).

Original entry on oeis.org

2, 6, 12, 24, 48, 96, 150, 192, 300, 384, 600, 726, 750, 768, 1200, 1452, 1500, 1536, 2310, 2400, 2904, 3000, 3072, 3174, 3750, 4620, 4800, 5046, 5808, 5874, 6000, 6090, 6144, 6348, 6930, 7500, 7986, 9240, 9600, 10086, 10092, 10374, 11550, 11616, 11748, 12000

Offset: 1

R. K. Guy

This sequence is infinite, in fact 3*2^n is a subsequence because if m = 3*2^n then phi(m-phi(m)) = phi(3*2^n-2^n) = 2^n = phi(m). Also, if p is a Sophie Germain prime greater than 3 then for each natural number n, 2^n*3*p^2 is in the sequence. Note that there exist terms of this sequence like 750 or 2310 that they aren't of either of these forms. - Farideh Firoozbakht, Jun 19 2005
If n is an even term greater than 2 in this sequence then 2n is also in the sequence. Because for even numbers m we have phi(2m) = 2*phi(m) so phi(2n) = 2*phi(n) = 2*phi(n-phi(n)) and since n is an even number greater than 2, n-phi(n) is even so 2*phi(n-phi(n)) = phi(2n-2*phi(n)) = phi(2n-phi(2n)) hence phi(2n) = phi(2n-phi(2n)) and 2n is in the sequence. Conjecture: All terms of this sequence are even. - Farideh Firoozbakht, Jul 04 2005
If n is in the sequence and the natural number m divides gcd(n,phi(n)) then m*n is in the sequence. The facts that I have found about this sequence earlier (Jun 19 2005 and Jul 04 2005) are consequences of this. If p is a Sophie Germain prime greater than 3, k>1 and k & n are natural numbers then 2^n*3*p^k are in the sequence. - Farideh Firoozbakht, Dec 10 2005
Numbers n such that phi(n) = phi(n + phi(n)) includes all n = 2^k. - Jonathan Vos Post, Oct 25 2007

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B42, p. 150.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Aleksander Grytczuk, Florian Luca and Marek Wojtowicz, A conjecture of Erdős concerning inequalities for the Euler totient function, Publ. Math. Debrecen, Vol. 59, No. 1-2, (2001), pp. 9-16.

Cf. A005384, A051488.

Cf. A000010, A051953.

a051487 n = a051487_list !! (n-1)
a051487_list = [x | x <- [2..], let t = a000010 x, t == a000010 (x - t)]
-- Reinhard Zumkeller, Jun 03 2013

Select[Range[11700], EulerPhi[ # ] == EulerPhi[ # - EulerPhi[ # ]] &] (* Farideh Firoozbakht, Jun 19 2005 *)

isA051487(n) = eulerphi(n) == eulerphi(n - eulerphi(n)) \\ Michael B. Porter, Dec 07 2009

More terms from James Sellers

A053044 a(n) is the number of iterations of the Euler totient function to reach 1, starting at n!.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 10, 13, 15, 18, 21, 24, 27, 30, 33, 37, 41, 44, 47, 51, 54, 58, 62, 66, 70, 74, 77, 81, 85, 89, 93, 98, 102, 107, 111, 115, 119, 123, 127, 132, 137, 141, 145, 150, 154, 159, 164, 169, 173, 178, 183, 188, 193, 197, 202, 207, 211, 216, 221, 226, 231

Offset: 1

Labos Elemer, Feb 25 2000

nonn

Powers of 2 arise at the end of iteration chains without interruption. Analogous to A053025 and A053034. The order of speed of convergence is as follows: A000005 > A000010 > A051953: e.g., for 20! the lengths of the corresponding iteration chains are 6, 51, and 101, respectively.

Partial sums of A064415.

			For n=1, no iteration is needed, so a(1)=0;
for n=2, the initial value is 2! = 2, so phi() must be applied once, thus a(2)=1;
for n=8, the iteration chain is {40320, 9216, 3072, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}; its length = 14 = a(8) + 1, so the number of iterations applied to reach 1 is a(8)=13.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]

Cf. A000010, A000142, A003434, A053025, A053034.

Cf. also A064415.

Table[Length@ NestWhileList[EulerPhi, n!, # > 1 &] - 1, {n, 61}] (* or *)
Table[Length@ FixedPointList[EulerPhi, n!] - 2, {n, 61}] (* Michael De Vlieger, Jan 01 2017 *)

a(n) = {my(nb = 0, ns = n!); while (ns != 1, ns = eulerphi(ns); nb++); nb;} \\ Michel Marcus, Jan 01 2017

a(n) = A003434(A000142(n)). - Michel Marcus, Jan 01 2017

A053144 Cototient of the n-th primorial number.

Original entry on oeis.org

1, 4, 22, 162, 1830, 24270, 418350, 8040810, 186597510, 5447823150, 169904387730, 6317118448410, 260105476071210, 11228680258518030, 529602053223499410, 28154196550210460730, 1665532558389396767070

Offset: 1

Labos Elemer, Feb 28 2000

nonn

a(n) > A005367(n), a(n) > A002110(n)/2.

Limit_{n->oo} a(n)/A002110(n) = 1 because (in the limit) the quotient is the probability that a randomly selected integer contains at least one of the first n primes in its factorization. - Geoffrey Critzer, Apr 08 2010

			In the reduced residue system of q(4) = 2*3*5*7 - 210 the number of coprimes to 210 is 48, while a(4) = 210 - 48 = 162 is the number of values divisible by one of the prime factors of q(4).

Michael De Vlieger, Table of n, a(n) for n = 1..350

Cf. A002110, A051953, A005867, A038110, A038111, A174909, A293558.
Cf. A000040 (prime numbers).
Cf. A161527, A060753.
Column 1 of A281891.

Abs[Table[ Total[Table[(-1)^(k + 1)* Total[Apply[Times, Subsets[Table[Prime[n], {n, 1, m}], {k}], 2]], {k, 0, m - 1}]], {m, 1, 22}]] (* Geoffrey Critzer, Apr 08 2010 *)
Array[# - EulerPhi@ # &@ Product[Prime@ i, {i, #}] &, 17] (* Michael De Vlieger, Feb 17 2019 *)

a(n) = prod(k=1, n, prime(k)) - prod(k=1, n, prime(k)-1); \\ Michel Marcus, Feb 08 2019

a(n) = A051953(A002110(n)) = A002110(n) - A005867(n).
a(n) = a(n-1)*A000040(n) + A005867(n-1). - Bob Selcoe, Feb 21 2016
a(n) = (1/A000040(n+1) - A038110(n+1)/A038111(n+1))*A002110(n+1). - Jamie Morken, Feb 08 2019
a(n) = A161527(n)*A002110(n)/A060753(n+1). - Jamie Morken, May 13 2022

A053192 a(n) is the cototient of n^3.

Original entry on oeis.org

0, 4, 9, 32, 25, 144, 49, 256, 243, 600, 121, 1152, 169, 1568, 1575, 2048, 289, 3888, 361, 4800, 3969, 5808, 529, 9216, 3125, 9464, 6561, 12544, 841, 19800, 961, 16384, 14157, 20808, 13475, 31104, 1369, 28880, 22815, 38400, 1681, 52920, 1849, 46464

Offset: 1

Labos Elemer, Mar 02 2000

For n^k, n^k - EulerPhi(n^k) = n^(k-1)*(n-EulerPhi(n)), or cototient(n^k) = n^(k-1)*cototient(n). A similar relation holds for Euler totient function.

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

Cf. A000010, A051953, A002618, A053650, A053191, A001248, A229099.

[n^3-EulerPhi(n^3): n in [1..44]]; // Vincenzo Librandi, Jul 28 2013

Table[(n^3 - EulerPhi[n^3]), {n, 1, 50}] (* Vincenzo Librandi, Jul 27 2013 *)

a(n) = n^3 - eulerphi(n^3) \\ Michel Marcus, Jul 26 2013

a(n) = n^2*Cototient(n) = A051953(n^3) = n^3 - EulerPhi(n^3) = Cototient(n^3).
a(prime(n)) = A051953(prime(n)^3) = A001248(n).
Sum_{k=1..n} a(k) ~ c * n^4 / 4, where c = 1 - 6/Pi^2 (A229099). - Amiram Eldar, Dec 15 2023

cp's OEIS Frontend

A063507 Least k such that k - phi(k) = n, or 0 if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A068418 Composite numbers k such that k - phi(k) divides sigma(k) - k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A306927 a(n) = A001615(n) - n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A070556 a(n) = cototient(totient(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A098006 (p-1)/2 - phi(p-1) as p runs through the odd primes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

A181833 The number of positive integers <= n that are not strongly prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A051487 Numbers k such that phi(k) = phi(k - phi(k)).

Views

Author

Keywords

Comments

References

Links