A014197 -id:A014197 - cp's OEIS frontend

A320000 Square array A(n, k) read by descending antidiagonals: A(1, 1) = 2, A(1, k) = 1 for k > 1, and for n > 1, A(n, k) = Sum_{d|n, d>=k} A010051(1+d)*[Sum_{i=0..valuation(n,1+d)} A((n/d)/((1+d)^i), 1+d)].

2, 1, 3, 1, 1, 0, 1, 0, 0, 4, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 4, 1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 0, 1, 0, 5, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0

Offset: 1

Antti Karttunen, Dec 03 2018

This square array gives the values obtained from the recursive PARI-program that M. F. Hasler has provided Oct 05 2009 for A014197, in its two-argument form.

			Array begins as:
n  | k=1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16, ...
---+------------------------------------------------
1  |   2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
2  |   3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
3  |   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
4  |   4, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
5  |   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
6  |   4, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
7  |   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
8  |   5, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
9  |   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
10 |   2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, ...
11 |   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
12 |   6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, ...
13 |   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
14 |   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
15 |   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
16 |   6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

Antti Karttunen, Table of n, a(n) for n = 1..10585; the first 145 antidiagonals of the array

Cf. A014197 (column 1).

Cf. A000010, A322310.

up_to = 120;
A320000sq(n, k) = if(1==n, if(1==k,2,1), sumdiv(n, d, if(d>=k && isprime(d+1), my(p=d+1, q=n/d); sum(i=0, valuation(n, p), A320000sq(q/(p^i), p))))); \\ After M. F. Hasler's code in A014197
A320000list(up_to) = { my(v = vector(up_to), i=0); for(a=1,oo, for(col=1,a, i++; if(i > up_to, return(v)); v[i] = A320000sq(col,(a-(col-1))))); (v); };
v320000 = A320000list(up_to);
A320000(n) = v320000[n];

A322310 a(n) = Product_{d|n, d+1 is prime} A008578(1+[Sum_{i=0..A286561(n,1+d)} A320000((n/d)/((1+d)^i), 1+d)]). Here A286561(n,k) gives the k-valuation of n (for k > 1).

Original entry on oeis.org

3, 6, 1, 10, 1, 12, 1, 14, 1, 4, 1, 28, 1, 1, 1, 22, 1, 12, 1, 20, 1, 4, 1, 102, 1, 1, 1, 4, 1, 4, 1, 26, 1, 1, 1, 66, 1, 1, 1, 104, 1, 12, 1, 6, 1, 4, 1, 92, 1, 1, 1, 4, 1, 4, 1, 6, 1, 4, 1, 132, 1, 1, 1, 34, 1, 4, 1, 1, 1, 4, 1, 1240, 1, 1, 1, 1, 1, 4, 1, 57, 1, 4, 1, 21, 1, 1, 1, 28, 1, 1, 1, 6, 1, 1, 1, 492, 1, 1, 1, 12, 1, 4, 1, 6, 1

Offset: 1

Antti Karttunen, Dec 03 2018

nonn

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

Cf. A014197, A320000, A322311 (rgs-transform).

Cf. also A322312.

A320000sq(n, k) = if(1==n, if(1==k,2,1), sumdiv(n, d, if(d>=k && isprime(d+1), my(p=d+1, q=n/d); sum(i=0, valuation(n, p), A320000sq(q/(p^i), p))))); \\ From A320000
A322310(n) = if(1==n,3,my(m=1); fordiv(n,d, my(s, p=d+1, q=n/d); if(isprime(p) && (s = sum(i=0,valuation(n, p), A320000sq(q/(p^i),p))), m *= prime(s))); (m));

a(n) = Product_{d|n} A008578(1+[Sum_{i=0..A286561(n,1+d)} A320000((n/d)/((1+d)^i), 1+d)])^A010051(1+d).

For all n, A056239(a(n)) = A014197(n).

A035113 Numbers != 2 (mod 4) listed in order of increasing totient function phi (A000010).

Original entry on oeis.org

1, 3, 4, 5, 8, 12, 7, 9, 15, 16, 20, 24, 11, 13, 21, 28, 36, 17, 32, 40, 48, 60, 19, 27, 25, 33, 44, 23, 35, 39, 45, 52, 56, 72, 84, 29, 31, 51, 64, 68, 80, 96, 120, 37, 57, 63, 76, 108, 41, 55, 75, 88, 100, 132, 43, 49, 69, 92, 47, 65, 104, 105, 112, 140, 144

Offset: 1

N. J. A. Sloane

			phi(1)=1, phi(3)=2, phi(4)=2, phi(5)=4, ...

Dumitru Damian, Table of n, a(n) for n = 1..10000
L. C. Washington, The Main Conjecture and Annihilation of Class Groups, In: Introduction to Cyclotomic Fields, Graduate Texts in Mathematics, vol 83 (1997) Springer, New York, NY.

Cf. A000010, A035114.

Cf. A002181, A002202, A007614, A014197, A016825, A032447, A058277.

from sympy import totient as A000010
def lov(n): return sorted([[A000010(n), n] for n in range(1,n) if n%4 != 2])
print([x[1] for x in lov(200)][:100]) # Dumitru Damian, Feb 01 2022

More terms from James Sellers

a(43) onward corrected by Sean A. Irvine, Sep 26 2020

A035114 Values of phi(n) corresponding to A035113.

Original entry on oeis.org

1, 2, 2, 4, 4, 4, 6, 6, 8, 8, 8, 8, 10, 12, 12, 12, 12, 16, 16, 16, 16, 16, 18, 18, 20, 20, 20, 22, 24, 24, 24, 24, 24, 24, 24, 28, 30, 32, 32, 32, 32, 32, 32, 36, 36, 36, 36, 36, 40, 40, 40, 40, 40, 40, 42, 42, 44, 44, 46, 48, 48, 48, 48, 48, 48, 48, 48, 48

Offset: 1

N. J. A. Sloane

			phi(1)=1, phi(3)=2, phi(4)=2, phi(5)=4, ...

Dumitru Damian, Table of n, a(n) for n = 1..10000
L. C. Washington, The Main Conjecture and Annihilation of Class Groups, In: Introduction to Cyclotomic Fields, Graduate Texts in Mathematics, vol 83 (1997) Springer, New York, NY.

Cf. A000010, A035113.

Cf. A002181, A002202, A007614, A014197, A016825, A032447, A058277.

from sympy import totient as A000010
def lov(n): return sorted([[A000010(n), n] for n in range(1,n) if n%4 != 2])
print([x[0] for x in lov(200)][:100]) # Dumitru Damian, Feb 03 2022

a(n) = A000010(A035113(n)). - Michel Marcus, Feb 07 2022

More terms from James Sellers

a(43) onward corrected by Sean A. Irvine, Sep 26 2020

A063667 Number of solutions of phi(x) = 12n + 2.

Original entry on oeis.org

3, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Labos Elemer, Aug 22 2001

nonn

			In the range n=0..10000, only 18 invphi(12n + 2) sets are nonempty, always with 2 terms. E.g., n = 8034, a(8034) = 2 because 12*8034 + 2 = 96410 and invphi(96410) = {96721,193442}. - Original comment corrected by _Antti Karttunen_, Nov 07 2018
In the range n <= 100000, there are 48 nonzero values. - _Antti Karttunen_, Nov 07 2018

Antti Karttunen, Table of n, a(n) for n = 0..100000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A002202, A005277, A014197, A017545.

with(numtheory): [seq(nops(invphi(2+12*j)),j=0..10000)];

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))))}; \\ From A014197 by M. F. Hasler
A063667(n) = A014197(2+(12*n)); \\ Antti Karttunen, Nov 07 2018

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

a(n) = A014197(A017545(n)). - Antti Karttunen, Nov 07 2018

Term a(0) = 3 prepended by Antti Karttunen, Nov 07 2018

A070243 a(n) = Card{ k, phi(k) <= n }.

Original entry on oeis.org

2, 5, 5, 9, 9, 13, 13, 18, 18, 20, 20, 26, 26, 26, 26, 32, 32, 36, 36, 41, 41, 43, 43, 53, 53, 53, 53, 55, 55, 57, 57, 64, 64, 64, 64, 72, 72, 72, 72, 81, 81, 85, 85, 88, 88, 90, 90, 101, 101, 101, 101, 103, 103, 105, 105, 108, 108, 110, 110, 119, 119, 119, 119, 127, 127

Offset: 1

Benoit Cloitre, May 11 2002

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-118.
Gérald Tenenbaum and Jie Wu, Exercices corrigés de théorie analytique et probabiliste des nombres, Collection SMF, Cours spécialisés, Numero 2, pp. 78-79.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Matteo Caorsi and Sergio Cecotti, Geometric classification of 4d N=2 SCFTs, Journal of High Energy Physics, Vol. 2018 (2018), Article number 138; arXiv preprint, arXiv:1801.04542 [hep-th], 2018.

Partial sums of A014197.

Cf. A000010, A082695.

for(n=1,150,print1(sum(i=1,100*n,if(sign(eulerphi(i)-n)+1,0,1)+if((eulerphi(i)-n),0,1)),","))

list(nmax) = my(s = 0); for(n = 1, nmax, s += invphiNum(n); print1(s, ", ")); \\ Amiram Eldar, Dec 23 2024, using Max Alekseyev's invphi.gp

Limit_{n->oo} a(n)/n = zeta(2)*zeta(3)/zeta(6) = 1.943596436820759205057... = A082695.
From Benoit Cloitre, Apr 12 2003: (Start)
a(n) = Sum_{k=1..n} A014197(k).
a(n) = (zeta(2)*zeta(3)/zeta(6))*n + O(n*exp(-c*sqrt(log(n)))) for a suitable constant c > 0. (End)

A071387 Smallest number k for which the set of solutions to phi(x) = k has 2n-1 entries.

Original entry on oeis.org

0, 2, 8, 32, 40, 48, 396, 704, 72, 216, 144, 1056, 360, 384, 1320, 240, 9000, 7128, 480, 1296, 15936, 3072, 864, 7344, 720, 4992, 2016, 6000, 4752, 3024, 9984, 1920, 7560, 22848, 29160, 3360, 13248, 27720, 9072, 9360, 4032, 4800, 16896, 3840, 9504, 23520, 5040

Offset: 1

Labos Elemer, May 23 2002

nonn

			For n = 7: 2n-1 = 13, a(7) = Min(InvPhi(13)) = Min({396,400,420,552,560,660}) = 396.

Amiram Eldar, Table of n, a(n) for n = 1..1000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (see invphi.gp there).

Cf. A000010 (phi), A014197, A058277, A063512, A071386, A071388, A071389.

a(n) = {if (n==1, return (0)); my(k=1); while(#invphi(k) != 2*n-1, k++); k;} \\ Michel Marcus, May 13 2020

a(n) = Min({x; Card(InvPhi(x)) = 2n-1}); a(1)=0 because of Carmichael conjecture.

a(12)-a(47) from Donovan Johnson, Jul 27 2011

A071388 Numbers k such that the cardinality of the set of solutions to phi(x) = k is a prime.

Original entry on oeis.org

1, 2, 8, 10, 20, 22, 28, 30, 32, 44, 46, 48, 52, 54, 56, 58, 66, 70, 72, 78, 82, 92, 96, 102, 104, 106, 110, 116, 120, 126, 130, 132, 136, 138, 140, 148, 150, 156, 164, 166, 172, 178, 190, 196, 198, 204, 210, 212, 216, 220, 222, 226, 228, 238, 240, 250, 260, 262

Offset: 1

Labos Elemer, May 23 2002

nonn

All terms except 1 are even. - Robert Israel, Mar 29 2020

			InvPhi(48) = {65,104,105,112,130,140,144,156,168,180,210} has 11 terms, so 48 is a term.

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

Cf. A000010, A007366, A007367, A014197, A058277, A060668, A060670, A060674, A063512, A071386-A071389.

filter:= n -> isprime(nops(numtheory:-invphi(n))):
select(filter, [$1..400]); # Robert Israel, Mar 29 2020

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

A071389 Least number m such that cardinality of InvPhi(m) = prime(n).

Original entry on oeis.org

1, 2, 8, 32, 48, 396, 72, 216, 1056, 1320, 240, 480, 15936, 3072, 7344, 2016, 3024, 9984, 22848, 3360, 13248, 9360, 4800, 9504, 9216, 23328, 7680, 53280, 12480, 29376, 91200, 159744, 22464, 228960, 29952, 179200, 47040, 68544, 15840, 20736, 61440

Offset: 1

Labos Elemer, May 23 2002

nonn

			For n = 11: prime(11) = 31, Card(InvPhi(x)) = 31 for {240, 672, ...}; the smallest is 240 = a(11).

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

Cf. A000010, A014197, A058277, A063512, A071386, A071387, A071388.

lista(len) = {my(p = prime(len), v = vector(p, i, -!isprime(i)), c = 0, k = 1, i); while(c < len, i = invphiNum(k); if(i > 0 && i <= p && v[i] == 0, c++; v[i] = k); k++); select(x -> x > 0, v);} \\ Amiram Eldar, Nov 11 2024, using Max Alekseyev's invphi.gp

a(n) = Min{x; Card(InvPhi(x)) = prime(n), n-th prime}

4 more terms from Emeric Deutsch, Jul 25 2005

More terms from Max Alekseyev, Apr 24 2010

A165774 Largest solution to phi(x) = n!, where phi() is Euler totient function (A000010).

Original entry on oeis.org

2, 6, 18, 90, 462, 3150, 22050, 210210, 1891890, 19969950, 219669450, 2847714870, 37020293310, 520843112790, 7959363061650, 135309172048050, 2300255924816850, 41996101027370490, 797925919520039310, 16504589035937252250, 347097774991217099850, 7751850308137181896650, 179602728970220622816750, 4493489228616853106091450, 112337230715421327652286250, 2958213742172761628176871250, 79871771038664563960775523750, 2279417465795734863803670716250

Offset: 1

M. F. Hasler, Oct 04 2009

nonn

All solutions to phi(x) = n! belong to the interval [n!,(n+1)!] and are listed in the n-th row of A165773 (when written as table with row lengths A055506). Thus this sequence gives the last element in these rows, i.e., a(n) = A165773(Sum_{k=1..n} A055506(k)).
All terms in this sequence are even, since if x is an odd solution to phi(x) = n!, then 2x is a larger solution because phi(2x) = phi(2)*phi(x) = phi(x).
Most terms (and any term divisible by 4) are divisible by 3, since if x = 2^k*y is a solution with k>1 and gcd(y,2*3) = 1, then x*3/2 = 2^(k-1)*3*y is a larger solution because phi(2^(k-1)*3) = 2^(k-2)*(3-1) = 2^(k-1) = phi(2^k).
For the same reason, most terms are divisible by 5, since if x=2^k*y is a solution with k>2 and gcd(y,2*5) = 1, then x*5/4 is a larger solution.
Also, any term of the form x = 2^k*3^m*y with k,m>1 must be divisible by 7 (else x*7/6 would be a larger solution), and so on.
Experimentally, a(n) = c(n)*(n+1)! with a coefficient c(n) ~ 2^(-n/10) (e.g., c(1) = c(2) = 1, c(10) ~ 0.5).

			a(1) = 2 is the largest among the A055506(1) = 2 solutions {1,2} to phi(n) = 1! = 1.
a(4) = 90 is the largest among the A055506(4) = 10 solutions {35, 39, 45, 52, 56, 70, 72, 78, 84, 90} to phi(n) = 4! = 24.
See A165773 for more examples.

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).

Cf. A000010, A055487, A055506, A055489, A014197, A165773.

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

Edited and terms a(12)-a(28) added by Max Alekseyev, Jan 26 2012, Jul 09 2014

cp's OEIS Frontend

A320000 Square array A(n, k) read by descending antidiagonals: A(1, 1) = 2, A(1, k) = 1 for k > 1, and for n > 1, A(n, k) = Sum_{d|n, d>=k} A010051(1+d)*[Sum_{i=0..valuation(n,1+d)} A((n/d)/((1+d)^i), 1+d)].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A322310 a(n) = Product_{d|n, d+1 is prime} A008578(1+[Sum_{i=0..A286561(n,1+d)} A320000((n/d)/((1+d)^i), 1+d)]). Here A286561(n,k) gives the k-valuation of n (for k > 1).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A035113 Numbers != 2 (mod 4) listed in order of increasing totient function phi (A000010).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Extensions

A035114 Values of phi(n) corresponding to A035113.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A063667 Number of solutions of phi(x) = 12n + 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

PARI

Formula

Extensions

A070243 a(n) = Card{ k, phi(k) <= n }.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

PARI

Formula

A071387 Smallest number k for which the set of solutions to phi(x) = k has 2n-1 entries.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A071388 Numbers k such that the cardinality of the set of solutions to phi(x) = k is a prime.

Views

Author

Keywords