A256241 Numbers n whose Euler's totient function phi(n), divided by two, plus one, p = (phi(n) / 2) + 1, is a divisor of n.

4, 6, 12, 15, 20, 21, 28, 30, 33, 39, 42, 44, 51, 52, 57, 66, 68, 69, 76, 78, 87, 92, 93, 102, 111, 114, 116, 123, 124, 129, 138, 141, 148, 159, 164, 172, 174, 177, 183, 186, 188, 201, 212, 213, 219, 222, 236, 237, 244, 246, 249, 258, 267, 268, 282, 284, 291, 292, 303, 309, 316, 318, 321, 327, 332, 339, 354, 356, 366

Offset: 1

Author

David Morales Marciel, Apr 19 2015

Keywords

• nonn

Comments

p is always a prime factor of n as well.

Except for the case n=6, p is always the greatest prime factor of n.

(n/p) is an upper bound on the rest of the prime factors 'q' of n, so always q <= (n/p).

Examples

			For n = 4, phi(n) = 2, p = (phi(n)/2)+1 = 2, is prime and is a prime factor of 4.
For n = 6, phi(n) = 2, p = (phi(n)/2)+1 = 2, is prime and is a prime factor of 6.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• David Morales Marciel, Euler's Totient function statement proposal

Crossrefs

Cf. A000010.

Programs

Magma

[k:k in [1..370]| IsIntegral(k/(EulerPhi(k)/2+1))]; // Marius A. Burtea, Nov 06 2019

Mathematica

aQ[n_] := Divisible[n, 1 + EulerPhi[n] / 2]; Select[Range[400], aQ] (* Amiram Eldar, Nov 06 2019 *)

PARI

isok(n) = (n % (eulerphi(n)/2+1)) == 0; \\ Michel Marcus, Apr 20 2015

Python

from sympy import totient
[n for n in range(1, 10**5) if n%((totient(n)/2)+1)==0]

Extensions

Removed long Python code, and added very simple Python program (two lines) with sympy as suggested by the Editor.