A039649 -id:A039649 - cp's OEIS frontend

A039652 Becomes prime after n iterations of f(x) = phi(x)+1 (least inverse of A039651).

2, 1, 15, 35, 69, 255, 535, 949, 1957, 2513, 2923, 4531, 17701, 22957, 54589, 79421, 80029, 84493, 98581, 102827, 115243, 239111, 291149, 310813, 362621, 398893, 598341, 801923, 838307, 1063493, 1079833, 1123813, 1311121, 1329403, 1582439

Offset: 0

David W. Wilson

Of the terms n <= 66, all are semiprimes except those for n = 0, 1, 5, and 19. Why? - T. D. Noe, Oct 17 2013

T. D. Noe, Table of n, a(n) for n = 0..66

Cf. A039649, A039650, A039651, A039652, A039653, A039654, A039655, A039656.

nn = 34; t = Table[0, {nn}]; found = 0; n = 0; While[found < nn, n++; len = Length[NestWhileList[EulerPhi[#] + 1 &, n, UnsameQ, All]] - 2; If[len <= nn && t[[len]] == 0, t[[len]] = n; found++]]; t = Join[{2}, t] (* T. D. Noe, Oct 17 2013 *)

A186975 Irregular triangle T(n,k), n>=1, 1<=k<=A186971(n), read by rows: T(n,k) is the number of subsets of {1, 2, ..., n} containing n and having <=k pairwise coprime elements.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 3, 4, 1, 5, 10, 12, 1, 3, 4, 1, 7, 18, 26, 28, 1, 5, 11, 15, 16, 1, 7, 19, 29, 32, 1, 5, 10, 12, 1, 11, 42, 84, 110, 116, 1, 5, 11, 15, 16, 1, 13, 58, 137, 209, 242, 248, 1, 7, 21, 37, 46, 48, 1, 9, 30, 55, 69, 72, 1, 9, 33, 69, 98, 110, 112

Offset: 1

Alois P. Heinz, Mar 02 2011

T(n,k) = T(n,k-1) for k>A186971(n). The triangle contains all values of T up to the last element of each row that is different from its predecessor.

			T(5,3) = 10 because there are 10 subsets of {1,2,3,4,5} containing n and having <=3 pairwise coprime elements: {5}, {1,5}, {2,5}, {3,5}, {4,5}, {1,2,5}, {1,3,5}, {1,4,5}, {2,3,5}, {3,4,5}.
Triangle T(n,k) begins:
  1;
  1, 2;
  1, 3, 4;
  1, 3, 4;
  1, 5, 10, 12;
  1, 3, 4;
  1, 7, 18, 26, 28;

Alois P. Heinz, Rows n = 1..200, flattened

Columns k=1-9 give: A000012, A039649 for n>1, A186987, A186988, A186989, A186990, A186991, A186992, A186993.
Rightmost elements of rows give A186973.
Cf. A186971, A186972.

with(numtheory):
s:= proc(m,r) option remember; mul(`if`(in then 0
    elif k=1 then 1
    elif k=2 and t=n then `if`(n<2, 0, phi(n))
    else c:= 0;
         d:= 2-irem(t, 2);
         for h from 1 to n-1 by d do
           if igcd(t, h)=1 then c:= c +b(s(t*h, h), h, k-1) fi
         od; c
      fi
    end:
T:= proc(n, k) option remember;
       b(s(n, n), n, k) +`if`(k=0, 0, T(n, k-1))
    end:
seq(seq(T(n, k), k=1..a(n)), n=1..20);

s[m_, r_] := s[m, r] = Product[If[i < r, i, 1], {i, FactorInteger[m][[All, 1]]}]; a[n_] := a[n] = If[n < 4, n, PrimePi[n]-Length[FactorInteger[n]]+2]; b[t_, n_, k_] := b[t, n, k] = Module[{c, d, h}, Which[k == 0 || k > n, 0, k == 1, 1, k == 2 && t == n, If[n < 2, 0, EulerPhi[n]], True, c = 0; d = 2-Mod[t, 2]; For[h = 1, h <= n-1, h = h+d, If[GCD[t, h] == 1, c = c+b[s[t*h, h], h, k-1] ] ]; c ] ]; t[n_, k_] := t[n, k] = b[s[n, n], n, k]+If[k == 0, 0, t[n, k-1]]; Table[Table[t[n, k], {k, 1, a[n]}], {n, 1, 20}] // Flatten (* Jean-François Alcover, Dec 19 2013, translated from Maple *)

T(n,k) = Sum_{i=1..k} A186972(n,i).

A039656 Becomes prime after n iterations of f(x) = sigma(x)-1 (least inverse of A039655).

Original entry on oeis.org

2, 6, 4, 27, 12, 9, 121, 301, 930, 484, 578, 441, 1273, 468, 4863, 3171, 9216, 8373, 19692, 19416, 25442, 13440, 19230, 16641, 16804, 83161, 100652, 226181, 203400, 133200, 419248, 380979, 744796, 553296, 634710, 539476, 505584, 674416, 634206

Offset: 0

David W. Wilson

nonn

Records: 2, 6, 27, 121, 301, 930, 1273, 4863, 9216, 19692, 25442, 83161, 100652, 226181, 419248, 744796, 3739690, 4238314, etc. - Robert G. Wilson v, Sep 23 2017
Indices of records: 0, 1, 3, 6, 7, 8, 12, 14, 16, 18, 20, 25, 26, 27, 30, 32, 46, 47, 48, 49, 50, 56, 57, 58, 59, 61, 63, 65, 67, 76, 77, 78, 82, 83, 84, 85, etc. - Robert G. Wilson v, Sep 23 2017
Checked through a(138)=60780636903. - Hugo Pfoertner, Nov 15 2017

Hugo Pfoertner, Table of n, a(n) for n = 0..138 (terms up to 66 from David W. Wilson, 67-100 from Robert G. Wilson v and Charles R Greathouse IV).

Cf. A039649, A039650, A039651, A039652, A039653, A039654, A039655, A292114, A292115.

f[n_] := Plus @@ Divisors@ n -1; g[n_] := Length@ NestWhileList[f@# &, n, !PrimeQ@# &] - 1; t[] := -1; k = 2; While[k < 10000001, a = g[k]; If[ t@ a == -1, t@ a = k; Print[{a, k}]]; k++]; t@# & /@ Range[0, 50] (* _Robert G. Wilson v, Sep 22 2017 *)

A296078 Least number with the same prime signature as 1+phi(n), where phi = A000010, Euler totient function.

Original entry on oeis.org

2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 4, 2, 2, 2, 4, 6, 2, 2, 2, 2, 4, 2, 2, 6, 2, 4, 2, 2, 2, 4, 2, 2, 2, 2, 6, 4, 2, 2, 2, 2, 6, 6, 4, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 6, 4, 6, 2, 6, 12, 4, 2, 4, 2, 2, 2, 2, 2, 4, 2, 6, 6, 2, 2, 4, 6, 2, 6, 2, 2, 4, 2, 12, 2, 2, 2, 6, 2, 2, 2, 2, 2, 6, 2, 4, 4

Offset: 1

Antti Karttunen, Dec 05 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A046523, A039649, A296079, A296080.
Cf. A039698 (positions of 2's).
Cf. also A277906, A296076, A296085, A296092.

f[n_] := Block[{ps = Last@# & /@ FactorInteger[1 + EulerPhi@n]}, Times @@ ((Prime@ Range@ Length@ ps)^ps)]; Array[f, 105] (* Robert G. Wilson v, Dec 11 2017 *)

A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ This function from Charles R Greathouse IV, Aug 17 2011
A296078(n) = A046523(1+eulerphi(n));

a(n) = A046523(A039649(n)) = A046523(1+A000010(n)).

A138537 Primes p_n for which A140141(n) = 2p_n, where p_n = n-th prime (A000040).

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

Vladimir Shevelev, May 10 2008

nonn

Perhaps the same as A058340, but need proof. - Ray Chandler, May 20 2008

The first member of this sequence not in A058340 is 295937. - Robert Israel, Aug 12 2016

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

Cf. A000010, A000040, A039649, A058340, A140141.

filter:= n -> isprime(n) and numtheory:-invphi(numtheory:-phi(n))[2] = 2*n:
select(filter, [seq(i,i=2..1000)]); # Robert Israel, Aug 12 2016

Corrected and extended by Ray Chandler, May 20 2008

A296079 a(n) = 1 if 1+phi(n) is prime, 0 otherwise, where phi = A000010, Euler totient function.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0

Offset: 1

Antti Karttunen, Dec 05 2017

nonn

Out of the first 65537 values, 26197 are 1's (indicating primes), and 39340 are 0's, indicating nonprimes.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for characteristic functions

Characteristic function of A039698.
Cf. A039689 (positions of zeros).
Cf. also A296077, A296078, A296080.

Table[If[PrimeQ[EulerPhi[n]+1],1,0],{n,120}] (* Harvey P. Dale, Apr 23 2020 *)

PARI
```
A296079(n) = isprime(1+eulerphi(n));
```

a(n) = A010051(A039649(n)) = A010051(1+A000010(n)).

For all n, a(n) >= A010051(n) and a(2n) >= A010051(n).

A175177 Conjectured number of numbers for which the iteration x -> phi(x) + 1 terminates at prime(n). Cardinality of rooted tree T_p (where p is n-th prime) in Karpenko's book.

Original entry on oeis.org

2, 3, 4, 9, 2, 31, 6, 4, 2, 2, 2, 11, 24, 41, 2, 2, 2, 57, 2, 2, 58, 2, 2, 6, 17, 4, 2, 2, 39, 67, 2, 2, 2, 2, 2, 2, 25, 4, 2, 2, 2, 158, 2, 61, 2, 2, 2, 2, 2, 2, 54, 2, 186, 2, 10, 2, 2, 2, 18, 8, 2, 2, 2, 2, 96, 2, 2, 18, 2, 6, 15, 2, 2, 2, 2, 2, 2, 44, 34, 6, 2, 16, 2, 105, 2, 2, 60, 5, 4, 2, 2, 2, 4

Offset: 1

Artur Jasinski, Mar 01 2010

nonn

			a(3) = 4 because x = { 5, 8, 10, 12 } are the 4 numbers from which the iteration x -> phi(x) + 1 terminates at prime(3) = 5.
a(4) = 8 because x = { 7, 9, 14, 15, 16, 18, 20, 24, 30 } are the 9 numbers from which the iteration x -> phi(x) + 1 terminates at prime(4) = 7.

Richard K. Guy, Unsolved Problems in Number Theory, Third Edition, Springer, New York 2004. Chapter B41, Iterations of phi and sigma, page 148.
A. S. Karpenko, Lukasiewicz's Logics and Prime Numbers, (English translation), 2006. See Table 2 on p.125 ff.
A. S. Karpenko, Lukasiewicz's Logics and Prime Numbers, (Russian), 2000.

Hugo Pfoertner, Table of n, a(n) for n = 1..1000

Cf. A039649, A039650, A039651, A039652, A096827, A175178.

iterat(x) = {my(k,s); if ( isprime(x),return(x)); s=x;
for (k=1,1000000000,s=eulerphi(s)+1;if(isprime(s),return(s)));
return(s); }
check(y,endrange) = {my(count,start); count=0;
for(start=1,endrange,if(iterat(start)==y,count++;));
return(count); }
for (n=1,93,x=prime(n);print1(check(x,1000000),", "))
\\ Hugo Pfoertner, Sep 23 2017

Name clarified by Hugo Pfoertner, Sep 23 2017

A221740 a(n) = -4((n-1)(n+1)^(n+1)+1)/(((-1)^n-3)*n^3).

Original entry on oeis.org

1, 7, 19, 293, 1493, 38127, 293479, 10593529, 109739369, 5135610071, 66987982331, 3856048810781, 60693710471869, 4149140360751583, 76519827268721103, 6058888636862818097, 128138108936443028945, 11533996620790579909159

Offset: 1

Alexander R. Povolotsky, Jan 23 2013

nonn

Per exhaustive program, written for bases from 2 to 10, the number of permutations pairs, which have the same ratio, equal to A221740(n)/A221741(n) = (n^2*(n+1)^n - (n+1)^n + 1) / (-n^2 + n*(n+1)^n + (n+1)^n - n - 1), is: {2,2,3,3,5,3,7,5,7,...} for n >= 1 where n = r-1 and r is the base radix. Judging by above sequence it appears that the number of such permutations pairs is related to phi, which is the Euler totient function - according to A039649, A039650, A214288 (see bullet 1 of the analysis in the answer section of the Mathematics StackExchange link). - Alexander R. Povolotsky, Jan 26 2013

G. C. Greubel, Table of n, a(n) for n = 1..385
Mathematics StackExchange, Permutations (with no duplicates) of decimal base digits 1,2,...,8,9,0.
NMBRTHRY, Number of specific permutations pairs relates to Euler Phi totient function?

Cf. A221741, A051846.

Table[-4*((n - 1)*(n + 1)^(n + 1) + 1)/(((-1)^n - 3)*n^3), {n,1,50}] (* G. C. Greubel, Feb 19 2017 *)

makelist(-4*((n-1)*(n+1)^(n+1)+1)/(((-1)^n-3)*n^3),n,1,20); /* Martin Ettl, Jan 25 2013 */

for(n=1,25, print1(-4*((n - 1)*(n + 1)^(n + 1) + 1)/(((-1)^n - 3)*n^3), ", ")) \\ G. C. Greubel, Feb 19 2017

a(n) = -4*A051846(n)/((-3 + (-1)^n)*n).
From Alexander R. Povolotsky, Oct 12 2022: (Start)
floor(a(n+1)/A221741(n+1)) = n.
Limit_{n->oo} (a(n)/A221741(n) - floor(a(n)/A221741(n))) = 0. (End)

A221741 a(n) = -4(((n+1)^(n+1)-(n+1))/((n+1)-1)^2-1)/((-3+(-1)^n)n).

Original entry on oeis.org

1, 5, 9, 97, 373, 7625, 48913, 1513361, 13717421, 570623341, 6698798233, 350549891889, 5057809205989, 319164643134737, 5465701947765793, 403925909124187873, 8008631808527689309, 678470389458269406421, 15287592943577781017641

Offset: 1

Alexander R. Povolotsky, Jan 23 2013

Per exhaustive program, written for bases from 2 to 10, the number of permutations pairs, which have the same ratio, equal to A221740(n)/a(n) = (n^2 (n+1)^n-(n+1)^n+1) / (-n^2+n (n+1)^n+(n+1)^n-n-1), is: {2,2,3,3,5,3,7,5,7,...} for n>=1 where n=r-1 and r is the base radix. Judging by above sequence it appears that the number of such permutations pairs is related to phi, which is the Euler totient function - according to A039649, A039650, A214288 (see bullet 1 of the analysis in the answer section of the StackExchange link). Alexander R. Povolotsky, Jan 26 2013

G. C. Greubel, Table of n, a(n) for n = 1..385
NMBRTHRY, Number of specific permutations pairs relates to Euler Phi totient function ?
StackExchange, Permutations (with no duplicates) of decimal base digits 1,2,...,8,9,0.

Cf. A221740, A023811.

Table[-4*(((n + 1)^(n + 1) - (n + 1))/((n + 1) - 1)^2 - 1)/((-3 + (-1)^n)*n), {n,1,50}] (* G. C. Greubel, Feb 19 2017 *)

makelist(-4*(((n+1)^(n+1)-(n+1))/((n+1)-1)^2-1)/((-3+(-1)^n)*n), n, 1, 20); /* Martin Ettl, Jan 25 2013 */

for(n=1,25, print1(-4*(((n + 1)^(n + 1) - (n + 1))/((n + 1) - 1)^2 - 1)/((-3 + (-1)^n)*n), ", ")) \\ G. C. Greubel, Feb 19 2017

a(n) = -4*A023811(n+1)/((-3 + (-1)^n)*n).

A263027 a(n) = A002322(n) + 1, where A002322 is Carmichael lambda.

Original entry on oeis.org

2, 2, 3, 3, 5, 3, 7, 3, 7, 5, 11, 3, 13, 7, 5, 5, 17, 7, 19, 5, 7, 11, 23, 3, 21, 13, 19, 7, 29, 5, 31, 9, 11, 17, 13, 7, 37, 19, 13, 5, 41, 7, 43, 11, 13, 23, 47, 5, 43, 21, 17, 13, 53, 19, 21, 7, 19, 29, 59, 5, 61, 31, 7, 17, 13, 11, 67, 17, 23, 13, 71, 7

Offset: 1

Vincenzo Librandi, Oct 08 2015

nonn

The function t(k,n) = A002322(n)+k provides many prime values for k=1: for n up to 1000, for example, it returns 798 primes (with repetitions). On the other hand, for n <= 1000 and odd k from 3 to 11, t(k,n) gives 247, 387, 538, 231, 504 prime values, respectively.

Another function of this type is |A002322(n)-119|, which provides 693 prime values for n <= 1000. [Bruno Berselli, Oct 14 2015]

Antti Karttunen, Table of n, a(n) for n = 1..5000

Cf. A002322.
Cf. A263028: indices n for which a(n) is prime.
Cf. A263029: indices n for which a(n) is composite.
Cf. also A039649, A296076, A296077.

[2] cat [CarmichaelLambda(n)+1: n in [2..100]];

Table[CarmichaelLambda[n] + 1, {n, 1, 100}]

vector(100, n, 1 + lcm(znstar(n)[2])) \\ Altug Alkan, Oct 08 2015

Edited by Bruno Berselli, Oct 14 2015

cp's OEIS Frontend

A039652 Becomes prime after n iterations of f(x) = phi(x)+1 (least inverse of A039651).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A186975 Irregular triangle T(n,k), n>=1, 1<=k<=A186971(n), read by rows: T(n,k) is the number of subsets of {1, 2, ..., n} containing n and having <=k pairwise coprime elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A039656 Becomes prime after n iterations of f(x) = sigma(x)-1 (least inverse of A039655).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A296078 Least number with the same prime signature as 1+phi(n), where phi = A000010, Euler totient function.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A138537 Primes p_n for which A140141(n) = 2p_n, where p_n = n-th prime (A000040).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Extensions

A296079 a(n) = 1 if 1+phi(n) is prime, 0 otherwise, where phi = A000010, Euler totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A175177 Conjectured number of numbers for which the iteration x -> phi(x) + 1 terminates at prime(n). Cardinality of rooted tree T_p (where p is n-th prime) in Karpenko's book.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A221740 a(n) = -4*((n-1)*(n+1)^(n+1)+1)/(((-1)^n-3)*n^3).

Views

Author

Keywords

Comments

Links

Crossrefs

A221740 a(n) = -4((n-1)(n+1)^(n+1)+1)/(((-1)^n-3)*n^3).

A221741 a(n) = -4(((n+1)^(n+1)-(n+1))/((n+1)-1)^2-1)/((-3+(-1)^n)n).