A066073 -id:A066073 - cp's OEIS frontend

A066074 Primes arising in A066073.

11, 17, 23, 23, 41, 31, 59, 41, 71, 47, 53, 47, 59, 89, 83, 71, 71, 97, 71, 79, 89, 167, 103, 83, 113, 139, 167, 223, 107, 131, 179, 233, 167, 127, 251, 191, 151, 239, 181, 179, 359, 167, 223, 311, 251, 239, 269, 191, 167, 179, 227, 233, 191, 239, 191, 293

Offset: 1

Labos Elemer, Dec 03 2001

nonn

			p=71 appears in the sequence at 9th, 16th, 17th and 19th positions as -1+sigma(x) for x=30, 46, 51, 55.

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

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

Do[s=-1+DivisorSigma[1, n]; If[PrimeQ[s]&&!PrimeQ[n], Print[s]], {n, 1, 256}]

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

lista(nn) = forcomposite(n=1, nn, if (isprime(p=(sigma(n)-1)), print1(p, ", "))); \\ Michel Marcus, Jan 05 2018

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

Original entry on oeis.org

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

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

A248792 Numbers n such that sigma(n) - 1 is a prime p.

Original entry on oeis.org

2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 20, 21, 23, 24, 26, 29, 30, 31, 33, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 51, 52, 53, 55, 57, 58, 59, 60, 61, 63, 65, 67, 71, 73, 74, 76, 78, 79, 83, 84, 85, 86, 88, 89, 90, 92, 93, 96, 97, 101, 103, 105, 107, 109

Offset: 1

Jaroslav Krizek, Nov 01 2014

Union of primes (A000040) and terms of A066073 (composites).
Numbers n such that A039653(n) is prime.
Corresponding values of primes p are in A248793.

			6 is in sequence because sigma(6) - 1 = 12 - 1 = 11 (prime).

Michael De Vlieger, Table of n, a(n) for n = 1..10000
OEIS Wiki, Cyclotomic Polynomials at x=n, n! and sigma(n)

Cf. A000203 (sum of divisors), A000040 (primes).
Cf. A039653 (sigma(n)-1), A066073 (subsequence of composites), A248793.
Cf. A065512 (numbers n such that sigma(n) + 1 is prime).

[n: n in[1..1000] | IsPrime(SumOfDivisors(n) - 1)];

with(numtheory): A248792:=n->`if`(isprime(sigma(n)-1), n, NULL): seq(A248792(n), n=1..200); # Wesley Ivan Hurt, Jul 09 2015

Select[Range[110], PrimeQ[DivisorSigma[1, #] - 1] &] (* Vincenzo Librandi, Nov 02 2014 *)

for(n=1,10^3,if(isprime(sigma(n)-1),print1(n,", "))) \\ Derek Orr, Nov 01 2014

A206447 Composite numbers n such that sigma(n) = sigma(d) has solution for some other composite number d.

Original entry on oeis.org

14, 15, 16, 20, 24, 25, 26, 28, 30, 33, 35, 38, 39, 40, 42, 44, 46, 48, 51, 54, 55, 56, 58, 60, 62, 65, 66, 68, 69, 70, 75, 77, 78, 80, 82, 84, 87, 88, 90, 92, 94, 95, 96, 99, 102, 104, 105, 108, 110, 112, 114, 115, 116, 118, 119, 120, 122, 123, 124, 125

Offset: 1

Jaroslav Krizek, Feb 07 2012

nonn

			Composite numbers 14 and 15 are in sequence because sigma(14) = sigma(15) = 24.

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

Cf. A206036, A158913, A066073.

N:= 500:
Res:= {}: Q:= {}:
for n from 4 to N do
  if isprime(n) then next fi;
  s:= numtheory:-sigma(n);
  if not assigned(V[s]) then
     V[s]:= n;
     if s > N then Q:= Q union {n} fi;
  else
     Res:= Res union {n,V[s]};
     if s > N then Q:= Q minus {V[s]} fi;
  fi
od:
convert(select(`<`,Res, min(Q)),list); # Robert Israel, Dec 17 2017

t2 = Table[If[PrimeQ[n], 0, DivisorSigma[1, n]], {n, 1000}]; Select[Range[132], ! PrimeQ[#] && Length[Position[t2, t2[[#]]]] > 1 &] (* T. D. Noe, Feb 27 2012 *)

cp's OEIS Frontend

A066074 Primes arising in A066073.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

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

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

Links

Crossrefs