A066674 -id:A066674 - cp's OEIS frontend

A125878 Duplicate of A066674.

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

Artur Jasinski, Dec 13 2006

dead

Original name was: a(n) = the least number k such that cos(2pi/k) is an algebraic number of a prime(n)-smooth degree, but not prime(n-1)-smooth.
Comments from N. J. A. Sloane, Jan 07 2013: (Start)
This is a duplicate of A066674. This follows from the following argument. The degree of the minimal polynomial of cos(2*Pi/k) is phi(k)/2, where phi is Euler's totient function. Then a(n) is the least number k such that prime(n) is the largest prime dividing phi(k) and prime(n-1) does not divide phi(k)/2. For the rest of the proof see Bjorn Poonen's remarks in A066674.
It also seems likely that this is the same as A035095, but this is an open problem.
Conjecture: this sequence contains only primes (this would follow if this is indeed the same as A035095).
(End)

See A181877.

Cf. A066674, A035095, A125866-A125877.

Edited by Don Reble, Apr 24 2007

Minor edits by Ray Chandler, Oct 20 2011

A066675 a(n) = A066674(n)-1 divided by the n-th prime.

Original entry on oeis.org

1, 2, 2, 4, 2, 4, 6, 10, 2, 2, 10, 4, 2, 4, 6, 2, 12, 6, 4, 8, 4, 4, 2, 2, 4, 6, 6, 6, 10, 2, 4, 2, 6, 4, 8, 6, 10, 4, 14, 2, 2, 6, 2, 4, 18, 4, 10, 12, 24, 12, 2, 2, 6, 2, 6, 6, 8, 6, 4, 2, 6, 2, 4, 6, 6, 26, 6, 10, 6, 10, 14, 2, 6, 4, 12, 12, 24, 6, 8, 4, 2, 10, 2, 4, 10, 2, 8, 30, 6, 12, 6, 8, 4

Offset: 1

Labos Elemer, Dec 19 2001

nonn

Is this a duplicate of A035096? - R. J. Mathar, Dec 15 2008

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

Cf. A000010, A000040, A035096, A066674, A066675, A066676, A066677, A066678.

a(n) = min{m : phi(m) == 0 (mod p(n))} = min{m : A000010(m) == 0 (mod A000040(n))}.

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

A125879 Records in A066674.

Original entry on oeis.org

3, 7, 11, 29, 53, 103, 191, 311, 709, 1091, 1193, 1571, 2339, 3547, 5449, 8243, 9337, 13711, 16673, 18899, 25367, 37217, 62207, 74441, 87869, 94439, 94789, 96353, 114013, 229981, 397253, 424769, 432781, 496747, 542599, 583397, 673451, 733009, 869563, 874151

Offset: 1

Artur Jasinski, Dec 13 2006

nonn

Ray Chandler, Table of n, a(n) for n = 1..110

Cf. A066674.

a(9)-a(40) from Ray Chandler, Oct 20 2011

A198034 Positions of records in A066674.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 11, 17, 29, 35, 37, 39, 45, 49, 66, 77, 88, 98, 149, 191, 192, 259, 284, 302, 310, 382, 432, 448, 532, 694, 856, 922, 1140, 1539, 1576, 1597, 1783, 1875, 2011, 2130, 2250, 2910, 3256, 3407, 3818, 3940, 4440, 4751, 4855, 4878, 5566, 5588

Offset: 1

Ray Chandler, Oct 20 2011

nonn

Ray Chandler, Table of n, a(n) for n = 1..110

Cf. A066674, A125879.

A035095 Smallest prime congruent to 1 (mod prime(n)).

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

nonn

This is a version of the "least prime in special arithmetic progressions" problem.
Smallest numbers m such that largest prime factor of Phi(m) = prime(n), the n-th prime, also seems to be prime and identical to n-th term of A035095. See A068211, A068212, A065966: Min[x : A068211(x)=prime(n)] = A035095(n); e.g., Phi(a(7)) = Phi(103) = 2*3*17, of which 17 = p(7) is the largest prime factor, arising first here.
It appears that A035095, A066674, A125878 are probably all the same, but see the comments in A066674. - N. J. A. Sloane, Jan 05 2013
Minimum of the smallest prime factors of F(n,i) = (i^prime(n)-1)/(i-1), when i runs through all integers in [2, prime(n)]. Every prime factor of F(n,i) is congruent to 1 modulo prime(n). - Vladimir Shevelev, Nov 26 2014
Conjecture: a(n) is the smallest prime p such that gpf(p-1) = prime(n). See A023503. - Thomas Ordowski, Aug 06 2017
For n>1, a(n) is the smallest prime congruent to 1 mod (2*prime(n)). - Chai Wah Wu, Apr 28 2025

			a(8) = 191 because in the prime(8)k+1 = 19k+1 sequence, 191 is the smallest prime.

E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd 1 (reprinted Chelsea 1953).
E. C. Titchmarsh, A divisor problem, Renc. Circ. Math. Palermo, 54 (1930) pp. 414-429.
P. Turan, Über Primzahlen der arithmetischen Progression, Acta Sci. Math. (Szeged), 8 (1936/37) pp. 226-235.

T. D. Noe, Table of n, a(n) for n = 1..10000
P. Erdős, On some application of Brun's method, Acta Sci. Math (Szeged), v. 13, 1949, pp. 57-63.
A. Granville and C. Pomerance, On the least prime in certain arithmetic progressions
A. Granville and C. Pomerance, On the least prime in certain arithmetic progressions J. Lond Math Soc s2-41 (2) (1990), pp. 193-200.
D. R. Heath-Brown, almost-primes in arithmetic progressions in short intervals, Math Proc Cambr. Phil Soc v 83 (1978), pp. 357-375.
D. R. Heath-Brown, Siegel zeros and the least prime in arithmetic progression, Quart. J. of Math 41 (49) (1990), pp. 405-418.
H.-J. Kanold, Uber Primzahlen in arithmetischen Folgen, Math. Ann. v 156 (1964) pp. 393-395.
U. V. Linnik, On the least prime in an arithmetic progression. I. The basic theorem, Rec. Math (N.S.) v 15 (57) (1944), pp 139-178. MR0012111
C. Pomerance, A note on the least prime in an arithmetic progression J. Number Theory 12 (2) (1980), pp. 218-223.
K. Prachar, Uber die kleinste Primzahl in einer arithmetischen Reihe, J Reine Angew Math. 206 (1961) pp. 3-4.
A. Schinzel, Remark on the paper of K. Prachar Uber die kleinste.., J. Reine Angew Math. v 210 (1962) pp. 122-122.
S. S. Wagstaff, Jr., The irregular primes to 125000, Math. Comp., 32 (1978) pp. 583-591.
S. S. Wagstaff, Jr, Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus, Math. Comp., 33 (147) (1979) pp. 1073-1080.
Index entries for sequences related to primes in arithmetic progressions

Cf. A034694, A032448, A006530, A006093, A035096, A000040, A019434, A058383.
Cf. A068211, A068212, A065966, A000010, A070844-A070858, A061092.
Cf. A000040.

a[n_] := Block[{p = Prime[n]}, r = 1 + p; While[ !PrimeQ[r], r += p]; r]; Array[a, 51] (* Jean-François Alcover, Sep 20 2011, after PARI *)
a[n_]:=If[n<2,3,Block[{p=Prime[n]},r=1+2*p;While[!PrimeQ[r],r+=2*p]];r];Array[a,51] (* Zak Seidov, Dec 14 2013 *)

a(n)=local(p,r);p=prime(n);r=1;while(!isprime(r),r+=p);r

{my(N=66); forprime(p=2, , forprime(q=p+1,10^10, if((q-1)%p==0, print1(q,", "); N-=1; break)); if(N==0,break)); } \\ Joerg Arndt, May 27 2016

from itertools import count
from sympy import prime, isprime
def A035095(n): return 3 if n==1 else next(filter(isprime,count((p:=prime(n)<<1)+1,p))) # Chai Wah Wu, Apr 28 2025

According to a long-standing conjecture (see the 1979 Wagstaff reference), a(n) <= prime(n)^2 + 1. This would be sufficient to imply that a(n) is the smallest prime such that greatest prime divisor of a(n)-1 is prime(n), the n-th prime: A006530(a(n)-1) = A000040(n). This in turn would be sufficient to imply that no value occurs twice in this sequence. - Franklin T. Adams-Watters, Jun 18 2010

a(n) = 1 + A035096(n)*A000040(n). - Zak Seidov, Dec 27 2013

Edited by Franklin T. Adams-Watters, Jun 18 2010
Minor edits by N. J. A. Sloane, Jun 27 2010
Edited by N. J. A. Sloane, Jan 05 2013

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

A066678 Totients of the least numbers for which the totient is divisible by n.

Original entry on oeis.org

1, 2, 6, 4, 10, 6, 28, 8, 18, 10, 22, 12, 52, 28, 30, 16, 102, 18, 190, 20, 42, 22, 46, 24, 100, 52, 54, 28, 58, 30, 310, 32, 66, 102, 70, 36, 148, 190, 78, 40, 82, 42, 172, 44, 180, 46, 282, 48, 196, 100, 102, 52, 106, 54, 110, 56, 228, 58, 708, 60, 366, 310, 126, 64

Offset: 1

Labos Elemer, Dec 22 2001

nonn

From Alonso del Arte, Feb 03 2017: (Start)
One of the less obvious consequences of Dirichlet's theorem on primes in arithmetic progression is that this sequence is well-defined for all positive integers.
Suppose n is a nontotient (see A007617). Obviously a(n) != n. Dirichlet's theorem assures us that, if nothing else, there are infinitely many primes of the form nk + 1 for k positive (and in this case, k > 1). Then phi(nk + 1) = nk, suggesting a(n) = nk corresponding to the smallest k.
Of course not all a(n) are 1 less than a prime, such as 8, 20, 24, 54, etc. (End)

			a(23) = 46 because there is no solution to phi(x) = 23 but there are solutions to phi(x) = 46, like x = 47.
a(24) = 24 because there are solutions to phi(x) = 24, such as x = 35.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..5000 from Vincenzo Librandi)

Cf. A000010, A066674, A066675, A066676, A066677, A067005, A061026.

EulerPhi[mulTotientList = ConstantArray[1, 70]; k = 1; While[Length[vac = Rest[Flatten[Position[mulTotientList, 1]]]] > 0, k++; mulTotientList[[Intersection[Divisors[EulerPhi[k]], vac]]] *= k]; mulTotientList] (* Vincenzo Librandi Feb 04 2017 *)
a[n_] := For[k=1, True, k++, If[Divisible[t = EulerPhi[k], n], Return[t]]];
Array[a, 64] (* Jean-François Alcover, Jul 30 2018 *)

list(len) = {my(v = vector(len), c = 0, k = 1, e); while(c < len, e = eulerphi(k); fordiv(e, d, if(d <= len && v[d] == 0, v[d] = e; c++)); k++); v;} \\ Amiram Eldar, Mar 07 2025

def A066678(n):
    s = 1
    while euler_phi(s) % n: s += 1
    return euler_phi(s)
print([A066678(n) for n in (1..64)]) # Peter Luschny, Feb 05 2017

a(n) = A000010(A061026(n)).

A066676 Smallest number m such that phi(m) is a multiple of n-th primorial number, the product of first n primes.

Original entry on oeis.org

3, 7, 31, 211, 2311, 60653, 1023053, 19417793, 446235509, 12939711677, 200560490131, 14841484883609, 608500576478849, 26165522997357677, 1229779567395958169, 65178316970529225209, 3845520700432469775917, 234576762719782814756597, 15716643102168462956621849

Offset: 1

Labos Elemer, Dec 19 2001

nonn

			n = 8: a(8) = 19417793, phi(a(8)) = 19199380 = 2*9699690 = 2*2*3*5*7*11*13*17*19.

Ray Chandler, Table of n, a(n) for n = 1..25

Cf. A000010, A002110, A066674, A066675, A066677, A066678.

nmax = 25;
A066676 = {};
pm = 1;
Do[
  pm *= Prime[n];
  sol = 0;
  If[PrimeQ[pm + 1],
   sol = pm + 1;
   ,
   sd = Select[Divisors[pm/2], # <= Sqrt[pm/2] &];
   Do[
    f1 = sd[[i]];
    f2 = pm/2/f1;
    If[PrimeQ[2 f1 + 1] && PrimeQ[2 f2 + 1],
     sol = (2 f1 + 1)*(2 f2 + 1);
     Break[];
     ];
     , {i, Length[sd], 1, -1}];
   ];
  AppendTo[A066676, sol];
  Print[{n, sol}];
   , {n, nmax}];
A066676 (* Ray Chandler, Oct 21 2011 *)

a(n) = Min{x : A000010(x) mod A002110(n) = 0}.

a(9)-a(11) from Donovan Johnson, Oct 12 2011

a(12)-a(13) upper limits from Donovan Johnson confirmed as next terms, a(14)-a(19) added by Ray Chandler, Oct 21 2011

A067005 Totient of A061026(n) divided by n.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 4, 1, 2, 1, 2, 1, 4, 2, 2, 1, 6, 1, 10, 1, 2, 1, 2, 1, 4, 2, 2, 1, 2, 1, 10, 1, 2, 3, 2, 1, 4, 5, 2, 1, 2, 1, 4, 1, 4, 1, 6, 1, 4, 2, 2, 1, 2, 1, 2, 1, 4, 1, 12, 1, 6, 5, 2, 1, 2, 1, 4, 2, 2, 1, 8, 1, 4, 2, 2, 3, 6, 1, 4, 1, 2, 1, 2, 1, 12, 2, 4, 1, 2, 2, 6, 1, 4, 3, 2, 1, 4, 2, 2, 1

Offset: 1

Labos Elemer, Dec 22 2001

nonn

			n = 24: a(24) = 1 = phi(A061026(24))/24 = phi(35)/24 = 24/24;
n = 85: a(85) = 12 = phi(A061026(85))/85 = 1020/85.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Zak Seidov)

Cf. A000010, A061026, A066674, A066675, A066676, A066677, A066678.

Table[m = 1; While[! Divisible[Set[k, EulerPhi@ m], n], m++]; k/n, {n, 100}] (* Michael De Vlieger, Mar 18 2017 *)

for(n=1,100, s=1; while((e=eulerphi(s))%n>0, s++); print1(e/n ", ")); \\ Zak Seidov, Feb 22 2014

list(len) = {my(v = vector(len), c = 0, k = 1, e); while(c < len, e = eulerphi(k); fordiv(e, d, if(d <= len && v[d] == 0, v[d] = e/d; c++)); k++); v; } \\ Amiram Eldar, Mar 08 2025

from sympy.ntheory import totient
def k(n):
    m=1
    while totient(m)%n: m+=1
    return m
print([totient(k(n))//n for n in range(1, 101)]) # Indranil Ghosh, Mar 18 2017

a(n) = A000010(A061026(n))/n.

a(n) = A066678(n)/n. - Amiram Eldar, Mar 08 2025

A277915 A(n,k) is the n-th number m such that a nontrivial prime(k)-th root of unity modulo m exists; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Original entry on oeis.org

8, 7, 12, 11, 9, 15, 29, 22, 13, 16, 23, 43, 25, 14, 20, 53, 46, 49, 31, 18, 21, 103, 79, 67, 58, 33, 19, 24, 191, 137, 106, 69, 71, 41, 21, 28, 47, 229, 206, 131, 89, 86, 44, 26, 30, 59, 94, 361, 239, 157, 92, 87, 50, 27, 32, 311, 118, 139, 382, 274, 158, 115, 98, 55, 28, 33

Offset: 1

Alois P. Heinz, Nov 03 2016

The trivial square roots of unity modulo m are {1, m-1} and for an odd prime p the trivial p-th root of unity modulo m is 1.
There is no prime in the first column.
Column k>1 contains prime(k)^2.

			Square array A(n,k) begins:
:  8,  7, 11, 29,  23,  53, 103, 191, ...
: 12,  9, 22, 43,  46,  79, 137, 229, ...
: 15, 13, 25, 49,  67, 106, 206, 361, ...
: 16, 14, 31, 58,  69, 131, 239, 382, ...
: 20, 18, 33, 71,  89, 157, 274, 419, ...
: 21, 19, 41, 86,  92, 158, 289, 457, ...
: 24, 21, 44, 87, 115, 159, 307, 458, ...
: 28, 26, 50, 98, 121, 169, 309, 571, ...

Alois P. Heinz, Antidiagonals n = 1..200, flattened
Wikipedia, Root of unity modulo n

Columns k=1-4 give: A033949, A066498, A066500, A066502.
Row n=1 gives A066674 for k>1.
Main diagonal gives A305828.
Cf. A000010, A000040, A002322.

with(numtheory):
A:= proc() local j, l; l:= proc() [] end;
      proc(n, k)
        while nops(l(k)) lambda(j) or k>1 and
                  irem(phi(j), ithprime(k))=0 then
                  l(k):= [l(k)[], j]; break fi
          od
        od: l(k)[n]
      end
    end():
seq(seq(A(n, 1+d-n), n=1..d), d=1..15);

A[n_, k_] := Module[{j, l = {}}, While[Length[l]CarmichaelLambda[j] || k>1 && Mod[EulerPhi[j], Prime[k]]==0, AppendTo[l, j]; Break[]]]]; l[[n]]];
Table[A[n, 1 + d - n], {d, 1, 15}, {n, 1, d}] // Flatten (* Jean-François Alcover, May 29 2018, from Maple *)

cp's OEIS Frontend

A125878 Duplicate of A066674.

Views

Author

Keywords

Comments

References

Crossrefs

Extensions

A066675 a(n) = A066674(n)-1 divided by the n-th prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A125879 Records in A066674.

Views

Author

Keywords

Links

Crossrefs

Extensions

A198034 Positions of records in A066674.

Views

Author

Keywords

Links

Crossrefs

A035095 Smallest prime congruent to 1 (mod prime(n)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

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

PARI

Python

Formula

A066678 Totients of the least numbers for which the totient is divisible by n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A066676 Smallest number m such that phi(m) is a multiple of n-th primorial number, the product of first n primes.

Views

Author

Keywords

Examples

Links

Crossrefs