%I A104016
%S A104016 561,1105,1729,2465,2821,6601,8911,10585,11305,15841,29341,39865,41041,
%T A104016 46657,52633,62745,63973,75361,96985,101101,115921,126217,162401,172081,
%U A104016 188461,252601,278545,294409,314821,334153,340561,399001,401401,410041
%N A104016 Devaraj numbers: squarefree r-prime-factor (r>1) integers N=p1*...*pr 
               such that phi(N)=(p1-1)*...*(pr-1) divides gcd(p1-1,...,pr-1)^2*(N-1)^(r-2).
%C A104016 A. K. Devaraj conjectured that these numbers are exactly Carmichael numbers. 
               It was proved http://www.mersenneforum.org/showpost.php?p=55271 that 
               every Carmichael number is indeed a Devaraj number, but the converse 
               is not true. Devaraj numbers that are not Carmichael are given by 
               A104017.
%C A104016 These numbers can't be even, since phi(N) is always even (N>2) but p1=2 
               implies that gcd{pi-1}=1 and N-1 is odd. [From M. F. Hasler (MHasler(AT)univ-ag.fr), 
               Apr 03 2009]
%o A104016 (PARI) { Devaraj() = for(n=2,10^8, f=factorint(n); if(vecmax(f[,2])>1,
               next); f=f[,1]; r=length(f); if(r==1,next); d=f[1]-1; p=f[1]-1; for(i=2,
               r,d=gcd(d,f[i]-1); p*=f[i]-1); if( ((n-1)^(r-2)*d^2)%p==0, print1(" 
               ",n)) ) }
%o A104016 Contribution from M. F. Hasler (MHasler(AT)univ-ag.fr), Apr 03 2009: 
               (Start)
%o A104016 (PARI) isA104016(n)={ local(f=factor(n)); vecmax(f[,2])==1 & #(f*=[1,
               -1]~)>1 & gcd(f)^2*(n-1)^(#f-2)%prod(i=1,#f,f[i])==0 }
%o A104016 /* To print the list: */ forstep( n=3, 10^6, 2, vecmax((f=factor(n))[,
               2])>1 & next; #(f*=[1,-1]~)>1 | next; gcd(f)^2*(n-1)^(#f-2)%prod(i=1,
               #f,f[i]) | print1(n","))
%o A104016 /* The following version could be efficient for large omega(n) */
%o A104016 isA104016(n) = issquarefree(n) & !isprime(n) & Mod(n-1,prod(i=1,#n=factor(n)*[1,
               -1]~,n[i]))^(#n-2)*gcd(n)^2==0 \\ (End)
%Y A104016 Cf. A104017, A002997.
%Y A104016 Sequence in context: A135721 A047713 A006971 this_sequence A002997 A087788 
               A083733
%Y A104016 Adjacent sequences: A104013 A104014 A104015 this_sequence A104017 A104018 
               A104019
%K A104016 nonn
%O A104016 1,1
%A A104016 Max Alekseyev (maxale(AT)gmail.com), Feb 25 2005