values_of_Euler_s_totient_function.py

# Какие значения может принимать функция Эйлера? (По видимости, следующие значения не встречаются никогда: 14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114, 118, 122, 124, 134, 142, 146, 152, 154, 158, 170, 174, 182, 186, 188, 194, 202, 206, 214, 218, 230, 234, 236, 242, 244, 246, 248, 254, 258, 266, 274, 278, 284, 286, 290, 298, 302, 304, 308, 314.)

def gcd(a, b):
    while b > 0:   # The best way to find gcd
        a = a % b
        a, b = b, a
    return(a)

def fi(n):   # Функция Эйлера
    a = 1
    for i in range(2, n):
        if gcd(i, n) == 1:
            a = a + 1
    return(a)

n = 1
b = []   # Список возможных значений функции Эйлера
c = []   # Список невозможных (четных) значений функции Эйлера
print()
while len(b) < 100:
    a = fi(n)
    if a not in b:
        b.append(a)
    print('φ(' + str(n) + ') =', a)
    n = n + 1
for i in range(2, max(b), 2):
    if i not in b:
        c.append(i)
print(f'\nВот какие значения может принимать функция Эйлера φ(n) при n < {n} (всего {len(b)}): \n')
print(sorted(b))
print(f'\nА вот какие не может (всего {len(c)}): \n')
print(sorted(c))
print()