A135832 -id:A135832 - cp's OEIS frontend

A135833 Number of Section I primes between 2^n and 2^(n+1). See A135832.

1, 2, 2, 4, 5, 7, 9, 13, 18, 21, 28, 43, 56, 62, 72, 94, 133, 142, 187, 241, 313, 376, 436, 517, 709, 858, 982, 1271, 1561, 1814, 2192, 2658, 3184, 3853, 4601, 5648, 6881, 8009, 9535, 11651, 13712, 16325, 19381, 23323, 27097, 31782, 37924, 44673, 52695, 62147

Offset: 1

T. D. Noe, Nov 30 2007

nonn

Comparing these numbers with A036378, the number of primes between 2^n and 2^(n+1), leads one to conjecture that the density of Section I primes is 0.

			3; 5, 7; 11, 13; 17, 23, 29, 31; 41, 47, 53, 59, 61; 83,...

T. D. Noe, Computing Numbers in Section I of the Totient Iteration

Cf. A092878 (number of odd numbers in Section I).

class[ n_ ] := Length[ NestWhileList[ EulerPhi,n,#>2& ] ]-1; k=2; Table[ cnt=0; While[ p=Prime[ k ]; p<2^(n+1), If[ class[ p ]==n, cnt++ ]; k++ ]; cnt, {n,20} ] (* T. D. Noe, Aug 04 2008 *)

More terms from T. D. Noe, Aug 04 2008

Extension. T. D. Noe, Nov 18 2008

A135834 Section II primes. Complement of A135832.

Original entry on oeis.org

2, 19, 37, 43, 67, 71, 73, 79, 109, 127, 131, 139, 149, 151, 157, 163, 173, 181, 191, 197, 199, 211, 223, 229, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 367, 373, 379, 383, 397, 419, 421, 431, 433, 439, 457, 463, 487, 491, 509

Offset: 1

T. D. Noe, Nov 30 2007

nonn

A058812 Irregular triangle of rows of numbers in increasing order. Row 1 = {1}. Row m + 1 contains all numbers k such that phi(k) is in row m.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 8, 9, 10, 12, 14, 18, 11, 13, 15, 16, 19, 20, 21, 22, 24, 26, 27, 28, 30, 36, 38, 42, 54, 17, 23, 25, 29, 31, 32, 33, 34, 35, 37, 39, 40, 43, 44, 45, 46, 48, 49, 50, 52, 56, 57, 58, 60, 62, 63, 66, 70, 72, 74, 76, 78, 81, 84, 86, 90, 98, 108, 114, 126

Offset: 0

Labos Elemer, Jan 03 2001

Nontotient values (A007617) are also present as inverses of some previous value.

Old name was: Irregular triangle of inverse totient values of integers generated recursively. Initial value is 1. The inverse-phi sets in increasing order are as follows: {1} -> {2} -> {3, 4, 6} -> {5, 7, 8, 9, 10, 12, 14, 18} -> ... The terms of each row are arranged by magnitude. The next row starts when the increase of terms is violated. 2^n is included in the n-th row. - David A. Corneth, Mar 26 2019

			Triangle begins:
  1;
  2;
  3, 4, 6;
  5, 7, 8, 9, 10, 12, 14, 18;
  ...
Row 3 is {3, 4, 6} as for each number k in this row, phi(k) is in row 2. - _David A. Corneth_, Mar 26 2019

T. D. Noe, Rows n=0..9 of triangle, flattened
Hartosh Singh Bal, Gaurav Bhatnagar, Prime number conjectures from the Shapiro class structure, arXiv:1903.09619 [math.NT], 2019.
T. D. Noe, Primes in classes of the iterated totient function, JIS 11 (2008) 08.1.2.
Index entries for sequences that are permutations of the natural numbers

Cf. A000010, A007617, A005277.
A058811 gives the number of terms in each row.
Cf. A003434, A007755, A060611, A092878, A098196, A135832.
Cf. also A334111.

inversePhi[m_?OddQ] = {}; inversePhi[1] = {1, 2}; inversePhi[m_] := Module[{p, nmax, n, nn}, p = Select[Divisors[m] + 1, PrimeQ]; nmax = m*Times @@ (p/(p-1)); n = m; nn = {}; While[n <= nmax, If[EulerPhi[n] == m, AppendTo[nn, n]]; n++]; nn]; row[n_] := row[n] = inversePhi /@ row[n-1] // Flatten // Union; row[0] = {1}; row[1] = {2}; Table[row[n], {n, 0, 5}] // Flatten (* Jean-François Alcover, Dec 06 2012 *)

Definition revised by T. D. Noe, Nov 30 2007

New name from David A. Corneth, Mar 26 2019

A147545 Primes of the form p*2^k+1 with k>0 and p=1 or p in this sequence.

Original entry on oeis.org

3, 5, 7, 11, 13, 17, 23, 29, 41, 47, 53, 59, 83, 89, 97, 107, 113, 137, 167, 179, 193, 227, 233, 257, 353, 359, 389, 449, 467, 641, 719, 769, 773, 857, 929, 1097, 1283, 1409, 1433, 1439, 1553, 1697, 1889, 2657, 2819, 2879, 3089, 3329, 3593, 3617, 3779, 5639

Offset: 1

T. D. Noe, Nov 07 2008

nonn

This sequence starts like A074781 but grows much faster. Observe that there can be large differences between consecutive terms. Can it be shown that there is always such a prime between consecutive powers of 2? Or that this sequence is infinite? By theorem 1 of the Noe paper, this sequence is a subsequence of A135832, primes in Section I of the phi iteration.
From Antti Karttunen, Apr 19 2020: (Start)
Sequence can be considered as a generalization of Fermat primes, A019434, which is a subsequence of this sequence.
All terms with binary weight k (A000120, at least 2 for these terms) can be found as a subset of primes found on the row k-1 of array A334100. E.g. primes with weight 2 are Fermat primes (A019434), those with weight 3 are A334092 (which doesn't contain any other primes), those with weight 4 are in A334093 (among also other kind of primes), those with weights 5, 6, 7 are included as (proper) subsets in A334094, A334095 and A334096 respectively. (End)

T. D. Noe, Table of n, a(n) for n=1..2000
T. D. Noe, Primes in classes of the iterated totient function, J. Integer Sequences, 11 (2008), Article 08.1.2.

Cf. A000265, A329697, A334100.
Subsequence of A074781, and of A135832.
Subsequences: A019434, A334092 (including A039687, A050526, A300407).

nn=2^13; t={1}; i=1; While[q=t[[i]]; k=1; While[p=1+q*2^k; p

A000265(n) = (n>>valuation(n,2));
isA147454(n) = ((n>2)&&isprime(n)&&((1==(n=A000265(n-1)))||isA147454(n))); \\ Antti Karttunen, Apr 19 2020

A329697(a(n)) = A000120(a(n)) - 1. - Antti Karttunen, Apr 19 2020

A005239 Irregular triangle of Section I numbers. Row n contains numbers k with 2^n < k < 2^(n+1) and phi^n(k) = 2, where phi^n means n iterations of Euler's totient function.

Original entry on oeis.org

3, 5, 7, 11, 13, 15, 17, 23, 25, 29, 31, 41, 47, 51, 53, 55, 59, 61, 83, 85, 89, 97, 101, 103, 107, 113, 115, 119, 121, 123, 125, 137, 167, 179, 187, 193, 205, 221, 227, 233, 235, 239, 241, 249, 251, 253, 255, 257, 289, 353, 359, 389, 391, 401, 409

Offset: 1

N. J. A. Sloane

Sequence A092878 gives the number of terms in row n. Shapiro describes how the numbers x with phi^n(x)=2 can be divided into 3 sections: I: 2^n < x < 2^(n+1), II: 2^(n+1) <= x <= 3^n and III: 3^n < x <= 2*3^n. See A058812 for the numbers x for each n. - T. D. Noe, Dec 05 2007

			Triangle begins:
   3;
   5,  7;
  11, 13, 15;
  17, 23, 25, 29,  31;
  41, 47, 51, 53,  55,  59,  61;
  83, 85, 89, 97, 101, 103, 107, 113, 115, 119, 121, 123, 125;
  ...

R. K. Guy, Unsolved Problems in Number Theory, B41.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Rows n = 1..22 of triangle, flattened
T. D. Noe, Primes in classes of the iterated totient function, JIS 11 (2008) 08.1.2.
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A000010, A058812, A092878.

Cf. A135832 (Section I primes).

nMax=10; nn=2^nMax; c=Table[0,{nn}]; Do[c[[n]]=1+c[[EulerPhi[n]]], {n,2,nn}]; t={}; Do[t=Join[t,Select[Flatten[Position[c,n]], #<2^n&]], {n,nMax}]; t (* T. D. Noe, Dec 05 2007 *)

More terms from Jud McCranie, Feb 15 1997

Corrected and extended by T. D. Noe, Dec 05 2007

cp's OEIS Frontend

A135833 Number of Section I primes between 2^n and 2^(n+1). See A135832.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A135834 Section II primes. Complement of A135832.

Views

Author

Keywords

A058812 Irregular triangle of rows of numbers in increasing order. Row 1 = {1}. Row m + 1 contains all numbers k such that phi(k) is in row m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A147545 Primes of the form p*2^k+1 with k>0 and p=1 or p in this sequence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A005239 Irregular triangle of Section I numbers. Row n contains numbers k with 2^n < k < 2^(n+1) and phi^n(k) = 2, where phi^n means n iterations of Euler's totient function.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions