A000010 -id:A000010 - cp's OEIS frontend

A366716 a(n) = phi(12^n+1), where phi is Euler's totient function (A000010).

1, 12, 112, 1296, 20416, 229680, 2306304, 32916240, 400515072, 3863116800, 47825825600, 685853880624, 8732596764672, 97509650382144, 990242755633152, 11148606564480000, 184883057981234176, 2047145911595946000, 20281543142263603200, 294779525244632305920

Offset: 0

Sean A. Irvine, Oct 17 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 0..306

Cf. A178248, A000010, A366711, A366712, A366713, A366714, A366715, A366719, A366720, A366690.

EulerPhi[12^Range[0,19] + 1] (* Paul F. Marrero Romero, Oct 27 2023 *)

PARI
```
{a(n) = eulerphi(12^n+1)}
```

a(n) = A000010(A178248(n)). - Paul F. Marrero Romero, Oct 27 2023

A369291 Array read by antidiagonals: T(n,k) = phi(k^n-1)/n, where phi is Euler's totient function (A000010), n >= 1, k >= 2.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 4, 4, 2, 4, 4, 12, 8, 6, 2, 12, 20, 32, 22, 6, 6, 8, 56, 48, 120, 48, 18, 4, 18, 36, 216, 280, 288, 156, 16, 6, 16, 144, 160, 1240, 720, 1512, 320, 48, 4, 30, 96, 432, 1120, 5040, 5580, 4096, 1008, 60, 10, 16, 216, 640, 5400, 6048, 31992, 14976, 15552, 2640, 176

Offset: 1

Andrew Howroyd, Jan 28 2024

For k a prime power, T(n,k) is the number of primitive polynomials of degree n over GF(k). See A011260, A027385 for additional information.

			Array begins:
n\k|  2   3    4     5      6      7      8       9 ...
---+---------------------------------------------------
 1 |  1   1    2     2      4      2      6       4 ...
 2 |  1   2    4     4     12      8     18      16 ...
 3 |  2   4   12    20     56     36    144      96 ...
 4 |  2   8   32    48    216    160    432     640 ...
 5 |  6  22  120   280   1240   1120   5400    5280 ...
 6 |  6  48  288   720   5040   6048  23328   27648 ...
 7 | 18 156 1512  5580  31992  37856 254016  340704 ...
 8 | 16 320 4096 14976 139968 192000 829440 1966080 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)
Eric Weisstein's World of Mathematics, Totient Function.
Wikipedia, Euler's totient function.

Rows n=1..3 and 5 are A000010(k-1), A319210, A319213, A319214.
Columns 2..11 are A011260, A027385, A027695, A027741, A295496, A027743, A027744, A027745, A295497, A319166.
Cf. A319183.

A369291[n_, k_] := EulerPhi[k^n - 1]/n;
Table[A369291[k, n-k+2], {n, 15}, {k, n}] (* Paolo Xausa, Jun 17 2024 *)

PARI
```
T(n,k) = eulerphi(k^n-1)/n
```

A112954 Number of numbers m such that phi(m) = n*tau(m), with phi=A000010 and tau=A000005.

Original entry on oeis.org

7, 9, 10, 9, 7, 17, 4, 17, 14, 15, 7, 19, 2, 16, 20, 21, 0, 29, 0, 29, 9, 13, 7, 32, 7, 11, 23, 21, 7, 39, 0, 19, 17, 4, 11, 44, 2, 0, 11, 41, 7, 24, 2, 19, 30, 11, 0, 55, 4, 23, 7, 21, 7, 46, 9, 27, 4, 11, 0, 61, 0, 0, 27, 29, 9, 30, 2, 10, 19, 31, 0, 57, 2, 9, 27, 4, 4, 30, 2, 50, 29, 9

Offset: 1

Reinhard Zumkeller, Oct 07 2005

nonn

Enrique Pérez Herrero, Table of n, a(n) for n = 1..5000

Cf. A020491, A020488, A062516, A063469, A063470, A112955, A175667.

More terms from Max Alekseyev, Mar 01 2010

A132191 Square array a(m,n) read by antidiagonals, defined by A000010(n)*a(m,n) = Sum_{k=1..n, gcd(k,n)=1} m^{ Sum_{d|n} A000010(d)/ (multiplicative order of k modulo d) }.

Original entry on oeis.org

1, 1, 2, 1, 4, 3, 1, 6, 9, 4, 1, 12, 18, 16, 5, 1, 12, 54, 40, 25, 6, 1, 40, 72, 160, 75, 36, 7, 1, 28, 405, 280, 375, 126, 49, 8, 1, 96, 390, 2176, 825, 756, 196, 64, 9, 1, 104, 1944, 2800, 8125, 2016, 1372, 288, 81, 10, 1, 280, 3411, 17920, 13175, 23976, 4312, 2304, 405

Offset: 1

N. J. A. Sloane, Dec 01 2007, based on email from Max Alekseyev, Nov 08 2007

From Andrew Howroyd, Apr 22 2017: (Start)
Number of step shifted (decimated) sequences of length n using a maximum of m different symbols. See A056371 for an explanation of step shifts. -
Number of mappings with domain {0..n-1} and codomain {1..m} up to equivalence.  Mappings A and B are equivalent if there is a d, prime to n, such that A(i) = B(i*d mod n) for i in {0..n-1}. (End)

			Array begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
2, 4, 6, 12, 12, 40, 28, 96, 104, 280, 216, 1248, 704, 2800, 4344, 8928, 8232, 44224, 29204, 136032, ...
3, 9, 18, 54, 72, 405, 390, 1944, 3411, 14985, 17802, 139968, 133104, 798525, 1804518, 5454378, 8072532, 64599849, 64573626, 437732424, ...
4, 16, 40, 160, 280, 2176, 2800, 17920, 44224, 263296, 419872, 4280320, 5594000, 44751616, 134391040, 539054080, 1073758360, 11453771776, 15271054960, 137575813120, ...
5, 25, 75, 375, 825, 8125, 13175, 103125, 327125, 2445625, 4884435, 61640625, 101732425, 1017323125, 3816215625, 19104609375, 47683838325, 635787765625, 1059638680675, 11924780390625, ...

Vincenzo Librandi, Table of n, a(n) for n = 1..1830
Max Alekseyev, First 20 rows and columns of table
R. C. Titsworth, Equivalence classes of periodic sequences, Illinois J. Math., 8 (1964), 266-270.

Row m=2 is A056371
Row m=3 is A056372
Row m=4 is A056373
Row m=5 is A056374
Row m=6 is A056375
Column n=2 is A000290
Column n=3 is A002411
Column n=4 is A019582
Cf. A285522, A285548.

a[m_, n_] := (1/EulerPhi[n])*Sum[If[GCD[k, n]==1, m^DivisorSum[n, EulerPhi[#] / MultiplicativeOrder[k, #]&], 0], {k, 1, n}]; Table[a[m-n+1, n], {m, 1, 15}, {n, m, 1, -1}] // Flatten (* Jean-François Alcover, Dec 01 2015 *)

for(i=1,15,for(m=1,i,n=i-m+1; print1(sum(k=1, n, if(gcd(k,n)==1, m^sumdiv(n,d,eulerphi(d)/znorder(Mod(k,d))),0))/eulerphi(n)","))) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Apr 26 2008

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Apr 26 2008

Offset corrected by Andrew Howroyd, Apr 20 2017

A295500 a(n) = phi(3^n-1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

1, 4, 12, 32, 110, 288, 1092, 2560, 9072, 26400, 84700, 165888, 797160, 2384928, 6019200, 15728640, 64533700, 141087744, 580765248, 1246080000, 4823425152, 14758128000, 46070066188, 85996339200, 385087175000, 1270928131200, 3474144608256, 8810420097024

Offset: 1

Seiichi Manyama, Nov 22 2017

nonn

Max Alekseyev, Table of n, a(n) for n = 1..690
Eric Weisstein's World of Mathematics, Totient Function
Wikipedia, Euler's totient function

Cf. A000010, A024023, A027385.

phi(k^n-1): A053287 (k=2), this sequence (k=3), A295501 (k=4), A295502 (k=5), A366623 (k=6), A366635 (k=7), A366654 (k=8), A366663 (k=9), A295503 (k=10), A366685 (k=11), A366711 (k=12).

EulerPhi[3^Range[30] - 1] (* Paolo Xausa, Jun 18 2024 *)

PARI
```
{a(n) = eulerphi(3^n-1)}
```

a(n) = n*A027385(n).

a(n) = A000010(A024023(n)). - Michel Marcus, Jun 18 2024

A366690 a(n) = phi(11^n+1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

1, 4, 60, 432, 7320, 53680, 803520, 6495720, 100874752, 764738496, 12756110400, 89493288192, 1568774615040, 11278053084480, 180228847518720, 1310982643872000, 22974417331646464, 168479281019744640, 2521788545778163200, 20190830281379049600

Offset: 0

Sean A. Irvine, Oct 16 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 0..325

Cf. A034524, A000010, A062308, A366685, A366686, A366687, A366689, A366689, A366716.

EulerPhi[11^Range[0,19] + 1] (* Paul F. Marrero Romero, Nov 10 2023 *)

PARI
```
{a(n) = eulerphi(11^n+1)}
```

a(n) = A000010(A034524(n)). - Paul F. Marrero Romero, Nov 10 2023

A366711 a(n) = phi(12^n-1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

10, 120, 1560, 13440, 226200, 2021760, 32518360, 274391040, 4534807680, 51953616000, 646094232960, 4662793175040, 97266341877120, 1070382142166400, 13666309113600000, 109897747141754880, 2016918439151095000, 17518491733377024000, 290436363064202660760

Offset: 1

Sean A. Irvine, Oct 17 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 1..310

phi(k^n-1): A053287 (k=2), A295500 (k=3), A295501 (k=4), A295502 (k=5), A366623 (k=6), A366635 (k=7), A366654 (k=8), A366663 (k=9), A295503 (k=10), A366685 (k=11), this sequence (k=12).

Cf. A000010, A024140, A366707, A366708, A366709, A366710, A366717, A366718.

Mathematica
```
EulerPhi[12^Range[30] - 1]
```
PARI
```
{a(n) = eulerphi(12^n-1)}
```

A061026 Smallest number m such that phi(m) is divisible by n, where phi = Euler totient function A000010.

Original entry on oeis.org

1, 3, 7, 5, 11, 7, 29, 15, 19, 11, 23, 13, 53, 29, 31, 17, 103, 19, 191, 25, 43, 23, 47, 35, 101, 53, 81, 29, 59, 31, 311, 51, 67, 103, 71, 37, 149, 191, 79, 41, 83, 43, 173, 69, 181, 47, 283, 65, 197, 101, 103, 53, 107, 81, 121, 87, 229, 59, 709, 61, 367, 311, 127, 85

Offset: 1

Melvin J. Knight (knightmj(AT)juno.com), May 25 2001

nonn

Conjecture: a(n) is odd for all n. Verified up to n <= 3*10^5. - Jianing Song, Feb 21 2021

The conjecture above is false because a(16842752) = 33817088; see A002181 and A143510. - Flávio V. Fernandes, Oct 08 2023

			a(48) = 65 because phi(65) = phi(5)*phi(13) = 4*12 = 48 and no smaller integer m has phi(m) divisible by 48.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Ho-joo Lee and Gerald Myerson, Consecutive Integers Whose Totients Are Multiples of n: 10837, The American Mathematical Monthly, Vol. 110, No. 2 (Feb., 2003), pp. 158-159.
Pieter Moree and Hans Roskam, On an arithmetical function related to Euler's totient and the discriminator, Fib. Quart., Vol. 33, No. 4 (1995), pp. 332-340.
József Sándor, On the Euler minimum and maximum functions, Notes on Number Theory and Discrete Mathematics, Volume 15, 2009, Number 3, pp. 1-8.

Cf. A000010, A066674, A066675, A066676, A066678, A067005.
Cf. A233516, A233517 (records).
Cf. A005179 (analog for number of divisors), A070982 (analog for sum of divisors).

a = ConstantArray[1, 64]; k = 1; While[Length[vac = Rest[Flatten[Position[a, 1]]]] > 0, k++; a[[Intersection[Divisors[EulerPhi[k]], vac]]] *= k]; a  (* Ivan Neretin, May 15 2015 *)

a(n) = my(s=1); while(eulerphi(s)%n, s++); s;
vector(100, n, a(n))

from sympy import totient as phi
def a(n):
  k = 1
  while phi(k)%n != 0: k += 1
  return k
print([a(n) for n in range(1, 65)]) # Michael S. Branicky, Feb 21 2021

Sequence is unbounded; a(n) <= n^2 since phi(n^2) is always divisible by n.
If n+1 is prime then a(n) = n+1.
a(n) = min{ k : phi(k) == 0 (mod n) }.
a(n) = a(2n) for odd n > 1. - Jianing Song, Feb 21 2021

A066674 Least number m such that phi(m) = A000010(m) is divisible by the n-th prime.

Original entry on oeis.org

3, 7, 11, 29, 23, 53, 103, 191, 47, 59, 311, 149, 83, 173, 283, 107, 709, 367, 269, 569, 293, 317, 167, 179, 389, 607, 619, 643, 1091, 227, 509, 263, 823, 557, 1193, 907, 1571, 653, 2339, 347, 359, 1087, 383, 773, 3547, 797, 2111, 2677, 5449, 2749, 467

Offset: 1

Labos Elemer, Dec 19 2001

nonn

All terms seem to be primes of the form a(n) = k*prime(n)+1 for some k.
Is this a duplicate of A035095? - R. J. Mathar, Dec 13 2008
For the first 5*10^6 terms, a(n) = A035095(n). - Donovan Johnson, Oct 21 2011
Comments on the relationship between A035095, A066674, A125878, added by N. J. A. Sloane, Jan 07 2013: (Start)
Let a(n) = A066674(n), b(n) = A035095(n), c(n) = A125878(n).
It is immediate from the definitions that a(n) <= b(n) and a(n) <= c(n).
Bjorn Poonen (Jan 06 2013) makes the following observations:
1) A prime p divides phi(m) if and only if p^2 | m or p | q-1 for some prime q | m. Thus the smallest m for p is either p^2 or the smallest prime q = 1 (mod p). In other words, a(n) = min(b(n),p(n)^2).
2) In particular, the m in the definition of a(n) is at most p(n)^2, so phi(m)/p(n) < p(n), so p(n) is the largest prime dividing phi(m), and phi(m)/(2 p(n)) < p(n)/2 < p(n-1), so p(n-1) does not divide phi(m)/2.
Thus c(n) = a(n).
Further comments from Eric Bach, Jan 07 2013: (Start)
As others have pointed out, the possible equivalence of a(n) and b(n) is basically the question of how quickly the least prime q == 1 mod p grows, as a function of p. In particular, if q < p^2, the two sequences are the same.
Here are some remarks connected with this.
1. There are probabilistic arguments suggesting that q = O(p (log p)^2). See Heath-Brown (1978), Wagstaff (1979), Bach and Huelsbergen (1993). Using the sieve of Eratosthenes, I found no exceptions to q < p^2 below p = 1254767. So it seems likely that a(n) and b(n) are the same.
2. If ERH holds, then q = O(p log p)^2, see Heath-Brown (1990), (1992). Explicitly, on the same hypothesis, q < 2(p log p)^2, see Bach and Sorenson (1996).
3. By Linnik's theorem, q = O(p^c) for some c > 0. This is unconditional, but the best known value of c, equal to 5.18 -- see Xylouris (2011) -- is nowhere near 2. Heath-Brown (1992) mentions the conjecture (generalized to Linnik's theorem) that q <= p^2. If true, a(n) and b(n) are identical, since p^2 cannot be 1 mod p. (End)
Don Reble (Jan 07 2013) observes that A074884 and A117673 are related to these questions.
Summary: A066674 and A125878 are the same, and A035095 is probably also the same, but this is an open question.
(End)

E. Bach and J. Shallit, Algorithmic Number Theory, Vol. 1: Efficient Algorithms, MIT Press, Cambridge, MA, 1996.

Robert G. Wilson v, Table of n, a(n) for n = 1..10000
E. Bach and L. Huelsbergen, Statistical evidence for small generating sets, Math. Comp. 61 (1993) 69-82.
E. Bach and J. Sorenson, Explicit bounds for primes in residue classes, Math. Comp. 65, 1996, pp. 1717-1735.
D. R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals, Math. Proc. Cambridge Phil. Soc., 83:357--375, 1978.
D. R. Heath-Brown, Siegel zeros and the least prime in an arithmetic progression, Quart. J. Math. Oxford (2) 41, 1990, 405-418.
D. R. Heath-Brown, Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression, Proc. London Math. Soc. 64(3) (1992), pp. 265-338.
S. S. Wagstaff, Jr, Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus, Math. Comp., 33 (147) (1979) pp. 1073-1080.
T. Xylouris, On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions, Acta Arith. 150 (2011), no. 1, 65-91.

Cf. A000010, A000040, A066675-A066678, A035095.

Cf. also A074884 and A117673.

f[n_] := Block[{m = p = Prime@ n}, While[ Mod[ EulerPhi@ m, p] != 0, m += 2]; m]; f[1] = 3; Array[f, 60] (* Robert G. Wilson v, Dec 27 2014 *)

a(n) = min{m : phi(m) = 0 mod prime(n) = 0}.

a(2) corrected by R. J. Mathar, Dec 13 2008

A179186 Numbers k such that phi(k) = phi(k+4), with Euler's totient function phi = A000010.

Original entry on oeis.org

8, 14, 16, 20, 35, 52, 64, 91, 140, 148, 244, 292, 403, 455, 616, 628, 772, 801, 1011, 1024, 1108, 1144, 1252, 1270, 1295, 1456, 1588, 1684, 1820, 1828, 2030, 2164, 2452, 2623, 2644, 2660, 2692, 2932, 3028, 3216, 3321, 3508, 3988, 4264, 4340, 4372, 4612, 4804, 4852, 4948

Offset: 1

M. F. Hasler, Jan 05 2011

nonn

Is there some k > 5 such that phi(k) = phi(k+3)?
None up to 500000. - Harvey P. Dale, Feb 16 2011
No further solutions to the phi(k) = phi(k+3) problem less than 10^12. On the other hand, this sequence has 267797240 terms under 10^12. - Jud McCranie, Feb 13 2012
No reason is known that would prevent other solutions of phi(k) = phi(k+3), see Graham, Holt, & Pomerance. - Jud McCranie, Jan 03 2013
If a(n) is even then a(n)/2 is in A001494 - see comment at A217139. - Jud McCranie, Dec 31 2012

S. W. Graham, J. J. Holt, and C. Pomerance, "On the solutions to phi(n)=phi(n+k)", Number Theory in Progress, Proc. Intern. Conf. in Honor of 60th Birthday of A. Schinzel, Poland, 1997. Walter de Gruyter, 1999, pp. 867-82.

Jud McCranie, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
F. Firoozbakht, Puzzle 466: phi(n-1)=phi(n)=phi(n+1), in C. Rivera's Primepuzzles.
Kevin Ford, Solutions of phi(n)=phi(n+k) and sigma(n)=sigma(n+k), arXiv:2002.12155 [math.NT], 2020.

Cf. A000010, A001274, A001494, A179187, A007015.

[n: n in [1..5000] | EulerPhi(n) eq EulerPhi(n+4)]; // Vincenzo Librandi, Sep 08 2016

Select[Range[5000],EulerPhi[#]==EulerPhi[#+4]&]  (* Harvey P. Dale, Feb 16 2011 *)
SequencePosition[EulerPhi[Range[5000]],{x_,,,_,x_}][[;;,1]] (* Harvey P. Dale, Sep 12 2024 *)

{op=vector(N=4); for( n=1,1e4,if( op[n%N+1]+0==op[n%N+1]=eulerphi(n),print1(n-N,",")))}

cp's OEIS Frontend

A366716 a(n) = phi(12^n+1), where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A369291 Array read by antidiagonals: T(n,k) = phi(k^n-1)/n, where phi is Euler's totient function (A000010), n >= 1, k >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A112954 Number of numbers m such that phi(m) = n*tau(m), with phi=A000010 and tau=A000005.

Views

Author

Keywords

Links

Crossrefs

Extensions

A132191 Square array a(m,n) read by antidiagonals, defined by A000010(n)*a(m,n) = Sum_{k=1..n, gcd(k,n)=1} m^{ Sum_{d|n} A000010(d)/ (multiplicative order of k modulo d) }.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A295500 a(n) = phi(3^n-1), where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A366690 a(n) = phi(11^n+1), where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A366711 a(n) = phi(12^n-1), where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A061026 Smallest number m such that phi(m) is divisible by n, where phi = Euler totient function A000010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica