login
Composite numbers whose Euler totient divides the sum of the Euler totients of the numbers less than or equal to n and not relatively prime to n.
3

%I #24 Nov 11 2014 21:05:11

%S 161,171,895,1337,1843,1967,2575,5833,8255,36121,54439,87353,195921,

%T 274115,284419,340363,368449,387087,444639,504539

%N Composite numbers whose Euler totient divides the sum of the Euler totients of the numbers less than or equal to n and not relatively prime to n.

%C No more terms < 10^6.

%e Numbers not coprime to 161 are 7, 14, 21, 23, 28, 35, 42, 46, 49, 56, 63, 69, 70, 77, 84, 91, 92, 98, 105, 112, 115, 119, 126, 133, 138, 140, 147, 154, 161 and the sum of their Euler totients is 1320; phi(161) = 132 and 1320/132 = 10.

%p with(numtheory): P:=proc(q) local a,k,n; for n from 1 to q do

%p if not isprime(n) then a:=0;

%p for k from 1 to n do if gcd(k,n)>1 then a:=a+phi(k); fi; od;

%p if type(a/phi(n),integer) then print(n); fi; fi; od; end: P(10^9);

%o (PARI) isok(n) = (n!=1) && !isprime(n) && (sum(k=1, n-1, if (gcd(k, n) != 1, eulerphi(k), 0)) % eulerphi(n) == 0); \\ _Michel Marcus_, Oct 29 2014

%Y Cf. A000010, A249396.

%K nonn,more

%O 1,1

%A _Paolo P. Lava_, Oct 27 2014

%E a(11)-a(12) from _Michel Marcus_, Nov 01 2014

%E a(13)-a(19) from _Michel Marcus_, Nov 03 2014

%E a(20) from _Ray Chandler_, Nov 04 2014