A005277 -id:A005277 - cp's OEIS frontend

A097942 Highly totient numbers: each number k on this list has more solutions to the equation phi(x) = k than any preceding k (where phi is Euler's totient function, A000010).

1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432, 480, 576, 720, 1152, 1440, 2880, 4320, 5760, 8640, 11520, 17280, 25920, 30240, 34560, 40320, 51840, 60480, 69120, 80640, 103680, 120960, 161280, 181440, 207360, 241920, 362880, 483840, 725760, 967680

Offset: 1

Alonso del Arte, Sep 05 2004

nonn

If you inspect PhiAnsYldList after running the Mathematica program below, the zeros with even-numbered indices should correspond to the nontotients (A005277).
Where records occur in A014197. - T. D. Noe, Jun 13 2006
Cf. A131934.

			a(4) = 8 since phi(x) = 8 has the solutions {15, 16, 20, 24, 30}, one more solution than a(3) = 4 for which phi(x) = 4 has solutions {5, 8, 10, 12}.

Jud McCranie, Table of n, a(n) for n = 1..109 (terms 1..79 from T. D. Noe, terms 80..86 from Donovan Johnson)
Wikipedia, Highly totient number.

A subsequence of A007374.

Cf. A000010, A005277, A014573, A004653, A105207, A105208.

HighlyTotientNumbers := proc(n) # n > 1 is search maximum
local L, m, i, r; L := NULL; m := 0;
for i from 1 to n do
  r := nops(numtheory[invphi](i));
  if r > m then L := L,[i,r]; m := r fi
od; [L] end:
A097942_list := n -> seq(s[1], s = HighlyTotientNumbers(n));
A097942_list(500); # Peter Luschny, Sep 01 2012

searchMax = 2000; phiAnsYldList = Table[0, {searchMax}]; Do[phiAns = EulerPhi[m]; If[phiAns <= searchMax, phiAnsYldList[[phiAns]]++ ], {m, 1, searchMax^2}]; highlyTotientList = {1}; currHigh = 1; Do[If[phiAnsYldList[[n]] > phiAnsYldList[[currHigh]], highlyTotientList = {highlyTotientList, n}; currHigh = n], {n, 2, searchMax}]; Flatten[highlyTotientList]

{ A097942_list(n) = local(L, m, i, r);
  m = 0;
  for(i=1, n,
\\ from Max Alekseyev, http://home.gwu.edu/~maxal/gpscripts/
   r = numinvphi(i);
   if(r > m, print1(i,", "); m = r) );
} \\ Peter Luschny, Sep 01 2012

def HighlyTotientNumbers(n) : # n > 1 is search maximum.
    R = {}
    for i in (1..n^2) :
        r = euler_phi(i)
        if r <= n :
            R[r] = R[r] + 1 if r in R else 1
    # print R.keys()   # A002202
    # print R.values() # A058277
    P = []; m = 1
    for l in sorted(R.keys()) :
        if R[l] > m : m = R[l]; P.append((l,m))
    # print [l[0] for l in P] # A097942
    # print [l[1] for l in P] # A131934
    return P
A097942_list = lambda n: [s[0] for s in HighlyTotientNumbers(n)]
A097942_list(500) # Peter Luschny, Sep 01 2012

Edited and extended by Robert G. Wilson v, Sep 07 2004

A057192 Least m such that 1 + prime(n)*2^m is a prime, or -1 if no such m exists.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 3, 6, 1, 1, 8, 2, 1, 2, 583, 1, 5, 4, 2, 3, 2, 2, 1, 1, 2, 3, 16, 3, 6, 1, 2, 1, 3, 2, 3, 4, 8, 2, 7, 1, 1, 4, 1, 2, 15, 2, 20, 8, 11, 6, 1, 1, 36, 1, 279, 29, 3, 4, 2, 1, 30, 1, 2, 9, 4, 7, 4, 4, 3, 10, 21, 1, 12, 2, 14, 6393, 11, 4, 3, 2, 1, 4, 1, 2, 6, 1, 3, 8, 5, 6, 19, 3, 2, 1, 2, 5

Offset: 1

Labos Elemer, Jan 10 2001

sign

Primes p such that p * 2^m + 1 is composite for all m are called Sierpiński numbers. The smallest known prime Sierpiński number is 271129. Currently, 10223 is the smallest prime whose status is unknown.
For 0 < k < a(n), prime(n)*2^k is a nontotient. See A005277. - T. D. Noe, Sep 13 2007
With the discovery of the primality of 10223 * 2^31172165 + 1 on November 6, 2016, we now know that 10223 is not a Sierpiński number. The smallest prime of unknown status is thus now 21181. The smallest confirmed instance of a(n) = -1 is for n = 78557. - Alonso del Arte, Dec 16 2016 [Since we only care about prime Sierpiński numbers in this sequence, 78557 should be replaced by primepi(271129) = 23738. - Jianing Song, Dec 15 2021]
Aguirre conjectured that, for every n > 1, a(n) is even if and only if prime(n) mod 3 = 1 (see the MathStackExchange link below). - Lorenzo Sauras Altuzarra, Feb 12 2021
If prime(n) is not a Fermat prime, then a(n) is also the least m such that prime(n)*2^m is a totient number, or -1 if no such m exists. If prime(n) = 2^2^e + 1 is a Fermat prime, then the least m such that prime(n)*2^m is a totient number is min{2^e, a(n)} if a(n) != -1 or 2^e if a(n) = -1, since 2^2^e * (2^2^e + 1) = phi((2^2^e+1)^2) is a totient number. For example, the least m such that 257*2^m is a totient number is m = 8, rather than a(primepi(257)) = 279; the least m such that 65537*2^m is a totient number is m = 16, rather than a(primepi(65537)) = 287. - Jianing Song, Dec 15 2021

			a(8) = 6 because prime(8) = 19 and the first prime in the sequence 1 + 19 * {2, 4, 8,1 6, 32, 64} = {39, 77, 153, 305, 609, 1217} is 1217 = 1 + 19 * 2^6.

See A046067.

T. D. Noe, Table of n, a(n) for n = 1..1000
Ray Ballinger and Wilfrid Keller, Sierpiński Problem
Timothy Revell, "Crowdsourced prime number could help solve a 50-year-old problem", New Scientist, November 18, 2016.
Tejas R. Rao, Effective primality test for p*2^n+1, p prime, n>1, arXiv:1811.06070 [math.NT], 2018.
Seventeen or Bust, A Distributed Attack on the Sierpinski problem
StackExchange, If p is prime, does there exist a positive integer k such that 2^k*p + 1 is also prime?

Cf. A058887, A058811, A058812, A002202, A014197, A005277, A005384, A005385, A051686.
Cf. A046067 (least k such that (2n - 1) * 2^k + 1 is prime).
a(n) = -1 if and only if n is in A076336.

a := proc(n)
   local m:
   m := 0:
   while not isprime(1+ithprime(n)*2^m) do m := m+1: od:
   m:
end: # Lorenzo Sauras Altuzarra, Feb 12 2021

Table[p = Prime[n]; k = 0; While[Not[PrimeQ[1 + p * 2^k]], k++]; k, {n, 100}] (* T. D. Noe *)

a(n) = my(m=0, p=prime(n)); while (!isprime(1+p*2^m), m++); m; \\ Michel Marcus, Feb 12 2021

Corrected by T. D. Noe, Aug 03 2005

A032446 Number of solutions to phi(k) = 2n.

Original entry on oeis.org

3, 4, 4, 5, 2, 6, 0, 6, 4, 5, 2, 10, 0, 2, 2, 7, 0, 8, 0, 9, 4, 3, 2, 11, 0, 2, 2, 3, 2, 9, 0, 8, 2, 0, 2, 17, 0, 0, 2, 10, 2, 6, 0, 6, 0, 3, 0, 17, 0, 4, 2, 3, 2, 9, 2, 6, 0, 3, 0, 17, 0, 0, 2, 9, 2, 7, 0, 2, 2, 3, 0, 21, 0, 2, 2, 0, 0, 7, 0, 12, 4, 3, 2, 12, 0, 2, 0, 8, 2, 10

Offset: 1

Ursula Gagelmann (gagelmann(AT)altavista.net)

By Carmichael's conjecture, a(n) <> 1 for any n. See A074987. - Thomas Ordowski, Sep 13 2017

a(n) = 0 iff n is a term of A079695. - Bernard Schott, Oct 02 2021

			If n = 8 then phi(x) = 2*8 = 16 is satisfied for only a(8) = 6 values of x, viz. 17, 32, 34, 40, 48, 60.

Albert H. Beiler, Recreations in the Theory of Numbers, The Queen of Mathematics Entertains, Second Edition, Dover Publications, Inc., NY, 1966, page 90.

T. D. Noe, Table of n, a(n) for n = 1..5000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Matteo Caorsi and Sergio Cecotti, Geometric classification of 4d N=2 SCFTs, arXiv:1801.04542 [hep-th], 2018.
Carl Pomerance, Popular values of Euler's function, Mathematica 27 (1980), 84-89.

Bisection of A014197.
Cf. A000010, A005277, A074987, A079695, A085758.
Cf. A006511 (largest k for which A000010(k) = A002202(n)), A057635.

[#EulerPhiInverse( 2*n):n in [1..100]]; // Marius A. Burtea, Sep 08 2019

with(numtheory); [ seq(nops(invphi(2*n)), n=1..90) ];

t = Table[0, {100} ]; Do[a = EulerPhi[n]; If[a < 202, t[[a/2]]++ ], {n, 3, 10^5} ]; t

a(n) = invphiNum(2*n); \\ Amiram Eldar, Nov 15 2024 using Max Alekseyev's invphi.gp

Extended by Robin Trew (trew(AT)hcs.harvard.edu).

A057826 Greatest number with totient 2n (or zero when no such number exists).

Original entry on oeis.org

6, 12, 18, 30, 22, 42, 0, 60, 54, 66, 46, 90, 0, 58, 62, 120, 0, 126, 0, 150, 98, 138, 94, 210, 0, 106, 162, 174, 118, 198, 0, 240, 134, 0, 142, 270, 0, 0, 158, 330, 166, 294, 0, 276, 0, 282, 0, 420, 0, 250, 206, 318, 214, 378, 242, 348, 0, 354, 0, 462, 0, 0, 254, 510

Offset: 1

Robert G. Wilson v, Nov 08 2000

nonn

If a(n) = 0, n is a nontotient number - see (A005277)/2.

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

Bisection of A057635. Cf. A000010, A005277, A002181.

a = Table[0, {100}]; Do[ t = EulerPhi[n]/2; If[t < 101, a[[t]] = n], {n, 1, 10^3}]; a

a(n) = invphiMax(2*n); \\ Amiram Eldar, Nov 11 2024, using Max Alekseyev's invphi.gp

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

Original entry on oeis.org

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

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

A109808 a(n) = 2*7^(n-1).

Original entry on oeis.org

2, 14, 98, 686, 4802, 33614, 235298, 1647086, 11529602, 80707214, 564950498, 3954653486, 27682574402, 193778020814, 1356446145698, 9495123019886, 66465861139202, 465261027974414, 3256827195820898, 22797790370746286, 159584532595224002, 1117091728166568014

Offset: 1

Woong Kook (andrewk(AT)math.uri.edu), Aug 16 2005

Value of Tutte dichromatic polynomial T_G(0,1) where G is the Cartesian product of the paths P_2 and P_n (n>1).
The value of Tutte dichromatic polynomial T_G(0,1) where G is the Cartesian product of the paths P_1 and P_n (n>1) is seen to be 2^(n-1), which is also the number of edge-rooted forests in P_n.
In 1956, Andrzej Schinzel showed that for every n >= 2, a(n) is not a value of Euler's function. - Arkadiusz Wesolowski, Oct 20 2013
Apart from first term 2, these are the numbers that satisfy phi(n) = 3*n/7. - Michel Marcus, Jul 14 2015

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Tanya Khovanova, Recursive Sequences.
W. Kook, Edge-rooted forests and alpha-invariant of cone graphs, Discrete Applied Mathematics, Volume 155, Issue 8, 15 April 2007, Pages 1071-1075.
Mitchell Paukner, Lucy Pepin, Manda Riehl, and Jarred Wieser, Pattern Avoidance in Task-Precedence Posets, arXiv:1511.00080 [math.CO], 2015-2016.
Index entries for linear recurrences with constant coefficients, signature (7).

Cf. A000420 (powers of 7), A005277 (nontotients), A132023.

[2*7^(n-1):n in [1..25]]; // Vincenzo Librandi, Sep 15 2011

Maple
```
a:= n-> 2*7^(n-1): seq(a(n), n=1..30);
```

2*7^Range[0, 40] (* Vladimir Joseph Stephan Orlovsky, Jun 10 2011 *)

a(n)=7^n*2/7 \\ Charles R Greathouse IV, Jun 10 2011

a(n) = 2*7^(n-1); a(n) = 7*a(n-1) where a(1) = 2.
G.f.: 2*x/(1 - 7*x). - Philippe Deléham, Nov 23 2008
E.g.f.: 2*(exp(7*x) - 1)/7. - Stefano Spezia, May 29 2021
From Amiram Eldar, May 08 2023: (Start)
Sum_{n>=1} 1/a(n) = 7/12.
Sum_{n>=1} (-1)^(n+1)/a(n) = 7/16.
Product_{n>=1} (1 - 1/a(n)) = A132023. (End)

Name changed by Arkadiusz Wesolowski, Oct 20 2013

A058888 Number of terms in the set invphi(2*prime(n)), where prime(n) is the n-th prime.

Original entry on oeis.org

4, 4, 2, 0, 2, 0, 0, 0, 2, 2, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 2, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Labos Elemer, Jan 08 2001

nonn

			The set invphi(2*3) = {7,9,14,18}. It has 4 terms, so a(2) = 4, while invphi(2*1601) = {3203,6406}, thus a(252) = 2.

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

Cf. A000010, A002202, A005277, A007617, A071629-A071634.

with(numtheory): [seq(nops(invphi(2*ithprime(i))),i=1..256)];

a(n) = invphiNum(2*prime(n)); \\ Amiram Eldar, Nov 07 2024, using Max Alekseyev's invphi.gp

Offset corrected by Donovan Johnson, Apr 28 2013

A071629 Number of terms in the set InvPhi(4*prime(n)), where prime(n) is the n-th prime.

Original entry on oeis.org

5, 6, 5, 2, 3, 2, 0, 0, 3, 3, 0, 2, 3, 2, 0, 3, 0, 0, 2, 0, 2, 2, 3, 3, 2, 0, 0, 0, 0, 3, 2, 3, 0, 2, 0, 0, 0, 2, 0, 3, 3, 0, 3, 2, 0, 2, 0, 0, 0, 0, 3, 3, 0, 3, 0, 0, 0, 0, 2, 3, 0, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 2, 0, 0, 0, 0, 0, 2, 3, 0, 3, 2, 0, 3, 0, 0, 0, 0, 0, 0, 2, 3, 2, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Labos Elemer, May 30 2002

nonn

			For n=5: invphi(4*11) = [69,92,138], a(5) = 3.

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

Cf. A000010, A002202, A005277, A007617, A058888, A071630-A071634.

[seq(nops(invphi(4*ithprime(i))),i=1..128)];

a(n) = invphiNum(4*prime(n)); \\ Amiram Eldar, Nov 07 2024, using Max Alekseyev's invphi.gp

A071634 Number of terms in the set InvPhi(1048576*prime(n)), where prime(n) is the n-th prime.

Original entry on oeis.org

23, 112, 81, 64, 75, 48, 36, 28, 43, 68, 14, 80, 35, 50, 0, 43, 28, 28, 46, 52, 44, 32, 38, 49, 48, 37, 10, 34, 24, 47, 34, 65, 19, 28, 59, 20, 32, 82, 15, 30, 61, 32, 48, 62, 10, 32, 2, 26, 18, 16, 65, 77, 0, 46, 8, 0, 43, 18, 56, 60, 0, 38, 40, 13, 36, 26, 44, 46, 41, 12, 0

Offset: 1

Labos Elemer, May 30 2002

nonn

			InvPhi(1048576*211) = {221249537,442499074}, a(47) = 2.
Observe that a(15) = 0 because 47 needs a very large 2^i multiplier (instead of 1048576) to give a nonempty InvPhi set.

Donovan Johnson, Table of n, a(n) for n = 1..1000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A002202, A005277, A007617, A058888, A071629, A071630, A071631, A071632, A071633.

>[seq(nops(invphi(1048576*ithprime(i))),i=1..128)];

a(n) = invphiNum(1048576 * prime(n)); \\ Amiram Eldar, Nov 11 2024, using Max Alekseyev's invphi.gp

cp's OEIS Frontend

A097942 Highly totient numbers: each number k on this list has more solutions to the equation phi(x) = k than any preceding k (where phi is Euler's totient function, A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Extensions

A057192 Least m such that 1 + prime(n)*2^m is a prime, or -1 if no such m exists.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A032446 Number of solutions to phi(k) = 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Extensions

A057826 Greatest number with totient 2n (or zero when no such number exists).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

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

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

A109808 a(n) = 2*7^(n-1).

Views

Author