

A003277


Cyclic numbers: n such that n and phi(n) are relatively prime; also n such that there is just one group of order n, i.e., A000001(n) = 1.
(Formerly M0650)


42



1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 33, 35, 37, 41, 43, 47, 51, 53, 59, 61, 65, 67, 69, 71, 73, 77, 79, 83, 85, 87, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 123, 127, 131, 133, 137, 139, 141, 143, 145, 149, 151, 157, 159, 161, 163, 167, 173
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Except for a(2)=2, all the terms in the sequence are odd. This is because of the existence of a noncyclic dihedral group of order 2n for each n>1.  Ahmed Fares (ahmedfares(AT)mydeja.com), May 09 2001
Also GCD(n, A051593(n)) = 1,  Labos Elemer
n such that x^n==1 (mod n) has no solution 2<=x<=n.  Benoit Cloitre, May 10 2002
There is only one group (the cyclic group of order n) whose order is n.  Gerard P. Michon, Jan 08 2008 [This is a 1947 result of Tibor Szele.  Charles R Greathouse IV, Nov 23 2011]
Any divisor of a Carmichael number (A002997) must be odd and cyclic. Conversely, G. P. Michon conjectured (c. 1980) that any odd cyclic number has at least one Carmichael multiple (if the conjecture is true, each of them has infinitely many such multiples). In 2007, Michon & Crump produced explicit Carmichael multiples of all odd cyclic numbers below 10000 (see link, cf. A253595).  Gerard P. Michon, Jan 08 2008
Numbers n such that phi(n)^phi(n) == 1 (mod n).  Michel Lagneau, Nov 18 2012
Contains A000040, and all members of A006094 except 6.  Robert Israel, Jul 08 2015
Number m such that n^n == r (mod m) is solvable for any r.  David W. Wilson, Oct 01 2015


REFERENCES

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.
J. S. Rose, A Course on Group Theory, Camb. Univ. Press, 1978, see p. 7.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000
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].
Max Alekseyev, Michon's conjecture (Open Problem Garden, Aug. 2007).
P. J. Dukes, J. Niezen, Pairwise balanced designs of dimension three, Australasian Journal Of Combinatorics, Volume 61(1) (2015), pages 98113.
Paul Erdős, Some asymptotic formulas in number theory, J. Indian Math. Soc. (N.S.) 12 (1948), pp. 7578.
J. M. Grau, A. M. OllerMarcen, M. Rodríguez, D. Sadornil, Fermat test with gaussian base and Gaussian pseudoprimes, arXiv preprint arXiv:1401.4708 [math.NT], 2014.
Gerard P. Michon, Carmichael Divisors
G. P. Michon and J. K. Crump, Carmichael Multiples of Odd Cyclic Numbers (up to 10000)
J. Pakianathan and K. Shankar, Nilpotent Numbers, Amer. Math. Monthly, 107, AugustSeptember 2000, 631634.
Index entries for sequences related to groups


FORMULA

n = p_1*p_2*...*p_k (for some k >= 0), where the p_i are distinct primes and no p_j1 is divisible by any p_i.
Erdős proved that a(n) ~ e^gamma n log log log n, where e^gamma is A073004.  Charles R Greathouse IV, Nov 23 2011
A000005(a(n)) = 2^k.  Carlos Eduardo Olivieri, Jul 07 2015


MAPLE

select(t > igcd(t, numtheory:phi(t))=1, [$1..1000]); # Robert Israel, Jul 08 2015


MATHEMATICA

Select[Range[175], GCD[#, EulerPhi[#]] == 1 &] (* JeanFrançois Alcover, Apr 04 2011 *)


PROG

(PARI) isA003277(n) = gcd(n, eulerphi(n))==1 \\ Michael B. Porter, Feb 21 2010
(Haskell)
import Data.List (elemIndices)
a003277 n = a003277_list !! (n1)
a003277_list = map (+ 1) $ elemIndices 1 a009195_list
 Reinhard Zumkeller, Feb 27 2012
(MAGMA) [n: n in [1..200]  Gcd(n, EulerPhi(n)) eq 1]; // Vincenzo Librandi, Jul 09 2015


CROSSREFS

Subsequence of A051532.
Cf. A000010, A009195, A050384 (the same sequence but with the primes removed). Also A000001(n) = 1.
Cf. A002997, A006094, A054395, A055561, A054396, A054397, A135850, A249550, A249551, A249552, A249553, A249554, A249555, A036537, A051593, A253595.
Sequence in context: A072697 A102553 A069161 * A117287 A121615 A097605
Adjacent sequences: A003274 A003275 A003276 * A003278 A003279 A003280


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane and Richard Stanley


EXTENSIONS

More terms from Christian G. Bower


STATUS

approved



