A097942 -id:A097942 - cp's OEIS frontend

A209195 Smallest prime factor of the n-th highly totient number (A097942(n)) plus 1.

2, 3, 5, 3, 13, 5, 7, 73, 5, 241, 433, 13, 577, 7, 1153, 11, 43, 29, 7, 8641, 41, 11, 7, 30241, 17, 61, 47, 31, 13, 11, 103681, 73, 161281, 13, 7, 241921, 19, 41, 293, 11, 17, 1451521, 31, 2177281, 83, 2903041, 11, 4354561, 109, 5806081, 13, 8709121, 9676801

Offset: 1

N. J. A. Sloane, Mar 05 2012

nonn

Amiram Eldar, Table of n, a(n) for n = 1..109 (calculated from the b-file at A097942)

Cf. A020639, A097942.

a(n) = A020639(A097942(n) + 1). - Amiram Eldar, Jul 08 2019

More terms from Amiram Eldar, Jul 08 2019

A014197 Number of numbers m with Euler phi(m) = n.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

Carmichael conjectured that there are no 1's in this sequence. - Jud McCranie, Oct 10 2000
Number of cyclotomic polynomials of degree n. - T. D. Noe, Aug 15 2003
Let v == 0 (mod 24), w = v + 24, and v < k < q < w, where k and q are integer. It seems that, for most values of v, there is no b such that b = a(k) + a(q) and b > a(v) + a(w). The first case where b > a(v) + a(w) occurs at v = 888: b = a(896) + a(900) = 15 + 4, b > a(888) + a(912), or 19 > 8 + 7. The first case where v < n < w and a(n) > a(v) + a(w) occurs at v = 2232: a(2240) > a(2232) + a(2256), or 27 > 7 + 8. - Sergey Pavlov, Feb 05 2017
One elementary result relating to phi(m) is that if m is odd, then phi(m)=phi(2m) because 1 and 2 both have phi value 1 and phi is multiplicative. - Roderick MacPhee, Jun 03 2017

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B39, pp. 144-146.
Joe Roberts, Lure of The Integers, The Mathematical Association of America, 1992, entry 32, page 182.

T. D. Noe, Table of n, a(n) for n = 1..10000
Max A. Alekseyev, Computing the Inverses, their Power Sums, and Extrema for Euler's Totient and Other Multiplicative Functions, Journal of Integer Sequences, Vol. 19 (2016), Article 16.5.2.
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
R. D. Carmichael, On Euler’s phi-function, Bull. Amer. Math. Soc. 13 (1907), 241-243.
R. D. Carmichael, Note on Euler’s phi-function, Bull. Amer. Math. Soc. 28 (1922), 109-110.
Kevin Ford, The number of solutions of phi(x)=m, arXiv:math/9907204 [math.NT], 1999.
S. Sivasankaranarayana Pillai, On some functions connected with phi(n), Bull. Amer. Math. Soc. 35 (1929), 832-836.
Primefan, Totient Answers For The First 1000 Integers.
Eric Weisstein's World of Mathematics, Totient Function.
Eric Weisstein's World of Mathematics, Totient Valence Function.

Cf. A000010, A002202, A032446 (bisection), A049283, A051894, A055506, A057635, A057826, A058277 (nonzero terms), A058341, A063439, A066412, A070243 (partial sums), A070633, A071386 (positions of odd terms), A071387, A071388 (positions of primes), A071389 (where prime(n) occurs for the first time), A082695, A097942 (positions of records), A097946, A120963, A134269, A219930, A280611, A280709, A280712, A296655 (positions of positive even terms), A305353, A305656, A319048, A322019.
For records see A131934.
Column 1 of array A320000.

a := function(n)
local S, T, R, max, i, k, r;
S:=[];
for i in DivisorsInt(n)+1 do
    if IsPrime(i)=true then
        S:=Concatenation(S,[i]);
    fi;
od;
T:=[];
for k in [1..Size(S)] do
    T:=Concatenation(T,[S[k]/(S[k]-1)]);
od;
max := n*Product(T);
R:=[];
for r in [1..Int(max)] do
    if Phi(r)=n then
        R:=Concatenation(R,[r]);
    fi;
od;
return Size(R);
end; # Miles Englezou, Oct 22 2024

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

with(numtheory): A014197:=n-> nops(invphi(n)): seq(A014197(n), n=1..200);

a[1] = 2; a[m_?OddQ] = 0; a[m_] := Module[{p, nmax, n, k}, p = Select[ Divisors[m]+1, PrimeQ]; nmax = m*Times @@ (p/(p - 1)); n = m; k = 0; While[n <= nmax, If[EulerPhi[n] == m, k++]; n++]; k]; Array[a, 92] (* Jean-François Alcover, Dec 09 2011, updated Apr 25 2016 *)
With[{nn = 116}, Function[s, Function[t, Take[#, nn] &@ ReplacePart[t, Map[# -> Length@ Lookup[s, #] &, Keys@ s]]]@ ConstantArray[0, Max@ Keys@ s]]@ KeySort@ PositionIndex@ Array[EulerPhi, Floor[nn^(3/2)] + 10]] (* Michael De Vlieger, Jul 19 2017 *)

A014197(n,m=1) = { n==1 && return(1+(m<2)); my(p,q); sumdiv(n, d, if( d>=m && isprime(d+1), sum( i=0,valuation(q=n\d,p=d+1), A014197(q\p^i,p))))} \\ M. F. Hasler, Oct 05 2009

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

from sympy import totient, divisors, isprime, prod
def a(m):
    if m == 1: return 2
    if m % 2: return 0
    X = (x + 1 for x in divisors(m))
    nmax=m*prod(i/(i - 1) for i in X if isprime(i))
    n=m
    k=0
    while n<=nmax:
        if totient(n)==m:k+=1
        n+=1
    return k
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 18 2017, after Mathematica code

Dirichlet g.f.: Sum_{n>=1} a(n)*n^-s = zeta(s)*Product_(1+1/(p-1)^s-1/p^s). - Benoit Cloitre, Apr 12 2003
Limit_{n->infinity} (1/n) * Sum_{k=1..n} a(k) = zeta(2)*zeta(3)/zeta(6) = 1.94359643682075920505707036... (see A082695). - Benoit Cloitre, Apr 12 2003
From Christopher J. Smyth, Jan 08 2017: (Start)
Euler transform = Product_{n>=1} (1-x^n)^(-a(n)) = g.f. of A120963.
Product_{n>=1} (1+x^n)^a(n)
= Product_{n>=1} ((1-x^(2n))/(1-x^n))^a(n)
= Product_{n>=1} (1-x^n)^(-A280712(n))
= Euler transform of A280712 = g.f. of A280611.
(End)
a(A000010(n)) = A066412(n). - Antti Karttunen, Jul 18 2017
From Antti Karttunen, Dec 04 2018: (Start)
a(A000079(n)) = A058321(n).
a(A000142(n)) = A055506(n).
a(A017545(n)) = A063667(n).
a(n) = Sum_{d|n} A008683(n/d)*A070633(d).
a(n) = A056239(A322310(n)).
(End)

A007374 Smallest k such that phi(x) = k has exactly n solutions, n>=2.

Original entry on oeis.org

1, 2, 4, 8, 12, 32, 36, 40, 24, 48, 160, 396, 2268, 704, 312, 72, 336, 216, 936, 144, 624, 1056, 1760, 360, 2560, 384, 288, 1320, 3696, 240, 768, 9000, 432, 7128, 4200, 480, 576, 1296, 1200, 15936, 3312, 3072, 3240, 864, 3120, 7344, 3888, 720, 1680, 4992

Offset: 2

N. J. A. Sloane, Mira Bernstein, Robert G. Wilson v

The Carmichael Totient Conjecture is that there is no k such that phi(x) = k has a unique solution x. So a(1) does not exist.

Ford proved that a(n) exists for all n > 1. - Charles R Greathouse IV, Oct 13 2014

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
Wacław Sierpiński, Elementary Theory of Numbers, p. 234, Warsaw, 1964.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jud McCranie, Table of n, a(n) for n = 2..10000 (terms up to 1..1023 from T. D. Noe, terms 1024..7448 from Donovan Johnson)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Kevin Ford, The distribution of totients, Ramanujan J., (2) No. 1-2 (1998); New version of the 1998 article, arXiv:1104.3264 [math.NT], 2011-2013.
Kevin Ford, The number of solutions of phi(x) = m, Annals of Mathematics 150:1 (1999), pp. 283-311.
S. D. Merow, Has Carmichael's Totient Conjecture Been Proven? No, No, It Has Not, Notices Amer. Math. Soc., 66 (No. 5, 2019), 759-761.
A. Schlafly and S. Wagon, Carmichael's conjecture on the Euler function is valid below 10^{10,000,000}, Mathematics of Computation, 63 No. 207 (1994), 415-419. See Table 2.
Eric Weisstein's World of Mathematics, Phi function.
Eric Weisstein's World of Mathematics, Carmichael's Totient Function Conjecture.

Essentially same as A014573. Records in A105207, A105208.

Cf. A000010, A097942, A105207, A105208.

a = Table[ 0, {10^5} ]; Do[ s = EulerPhi[ n ]; If[ s < 100001, a[ [ s ] ]++ ], {n, 1, 10^6} ]; Do[ k = 1; While[ a[ [ k ] ] != n, k++ ]; Print[ k ], {n, 2, 75} ]

v=vectorsmall(10^6);for(n=1,1e7,t=eulerphi(n);if(t<=#v,v[t]++))
u=vector(100);for(i=1,#v,t=v[i];if(t&&t<=#u&&u[t]==0,u[t]=i)); u[2..#u]
\\ Charles R Greathouse IV, Oct 13 2014

A036913 Sparsely totient numbers; numbers n such that m > n implies phi(m) > phi(n).

Original entry on oeis.org

2, 6, 12, 18, 30, 42, 60, 66, 90, 120, 126, 150, 210, 240, 270, 330, 420, 462, 510, 630, 660, 690, 840, 870, 1050, 1260, 1320, 1470, 1680, 1890, 2310, 2730, 2940, 3150, 3570, 3990, 4620, 4830, 5460, 5610, 5670, 6090, 6930, 7140, 7350, 8190, 9240, 9660

Offset: 1

David W. Wilson

nonn

The paper by Masser and Shiu lists 150 terms of this sequence less than 10^6. For odd prime p, they show that p# and p*p# are in this sequence, where p# denotes the primorial (A002110). - T. D. Noe, Jun 14 2006

Conjecture: Except for 2 and 18, all terms are Zumkeller numbers (A083207). Verified for the first 1800 terms. - Ivan N. Ianakiev, Sep 04 2022

			This sequence contains 60 because of all the numbers whose totient is <=16, 60 is the largest such number. [From _Graeme McRae_, Feb 12 2009]
From _Michael De Vlieger_, Jun 25 2017: (Start)
Positions of primorials A002110(k) in a(n):
     n     k       a(n) = A002110(k)
  ----------------------------------
     1     1                       2
     2     2                       6
     5     3                      30
    13     4                     210
    31     5                    2310
    69     6                   30030
   136     7                  510510
   231     8                 9699690
   374     9               223092870
   578    10              6469693230
   836    11            200560490130
  1169    12           7420738134810
  1591    13         304250263527210
  2149    14       13082761331670030
  2831    15      614889782588491410
  3667    16    32589158477190044730
  4661    17  1922760350154212639070
(End)

T. D. Noe, Table of n, a(n) for n = 1..5000
Roger C. Baker and Glyn Harman, Sparsely totient numbers, Annales de la Faculté des Sciences de Toulouse Ser. 6, 5 no. 2 (1996), 183-190.
Glyn Harman, On sparsely totient numbers, Glasgow Math. J. 33 (1991), 349-358.
D. W. Masser and P. Shiu, On sparsely totient numbers, Pacific J. Math. 121, no. 2 (1986), 407-426.
Michael De Vlieger, Largest k such that A002110(k) | a(n) and A287352(a(n)).
Michael De Vlieger, First term m > prime(n)^2 in A036913 such that gcd(prime(n), m) = 1.

Cf. A097942 (highly totient numbers). Records in A006511 (see also A132154).

nn=10000; lastN=Table[0,{nn}]; Do[e=EulerPhi[n]; If[e<=nn, lastN[[e]]=n], {n,10nn}]; mx=0; lst={}; Do[If[lastN[[i]]>mx, mx=lastN[[i]]; AppendTo[lst,mx]], {i,Length[lastN]}]; lst (* T. D. Noe, Jun 14 2006 *)

A100827 Highly cototient numbers: records for a(n) in A063741.

Original entry on oeis.org

2, 4, 8, 23, 35, 47, 59, 63, 83, 89, 113, 119, 167, 209, 269, 299, 329, 389, 419, 509, 629, 659, 779, 839, 1049, 1169, 1259, 1469, 1649, 1679, 1889, 2099, 2309, 2729, 3149, 3359, 3569, 3989, 4199, 4289, 4409, 4619, 5249, 5459, 5879, 6089, 6509, 6719, 6929

Offset: 1

Alonso del Arte, Jan 06 2005

nonn

Each number k on this list has more solutions to the equation x - phi(x) = k (where phi is Euler's totient function, A000010) than any preceding k except 1.
This sequence is a subset of A063741. As noted in that sequence, there are infinitely many solutions to x - phi(x) = 1. Unlike A097942, the highly totient numbers, this sequence has many odd numbers besides 1.
With the expection of 2, 4, 8, all of the known terms are congruent to -1 mod a primorial (A002110). The specific primorial satisfying this congruence would result in a sequence similar to A080404 a(n)=A007947[A055932(n)]. - Wilfredo Lopez (chakotay147138274(AT)yahoo.com), Dec 28 2006
Because most of the solutions to x - phi(x) = k are semiprimes p*q with p+q=k+1, it appears that this sequence eventually has terms that are one less than the Goldbach-related sequence A082917. In fact, terms a(108) to a(176) are A082917(n)-1 for n=106..174. [T. D. Noe, Mar 16 2010] This holds through a(229).  [Jud McCranie, May 18 2017]

			a(3) = 8 since x - phi(x) = 8 has three solutions, {12, 14, 16}, one more than a(2) = 4 which has two solutions, {6, 8}.

Jud McCranie, Table of n, a(n) for n = 1..229 (terms 1..176 by T. D. Noe)
Wikipedia, Highly cototient number

Cf. A063741, A097942, A007374, A101373.

searchMax = 4000; coPhiAnsYldList = Table[0, {searchMax}]; Do[coPhiAns = m - EulerPhi[m]; If[coPhiAns <= searchMax, coPhiAnsYldList[[coPhiAns]]++ ], {m, 1, searchMax^2}]; highlyCototientList = {2}; currHigh = 2; Do[If[coPhiAnsYldList[[n]] > coPhiAnsYldList[[currHigh]], highlyCototientList = {highlyCototientList, n}; currHigh = n], {n, 2, searchMax}]; Flatten[highlyCototientList]

More terms from Robert G. Wilson v, Jan 08 2005

A131934 Records in A014197.

Original entry on oeis.org

2, 3, 4, 5, 6, 10, 11, 17, 21, 31, 34, 37, 38, 49, 54, 72, 98, 126, 129, 176, 178, 247, 276, 281, 331, 359, 399, 441, 454, 525, 558, 692, 718, 734, 764, 1023, 1138, 1485, 1755, 2008, 2166, 2590, 2702, 2733, 3169, 3687, 3802, 4133, 4604, 5025, 5841, 6019, 6311

Offset: 1

N. J. A. Sloane, Nov 05 2007

nonn

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

Cf. A000010, A014197, A097942.

# For the function HighlyTotientNumbers see A097942.
A131934_list := n -> seq(s[2], s = HighlyTotientNumbers(n));
A131934_list(500); # Peter Luschny, Sep 01 2012

# For the function HighlyTotientNumbers see A097942.
A131934_list = lambda n: [s[1] for s in HighlyTotientNumbers(n)]
A131934_list(500) # Peter Luschny, Sep 01 2012

a(n) = A014197(A097942(n)). - R. J. Mathar, Nov 07 2007

More terms from R. J. Mathar, Nov 07 2007
Deleted my csh program which is unstable at high indices - R. J. Mathar, Mar 17 2010
Corrected and extended by T. D. Noe, Mar 16 2010

A361968 Unitary highly totient numbers: numbers k that have more solutions x to the equation uphi(x) = k than any smaller k, where uphi is the unitary totient function (A047994).

Original entry on oeis.org

1, 6, 8, 12, 24, 48, 96, 120, 144, 240, 480, 576, 720, 1440, 2880, 4320, 5760, 8640, 10080, 17280, 20160, 30240, 34560, 40320, 60480, 80640, 120960, 241920, 362880, 483840, 725760, 967680, 1209600, 1451520, 2177280, 2419200, 2903040, 3628800, 4354560, 4838400

Offset: 1

Amiram Eldar, Apr 01 2023

nonn

Indices of records of A361967.

The corresponding numbers of solutions are 2, 3, 4, 5, 8, 11, ... (A361971).

Amiram Eldar, Table of n, a(n) for n = 1..51

The unitary version of A097942.

Cf. A047994, A135347, A347771, A361966, A361967, A361969, A361970, A361971.

solnum[n_] :=  Length[invUPhi[n]]; seq[kmax_] := Module[{s = {}, solmax=0}, Do[sol = solnum[k]; If[sol > solmax, solmax = sol; AppendTo[s, k]], {k, 1, kmax}]; s]; seq[10^5] (* using the function invUPhi from A361966 *)

A105207 Records in A007374.

Original entry on oeis.org

1, 2, 4, 8, 12, 32, 36, 40, 48, 160, 396, 2268, 2560, 3696, 9000, 15936, 17640, 22848, 29160, 38640, 81216, 91872, 153120, 225280, 228960, 410112, 494592, 540672, 619920, 900000, 1111968, 1282176, 1350720, 1932000, 2153088, 4093440, 5634720

Offset: 1

N. J. A. Sloane, Apr 13 2005

nonn

Donovan Johnson, Table of n, a(n) for n = 1..72

Cf. A007374, A105208, A000010, A097942.

More terms from T. D. Noe, Jun 13 2006

A105208 Where records occur in A007374.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 26, 30, 33, 41, 52, 67, 69, 78, 80, 105, 122, 123, 139, 145, 201, 208, 216, 242, 312, 313, 337, 348, 354, 414, 528, 569, 599, 779, 783, 878, 925, 992, 1024, 1103, 1106, 1270, 1283, 1306, 1315, 1508, 1839, 2223

Offset: 1

N. J. A. Sloane, Apr 13 2005

nonn

Donovan Johnson, Table of n, a(n) for n = 1..72

Cf. A007374, A105207, A000010, A097942.

More terms from T. D. Noe, Jun 13 2006.

Corrected and extended by N. J. A. Sloane, Oct 26 2012, at the suggestion of Donovan Johnson.

A362183 Unitary highly cototient numbers: numbers k that have more solutions x to the equation A323410(x) = k than any smaller k.

Original entry on oeis.org

0, 6, 10, 20, 31, 47, 53, 65, 77, 89, 113, 119, 149, 167, 179, 209, 293, 299, 329, 359, 389, 419, 479, 509, 599, 629, 779, 839, 989, 1049, 1139, 1259, 1469, 1559, 1649, 1679, 1889, 2099, 2309, 2729, 3149, 3359, 3569, 3989, 4289, 4409, 4619, 5249, 5459, 6089, 6509

Offset: 1

Amiram Eldar, Apr 10 2023

nonn

Indices of records of A362181.

The corresponding numbers of solutions are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 16, 17, 21, ... (A362184).

Amiram Eldar, Table of n, a(n) for n = 1..96 (terms below 10^5)

Cf. A323410, A362181, A362184.
The unitary version of A100827.
Similar sequences: A097942, A361968.

ucototient[n_] := n - Times @@ (Power @@@ FactorInteger[n] - 1); ucototient[1] = 0; With[{max = 300}, solnum = Table[0, {n, 1, max}]; Do[If[(i = ucototient[k]) <= max, solnum[[i]]++], {k, 2, max^2}]; s = {0}; solmax=1; Do[sol = solnum[[k]]; If[sol > solmax, solmax = sol; AppendTo[s, k]], {k, 2, max}]; s]

cp's OEIS Frontend

A209195 Smallest prime factor of the n-th highly totient number (A097942(n)) plus 1.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A014197 Number of numbers m with Euler phi(m) = n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A007374 Smallest k such that phi(x) = k has exactly n solutions, n>=2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

A036913 Sparsely totient numbers; numbers n such that m > n implies phi(m) > phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A100827 Highly cototient numbers: records for a(n) in A063741.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A131934 Records in A014197.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Sage

Formula

Extensions

A361968 Unitary highly totient numbers: numbers k that have more solutions x to the equation uphi(x) = k than any smaller k, where uphi is the unitary totient function (A047994).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A105207 Records in A007374.

Views