login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A039769 Composite integers n such that GCD(phi(n),n-1)>1. 5
9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51, 52, 55, 57, 63, 65, 66, 69, 70, 75, 76, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124, 125, 129, 130, 133, 135, 141, 143, 145, 147, 148, 153, 154, 155, 159, 161, 165, 169, 171, 172, 175 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Previous name was: phi(a(n)) and (a(n)-1) have a common factor but are distinct.

Equivalently, numbers n that are Fermat pseudoprimes to some base b, 1 < b < n.  A nonprime number n is a Fermat pseudoprime to base b if b^(n-1) = 1 (mod n). Cf. A181780. - Geoffrey Critzer, Apr 04 2015

A071904, the odd composite numbers, is a subset of this sequence. - Peter Munn, May 15 2017

LINKS

Robert Israel, Table of n, a(n) for n = 1..10000

EXAMPLE

phi(21)=12, gcd(12,20)=4.

MAPLE

select(n -> not isprime(n) and igcd(n-1, numtheory:-phi(n))>1, [$4..1000]);  #Robert Israel, Apr 07 2015

MATHEMATICA

Select[Table[mm = n; {n, Table[Mod[a^(mm - 1), mm], {a, 2, mm - 1}]}, {n,

    Select[Range[250], ! PrimeQ[#] &]}], MemberQ[#[[2]], 1] &][[All, 1]]

(* or *)

Select[Range[250], GCD[EulerPhi[#], # - 1] > 1 && EulerPhi[#] != # - 1 &] (* Geoffrey Critzer, Apr 04 2015 *)

CROSSREFS

Cf. A000010, A071904, A181780.

Sequence in context: A255763 A079364 A160666 * A270574 A071904 A014076

Adjacent sequences:  A039766 A039767 A039768 * A039770 A039771 A039772

KEYWORD

nonn,easy

AUTHOR

Olivier Gérard

EXTENSIONS

Name clarified by Tom Edgar, Apr 05 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 22 08:39 EST 2018. Contains 298042 sequences.