A066074 -id:A066074 - cp's OEIS frontend

A058340 Primes p such that phi(x) = p-1 has only 2 solutions, namely x = p and x = 2p.

11, 23, 29, 31, 47, 53, 59, 67, 71, 79, 83, 103, 107, 127, 131, 137, 139, 149, 151, 167, 173, 179, 191, 197, 199, 211, 223, 227, 229, 239, 251, 263, 269, 271, 283, 293, 307, 311, 317, 331, 347, 359, 367, 373, 379, 383, 389, 419, 431, 439, 443, 463, 467, 479

Offset: 1

Labos Elemer, Dec 14 2000

nonn

Two solutions, p and 2p, exist for all odd primes p; primes in sequence have no other solutions.
Conjecture: if q > 7 is in A005385, then q is in the sequence. - Thomas Ordowski, Jan 04 2017
Proof of conjecture: q'=(q-1)/2 is an odd prime > 3.  If phi(x)=2q', which has 2-adic order 1 but is not a power of 2, there must be exactly one odd prime r dividing x.  We could also have a factor of 2 (but no higher power, which would contribute more 2's to phi(x)).  If x = r^e or 2r^e, then phi(x) = (r-1) r^(e-1).  For this to be 2q' one possibility is r-1 = 2 and r^(e-1)=q', but then q'=r=3, ruled out by q > 7.  The only other possibility is r-1=2q' and e=1, which makes r=q and x=q or 2q. - Robert Israel, Jan 04 2017
Information from Carl Pomerance: It is known that almost all primes (in the sense of relative asymptotic density) are in the sequence. - Thomas Ordowski, Jan 08 2017

			For p=2, phi(x)=1 has only two solutions, but they are 1 and 2, not 2 and 4, so 2 is not in the sequence.

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

Cf. A000010, A000040, A005385, A006093, A058339, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080, A138537.

filter:= n -> isprime(n) and nops(numtheory:-invphi(n-1))=2:
select(filter, [seq(i,i=3..10000,2)]); # Robert Israel, Aug 12 2016

Take[Rest@ Keys@ Select[KeySelect[KeyMap[# + 1 &, PositionIndex@ Array[EulerPhi, 10^4]], PrimeQ], Length@ # == 2 &], 54] (* Michael De Vlieger, Dec 29 2017 *)

a(n) ~ n log . - Charles R Greathouse IV, Nov 18 2022

Edited by Ray Chandler, Jun 06 2008

A066073 Composite numbers k such that sigma(k) - 1 is prime.

Original entry on oeis.org

6, 10, 14, 15, 20, 21, 24, 26, 30, 33, 34, 35, 38, 40, 44, 46, 51, 52, 55, 57, 58, 60, 63, 65, 74, 76, 78, 84, 85, 86, 88, 90, 92, 93, 96, 105, 111, 114, 117, 118, 120, 123, 124, 126, 130, 135, 136, 141, 143, 145, 147, 153, 155, 158, 161, 164, 166, 168, 172, 174

Offset: 1

Labos Elemer, Dec 03 2001

Composite numbers k such that sigma(k) = sigma(p) has a solution in the primes p. - Jaroslav Krizek, Feb 03 2012
Complement of A000040 (primes) with respect to A248792 (numbers n such that sigma(n) - 1 is prime). - Jaroslav Krizek, Nov 13 2014
Numbers k such that sigma(k) - 1 is greater than k and prime. - Giuseppe Coppoletta, Dec 22 2014

			30, 46, 51, and 55 are in the sequence because each is a composite number n such that sigma(n)-1 = 71, which is prime; 71 itself is excluded from the sequence by definition.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Harry J. Smith)

Cf. A000040, A000203, A058340, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080, A248792.

filter:= proc(n)
local s;
s:= numtheory:-sigma(n)-1;
  s > n and isprime(s);
end proc:
select(filter, [$2..1000]); # Robert Israel, Dec 22 2014

Do[s=-1+DivisorSigma[1, m]; If[PrimeQ[s]&&!PrimeQ[m], Print[m]], {m, 1, 256}]
Select[Range[200],CompositeQ[#]&&PrimeQ[DivisorSigma[1,#]-1]&] (* Harvey P. Dale, Jan 13 2025 *)

isA066073(n)=!isprime(n)&&isprime(sigma(n)-1) \\ Charles R Greathouse IV, Feb 20 2012

[n for n in (2..174) if (sigma(n)-1).is_prime() and sigma(n)-1>n] # Giuseppe Coppoletta, Dec 22 2014

A066071 Nonprime numbers k such that phi(k) + 1 is prime.

Original entry on oeis.org

1, 4, 6, 8, 9, 10, 12, 14, 18, 21, 22, 26, 27, 28, 32, 34, 36, 38, 40, 42, 46, 48, 49, 54, 55, 57, 58, 60, 62, 63, 74, 75, 76, 77, 82, 86, 88, 91, 93, 94, 95, 98, 99, 100, 106, 108, 110, 111, 114, 115, 117, 118, 119, 122, 124, 125, 126, 132, 133, 134, 135, 142, 145, 146

Offset: 1

Labos Elemer, Dec 03 2001

nonn

A039698 with the primes removed. For every prime p, 2p is in the sequence. - Ray Chandler, May 26 2008

Includes 3*p for p in A005382 and p^2 for p in A065508. - Robert Israel, Dec 29 2017

			Solutions to 1+phi(x)=13 are {13, 21, 26, 28, 36, 42} of which the 5 composites are in the sequence.

Iain Fox, Table of n, a(n) for n = 1..10000 (first 1000 terms from Harry J. Smith)

Cf. A000010, A000040, A005382, A006093, A039649, A039698, A058339, A058340, A065508, A066072, A066073, A066074, A066075, A066076, A066077, A066080.

[n: n in [1..200] |not IsPrime(n) and IsPrime(EulerPhi(n)+1)]; // Vincenzo Librandi, Jul 02 2016

select(n -> not isprime(n) and isprime(1+numtheory:-phi(n)), [$1..1000]); # Robert Israel, Dec 29 2017

Select[Complement[Range@ #, Prime@ Range@ PrimePi@ #] &@ 150, PrimeQ[EulerPhi@ # + 1] &] (* Michael De Vlieger, Jul 01 2016 *)

isok(k) = { !isprime(k) && isprime(eulerphi(k) + 1) } \\ Harry J. Smith, Nov 10 2009

A066076 Primes p such that there is a unique solution to p = sigma(x) - 1.

Original entry on oeis.org

2, 3, 5, 7, 13, 19, 29, 37, 43, 61, 67, 73, 101, 109, 137, 149, 157, 163, 173, 193, 197, 199, 211, 229, 241, 257, 277, 281, 283, 313, 317, 331, 337, 347, 349, 353, 367, 373, 379, 397, 401, 409, 421, 457, 461, 463, 487, 499, 509, 523, 541

Offset: 1

Labos Elemer, Dec 03 2001

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Harry J. Smith)
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000040, A000203, A058340, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080.

With[{s = KeySort@ PositionIndex@ Array[DivisorSigma[1, #] - 1 &, 10^5]}, Take[#, 51] &@ Keys@ KeySelect[s, PrimeQ@ # && Length@ Lookup[s, #] == 1 &]] (* Michael De Vlieger, Jul 16 2017 *)

{ n=0; for (m=1, 10^9, p=prime(m); a=1; for (x=1, p - 1, if (p == (sigma(x) - 1), a++; break)); if (a==1, write("b066076.txt", n++, " ", p); if (n==1000, return)) ) } \\ Harry J. Smith, Nov 10 2009

is(n) = isprime(n) && invsigmaNum(n + 1) == 1; \\ Amiram Eldar, Aug 18 2024, using Max Alekseyev's invphi.gp

If A066075(m) = 1, then prime(m) is a term.

A066075 Number of solutions x to prime(n) = sigma(x) - 1, where prime(n) is the n-th prime.

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Dec 03 2001

nonn

prime(n) itself is always the largest solution, but often composite solutions also occur.

If a(n) = 1, then the single solution is prime(n).

			For n = 96, prime(96) = 503, 503 = sigma(x)-1 has 10 solutions together with 503: {204, 220, 224, 246, 284, 286, 334, 415, 451, 503}, so a(96) = 10.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Harry J. Smith)
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Number of solutions to A000040(n) = A000203(x) - 1.

Cf. A000040, A000203, A054973, A058340, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080.

{ for (n=1, 1000, a=1; for (x=1, prime(n) - 1, if (prime(n) == (sigma(x) - 1), a++)); write("b066075.txt", n, " ", a) ) } \\ Harry J. Smith, Nov 10 2009

a(n) = invsigmaNum(prime(n)+1); \\ Amiram Eldar, Dec 16 2024, using Max Alekseyev's invphi.gp

a(n) = A054973(prime(n)+1). - Amiram Eldar, Dec 16 2024

A066077 a(n) is the number of x such that sigma(x)-1 is 0 or one of the first n-1 primes.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 10, 11, 14, 15, 17, 18, 21, 22, 25, 27, 30, 31, 32, 37, 38, 40, 43, 46, 48, 49, 51, 53, 54, 56, 58, 60, 61, 63, 64, 66, 67, 68, 74, 75, 79, 81, 86, 87, 88, 89, 90, 93, 96, 97, 100, 107, 108, 114, 115, 117, 120, 122, 123, 124, 125, 128, 130, 134, 135

Offset: 1

Labos Elemer, Dec 03 2001

nonn

Former name was: Smallest x such that p(n) = Sigma[x] - 1. That did not match the Data. See A296375 for that sequence.

Iain Fox, Table of n, a(n) for n = 1..10000

Cf. A000040, A000203, A058339, A058340, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080.

N:= 100: # To get a(1)..a(N)
P:= ithprime(N-1):
S:= select(t -> isprime(t) and t <= P,map(-1+numtheory:-sigma, [$1..P])):
T:= Statistics:-Tally(sort(S),output=table):
ListTools:-PartialSums([1,seq(T[ithprime(i)],i=1..N-1)]); # Robert Israel, Dec 27 2017

first(n) = my(res = vector(n), a = 1); res[1] = 1; for(k=2, n, for(x=1, prime(k-1), if(prime(k-1) == (sigma(x) - 1), a++)); res[k] = a); res \\ Iain Fox, Dec 28 2017

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

Edited by Robert Israel, Dec 27 2017

A066072 Prime numbers arising in A066071.

Original entry on oeis.org

2, 3, 3, 5, 7, 5, 5, 7, 7, 13, 11, 13, 19, 13, 17, 17, 13, 19, 17, 13, 23, 17, 43, 19, 41, 37, 29, 17, 31, 37, 37, 41, 37, 61, 41, 43, 41, 73, 61, 47, 73, 43, 61, 41, 53, 37, 41, 73, 37, 89, 73, 59, 97, 61, 61, 101, 37, 41, 109, 67, 73, 71, 113, 73, 73, 41, 73, 97, 61, 79, 83

Offset: 1

Labos Elemer, Dec 03 2001

nonn

			Solutions to 1+phi(x)=13 are {13, 21, 26, 28, 36, 42}; so 13 occur 5 times in the sequence in positions 10, 13, 15, 18 and 21, obtained as 1+Phi[m] values for 5 composite arguments.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Harry J. Smith)

Cf. A000010, A058340, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080.

Select[EulerPhi@ # + 1 & /@ Complement[Range@ #, Prime@ Range@ PrimePi@ #] &@ 168, PrimeQ] (* Michael De Vlieger, Jul 01 2016 *)

{ n=0; for (m=1, 10^9, if (!isprime(m) && isprime(p=(eulerphi(m) + 1)), write("b066072.txt", n++, " ", p); if (n==1000, return)) ) } \\ Harry J. Smith, Nov 10 2009

a(n) = 1 + phi(A066071(n)).

A058339 Number of solutions to 1 + phi(x) = prime(n), where phi is A000010.

Original entry on oeis.org

2, 3, 4, 4, 2, 6, 6, 4, 2, 2, 2, 8, 9, 4, 2, 2, 2, 9, 2, 2, 17, 2, 2, 6, 17, 4, 2, 2, 9, 6, 2, 2, 2, 2, 2, 2, 7, 4, 2, 2, 2, 10, 2, 21, 2, 2, 2, 2, 2, 2, 6, 2, 31, 2, 10, 2, 2, 2, 9, 8, 2, 2, 2, 2, 16, 2, 2, 18, 2, 6, 12, 2, 2, 2, 2, 2, 2, 13, 13, 6, 2, 13, 2, 34

Offset: 1

Labos Elemer, Dec 14 2000

nonn

			The equation phi(x) = p-1 always has at least 2 solutions: p and 2p a prime and a composite. Many times more than 2 x gives phi(x) = p-1. For p-1 = 96 there are 17 (that is, an odd number of) solutions: {97, 119, 153, 194, 195, 208, 224, 238, 260, 280, 288, 306, 312, 336, 360, 390, 420}, 4 odd and 13 even numbers while for p-1 = 100 there are 4 (an even number of) solutions: {101, 125, 202, 250}. For all odd solutions x, 2x is also a solution.
1+phi(x) = 11 has 2 solutions: 11 and 22; 1+phi(x) = 241 has 31 solutions: x = {241, 287, 305, 325, 369, 385, 429, 465, 482, 488, 495, 496, 525, 572, 574, 610, 616, 620, 650, 700, 732, 738, 744, 770, 792, 858, 900, 924, 930, 990, 1050}.

T. D. Noe, Table of n, a(n) for n = 1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
David M. Bressoud, CNT.m, Computational Number Theory Mathematica package.

Cf. A000010, A000040, A006093, A058340, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080.

with(numtheory): >[seq(nops(invphi(-1+ithprime(i))),i=1..256)];

Needs["CNT`"]; Table[Length[PhiInverse[Prime[n] - 1]], {n, 100}] (* T. D. Noe, Dec 11 2013 *)
Take[Length /@ Values@ KeySelect[KeyMap[# + 1 &, PositionIndex@ Array[EulerPhi, 10^4]], PrimeQ], 84] (* Michael De Vlieger, Dec 29 2017 *)

a(n) = invphiNum(prime(n) - 1); \\ Amiram Eldar, Aug 18 2024, using Max Alekseyev's invphi.gp

a(n) = A210500(n) + A210501(n). - Arkadiusz Wesolowski, Jan 19 2013

Offset corrected by Arkadiusz Wesolowski, Jan 19 2013

A206036 Numbers m such that sigma(m) = sigma(k) has solution for distinct numbers m and k.

Original entry on oeis.org

6, 10, 11, 14, 15, 16, 17, 20, 21, 23, 24, 25, 26, 28, 30, 31, 33, 34, 35, 38, 39, 40, 41, 42, 44, 46, 47, 48, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 62, 63, 65, 66, 68, 69, 70, 71, 74, 75, 76, 77, 78, 79, 80, 82, 83, 84, 85, 86, 87, 88, 89, 90, 92, 93, 94

Offset: 1

Jaroslav Krizek, Feb 03 2012

nonn

			6 and 11 are in the sequence because sigma(6) = sigma(11) = 12.
7 is not on the list because sigma(7) = 8 and there is no other integer for which sigma(n) = 8.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Complement of A211656.

Cf. A000203, A054973, A066074, A158913.

max = 9000; sigmaList = Table[DivisorSigma[1, n], {n, Prime[PrimePi[max]]}]; Select[Range[Floor[Sqrt[max]]], Count[sigmaList, sigmaList[[#]]] > 1 &] (* Alonso del Arte, Feb 06 2012 *)

is(k) = invsigmaNum(sigma(k)) > 1; \\ Amiram Eldar, Dec 15 2024, using Max Alekseyev's invphi.gp

A068014 Nonprimes n such that 1+phi(n) and -1 + sigma(n) are prime numbers.

Original entry on oeis.org

6, 10, 14, 21, 26, 34, 38, 40, 46, 55, 57, 58, 60, 63, 74, 76, 86, 88, 93, 111, 114, 117, 118, 124, 126, 135, 145, 153, 158, 166, 178, 184, 186, 190, 194, 198, 206, 208, 209, 216, 221, 224, 230, 232, 238, 250, 252, 254, 260, 266, 270, 278, 280, 295, 297, 298

Offset: 1

Labos Elemer, Feb 08 2002

nonn

1+A000010(n) and -1+A000203(n) are primes but n is nonprime.

			For n = 38, phi(38) + 1 = 19 and sigma(38) - 1 = 1 + 2 + 19 + 38 - 1 = 59. [corrected by _Peter Munn_, Dec 30 2017]

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

Cf. A000010, A000203, A058339, A058340, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080.

Do[s=-1+DivisorSigma[1, n]; s1=1+EulerPhi[n]; If[PrimeQ[s]&&PrimeQ[s1]&&!PrimeQ[n], Print[{n, s1, s}]], {n, 1, 1000}] (* generates sequence and related primes too *)
Select[Range@ 300, And[CompositeQ@ #, AllTrue[{1 + EulerPhi@ #, -1 + DivisorSigma[1, #]}, PrimeQ]] &] (* Michael De Vlieger, Dec 29 2017 *)

isok(n) = !isprime(n) && isprime(1+eulerphi(n)) && isprime(sigma(n)-1); \\ Michel Marcus, Dec 29 2017

cp's OEIS Frontend

A058340 Primes p such that phi(x) = p-1 has only 2 solutions, namely x = p and x = 2p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A066073 Composite numbers k such that sigma(k) - 1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

A066071 Nonprime numbers k such that phi(k) + 1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

A066076 Primes p such that there is a unique solution to p = sigma(x) - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A066075 Number of solutions x to prime(n) = sigma(x) - 1, where prime(n) is the n-th prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A066077 a(n) is the number of x such that sigma(x)-1 is 0 or one of the first n-1 primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A066072 Prime numbers arising in A066071.

Views

Author

Keywords

Examples