Задний план

Эйлера totient функция φ(n)определяется как количество целых чисел меньше или равно , nчто взаимно просты с n, то есть, число возможных значений xв 0 < x <= nтечение которого gcd(n, x) == 1. У нас было в несколько totient - родственные проблемы и раньше, но никогда не один , который просто его расчета.

Отображение полной функции на целые числа - OEIS A000010 .

Вызов

Учитывая целое число n > 0, рассчитать φ(n). Вы можете получить ввод через аргументы командной строки, стандартный ввод, аргументы функции или что-либо еще разумное. Вы можете выдавать вывод через стандартный вывод, возвращаемые значения или что-либо еще разумное. Анонимные функции приемлемы. Вы можете предположить, что ввод не будет переполнять ваш естественный метод хранения целых чисел, например, intв C, но вы должны поддерживать ввод до 255. Если ваш язык имеет встроенную функцию totient, вы не можете ее использовать.

Примеры

φ(1) => 1
φ(2) => 1
φ(3) => 2
φ(8) => 4
φ(9) => 6
φ(26) => 12
φ(44) => 20
φ(105) => 48

Кратчайший ответ в байтах побеждает. Если ваш язык использует кодировку, отличную от UTF-8, укажите это в своем ответе.

Mathematica, 27 22 байта

Range@#~GCD~#~Count~1&

Безымянная функция, которая принимает и возвращает целое число.

Здесь не так много объяснений, за исключением того, что @это префиксная нотация для вызовов функций и ~...~(слева-ассоциативная) инфиксная нотация, так что вышеупомянутое - то же самое:

Count[GCD[Range[#], #], 1] &

MATL, 7 байт

t:Zd1=s

Вы можете TryItOnline . Простейшая идея, сделать вектор от 1 до N и взять gcd каждого элемента с N ( Zdделает gcd). Затем найдите, какие элементы равны 1, и суммируйте вектор, чтобы получить ответ.

J, 9 байт

(-~:)&.q:

Это основано на эссе Jsoftware о текущих функциях.

При п = р ₁ ^{е ₁} ∙ р ₂ ^{е ₂} ∙∙∙ р _к ^{е _к} , где р _к является главным фактором п , функция totient ф ( п ) = ф ( р ₁ ^{е ₁} ) ∙ ф ( р ₂ ^{е ₂} ) φ φ ( p _k ^{e _k} ) = ( p ₁ - 1) p ₁ ^{e ₁ - 1} ∙ ( p ₂ - 1) p ₂^{e ₂ - 1} ∙∙∙ ( p _k - 1) p _k ^{e _k - 1} .

использование

   f =: (-~:)&.q:
   (,.f"0) 1 2 3 8 9 26 44 105
  1  1
  2  1
  3  2
  8  4
  9  6
 26 12
 44 20
105 48
   f 12345
6576

объяснение

(-~:)&.q:  Input: integer n
       q:  Prime decomposition. Get the prime factors whose product is n
(   )&     Operate on them
  ~:         Nub-sieve. Create a mask where 1 is the first occurrence
             of a unique value and 0 elsewhere
 -           Subtract elementwise between the prime factors and the mask
     &.q:  Perform the inverse of prime decomposition (Product of the values)

Желе, 4 байта

Rgċ1

Попробуйте онлайн!

объяснение

Rgċ1   Main monadic chain. Argument: z

R      Yield [1 2 3 .. z].
 g     gcd (of each) (with z).
  ċ1   Count the number of occurrences of 1.

Со встроенным

ÆṪ

Попробуйте онлайн!

объяснение

ÆṪ   Main monadic chain. Argument: z

ÆṪ   Totient of z.

Haskell, 28 байт

f n=sum[1|1<-gcd n<$>[1..n]]

Использует сопоставление с образцом констант в Haskell . Уловки здесь довольно стандартны для игры в гольф, но я объясню широкой аудитории.

Выражение gcd n<$>[1..n]отображается gcd nна [1..n]. Другими словами, он вычисляет gcdс nкаждого числа от 1до n:

[gcd n i|i<-[1..n]]

Отсюда желаемым выводом является количество 1записей, но в Haskell отсутствует countфункция. Идиоматический способ filterсохранить только 1букву и взять полученный результат length, который слишком длинен для игры в гольф.

Вместо этого filterимитируется понимание списка [1|1<-l]с результирующим списком l. Обычно, списочные выражения привязывают значения к переменной, как в [x*x|x<-l], но Haskell позволяет сопоставлять шаблон с, в данном случае, константой 1.

Таким образом, [1|1<-l]генерируя 1на каждом совпадении 1, эффективно извлекая только 1из исходного списка. Вызов sumна это дает его длину.

Python 2, 44 байта

f=lambda n,d=1:d/n or-f(d)*(n%d<1)-~f(n,d+1)

Менее гольф:

f=lambda n:n-sum(f(d)for d in range(1,n)if n%d<1)

Используется формула, по которой у коэффициентов Эйлера делителей nесть сумма n:

Затем значение ϕ(n)может быть рекурсивно вычислено как nминус сумма по нетривиальным делителям. По сути, это делает инверсию Мёбиуса на единичной функции. Я использовал тот же метод в гольфе, чтобы вычислить функцию Мёбиуса .

Спасибо Деннису за сохранение 1 байта с лучшим базовым регистром, распространение начального значения +nв +1для каждого из nциклов, сделанного как -~.

Пайк, 5 байт

m.H1/

Попробуй это здесь!

count(map(gcd, range(input)), 1)

Регулярное выражение (ECMAScript), 131 байт

По крайней мере -12 байт благодаря Deadcode (в чате)

(?=((xx+)(?=\2+$)|x+)+)(?=((x*?)(?=\1*$)(?=(\4xx+?)(\5*(?!(xx+)\7+$)\5)?$)(?=((x*)(?=\5\9*$)x)(\8*)$)x*(?=(?=\5$)\1|\5\10)x)+)\10|x

Попробуйте онлайн!

Выход - длина матча.

Регулярные выражения ECMAScript чрезвычайно усложняют подсчет. Любая обратная ссылка, определенная вне цикла, будет постоянной во время цикла, любая обратная ссылка, определенная внутри цикла, будет сброшена при цикле. Таким образом, единственный способ переноса состояния по итерациям цикла - использование текущей позиции совпадения. Это одно целое число, и оно может только уменьшаться (ну, позиция увеличивается, но длина хвоста уменьшается, и это то, что мы можем сделать по математике).

Учитывая эти ограничения, простой подсчет простых чисел кажется невозможным. Вместо этого мы используем формулу Эйлера для вычисления значения.

Вот как это выглядит в псевдокоде:

N = input
Z = largest prime factor of N
P = 0

do:
   P = smallest number > P that’s a prime factor of N
   N = N - (N / P)
while P != Z

return N

В этом есть две сомнительные вещи.

Во-первых, мы не сохраняем входные данные, а только текущий продукт, так как же мы можем получить основные факторы входных данных? Хитрость в том, что (N - (N / P)) имеет те же простые факторы> P, что и N. Он может получить новые простые факторы <P, но мы все равно их игнорируем. Обратите внимание, что это работает только потому, что мы перебираем простые множители от наименьшего к наибольшему, иное движение в обратном направлении завершится неудачей

Во-вторых, мы должны помнить два числа в итерациях цикла (P и N, Z не считается, поскольку он постоянен), и я только что сказал, что это невозможно! К счастью, мы можем объединить эти два числа в одном. Обратите внимание, что в начале цикла N всегда будет кратно Z, а P всегда будет меньше Z. Таким образом, мы можем просто запомнить N + P и извлечь P с помощью модуля.

Вот немного более подробный псевдокод:

N = input
Z = largest prime factor of N

do:
   P = N % Z
   N = N - P
   P = smallest number > P that’s a prime factor of N
   N = N - (N / P) + P
while P != Z

return N - Z

И вот прокомментированное регулярное выражение:

# \1 = largest prime factor of N
# Computed by repeatedly dividing N by its smallest factor
(?= ( (xx+) (?=\2+$) | x+ )+ )

(?=
        # Main loop!
        (
                # \4 = N % \1, N -= \4
                (x*?) (?=\1*$)

                # \5 = next prime factor of N
                (?= (\4xx+?) (\5* (?!(xx+)\7+$) \5)? $ )

                # \8 = N / \5, \9 = \8 - 1, \10 = N - \8
                (?= ((x*) (?=\5\9*$) x) (\8*) $ )

                x*
                (?=
                        # if \5 = \1, break.
                        (?=\5$) \1
                |
                        # else, N = (\5 - 1) + (N - B)
                        \5\10
                )
                x
        )+
) \10

И в качестве бонуса ...

Regex (ECMAScript 2018, количество совпадений), 23 байта

x(?<!^\1*(?=\1*$)(x+x))

Попробуйте онлайн!

Выход - это количество совпадений. В ECMAScript 2018 вводится функция обратной длины переменной (вычисляется справа налево), которая позволяет просто считать все числа, взаимно простые с вводом.

Оказывается, это независимо тот же метод, который используется в решении Retina Лики Нун , и регулярное выражение имеет даже ту же длину ( и взаимозаменяемо ). Я оставляю это здесь, потому что может быть интересно, что этот метод работает в ECMAScript 2018 (а не только .NET).

                        # Implicitly iterate from the input to 0
x                       # Don’t match 0
 (?<!                 ) # Match iff there is no...
                 (x+x)  # integer >= 2...
         (?=\1*$)       # that divides the current number...
     ^\1*               # and also divides the input

J 11 байт

+/@(1=+.)i.

использование

>> f =: +/@(1=+.)i.
>> f 44
<< 20

где >>STDIN и <<STDOUT.

объяснение

+/ @ ( 1 = +. ) i.
               │
   ┌───────────┴┐
 +/@(1=+.)      i.
   │
 ┌─┼──┐
+/ @ 1=+.
    ┌─┼─┐
    1 = +.

>> (i.) 44            NB. generate range
<< 0 1 2 3 4 ... 43
>> (+.i.) 44          NB. calculate gcd of each with input
<< 44 1 2 1 4 ... 1
>> ((1=+.)i.) 44      NB. then test if each is one (1 if yes, 0 if no)
<< 0 1 0 1 0 ... 1
>> (+/@(1=+.)i.) 44   NB. sum of all the tests
<< 20

Python> = 3,5, 76 64 58 байт

Спасибо LeakyNun за отыгрывание 12 (!) Байтов.

Спасибо Sp3000 за удаление 6 байтов.

import math
lambda n:sum(math.gcd(n,x)<2for x in range(n))

Мне нравится, как читаемый Python. Это имеет смысл, даже благодаря игре в гольф.

Perl 6 ,  26 24  22 байта

{[+] (^$^n Xgcd $n) X== 1}
{+grep 2>*,(^$_ Xgcd$_)}
{[+] 2 X>(^$_ Xgcd$_)}

Объяснение:

{
  [+] # reduce using &infix:<+>
    2
    X[>] # crossed compared using &infix:«>»
    (
      ^$_    # up to the input ( excludes input )
      X[gcd] # crossed using &infix:<gcd>
      $_     # the input
    )
}

Пример:

#! /usr/bin/env perl6
use v6.c;

my &φ = {[+] 2 X>(^$_ Xgcd$_)};

say φ(1) # 1
say φ(2) # 1
say φ(3) # 2
say φ(8) # 4
say φ(9) # 6
say φ(26) # 12
say φ(44) # 20
say φ(105) # 48

say φ 12345 # 6576

Юлия, 25 байт

!n=sum(i->gcd(i,n)<2,1:n)

Все просто - sumфункция позволяет дать ей функцию, которую нужно применить перед суммированием - в основном это эквивалент работы mapи затем sum. Это напрямую подсчитывает количество относительно простых чисел меньше, чем n.

Python 2, 57 байт

f=lambda n,k=1,m=1:n*(k>n)or f(n-(n%k<m%k)*n/k,k+1,m*k*k)

Проверьте это на Ideone .

Задний план

По формуле Эйлера ,

где φ обозначает функцию Эйлера, а p изменяется только по простым числам.

Чтобы определить простые числа, мы используем следствие теоремы Вильсона :

Как это работает

Всегда переменная m будет равна квадрату факториала от k - 1 . Фактически мы назвали аргументы по умолчанию k = 1 и m = 0! ² = 1 .

Пока k ≤ n , значение n*(k>n)равно 0 и выполняется следующий код or.

Напомним, что m%kэто даст 1, если m простое число и 0, если нет. Это означает, что x%k<m%kдаст True тогда и только тогда, когда оба k - простое число, а x делится на k .

В этом случае (n%k<m%k)*n/kдает n / k , и вычитая его из n заменяет его предыдущее значение на n (1 - 1 / k) , как в формуле произведения Эйлера. В противном случае (n%k<m%k)*n/kвозвращает 0, а n остается неизменным.

После вычисления вышеупомянутого, мы увеличиваем k и умножаем m на «старое» значение k ² , сохраняя, таким образом, требуемое соотношение между k и m , затем рекурсивно вызываем f с обновленными аргументами.

Как только k превышает n , n*(k>n)вычисляется значение n , которое возвращается функцией.

Рубин, 32 байта

->n{(1..n).count{|i|i.gcd(n)<2}}

лямбда, которая принимает целое число n и возвращает количество равных числу целых чисел в диапазоне (1..n) с n.

Брахилог , 25 байт

:{:1e.$pdL,?$pd:LcCdC}fl.

объяснение

Brachylog еще не имеет встроенной GCD, поэтому мы проверяем, что эти два числа не имеют общих общих факторов.

• Основной предикат:

  :{...}fl.             Find all variables which satisfy predicate 1 when given to it as
                        output and with Input as input.
                        Unify the Output with the length of the resulting list
  

• Предикат 1:

  :1e.                  Unify Output with a number between Input and 1
      $pdL              L is the list of prime factors of Output with no duplicates
          ,
           ?$pd:LcC     C is the concatenation of the list of prime factors of Input with
                        no duplicates and of L
                   dC   C with duplicates removed is still C
  

Pyth, 6 байт

smq1iQ

Попробуйте онлайн!

/iLQQ1

Попробуйте онлайн!

объяснение

smq1iQ     input as Q
smq1iQdQ   implicitly fill variables

 m     Q   for d in [0 1 2 3 .. Q-1]:
    iQd        gcd of Q and d
  q1           equals 1? (1 if yes, 0 if no)
s          sum of the results


/iLQQ1     input as Q

 iLQQ      gcd of each in [0 1 2 3 .. Q-1] with Q
/    1     count the number of occurrences of 1

PowerShell v2 +, 72 байта

param($n)1..$n|%{$a=$_;$b=$n;while($b){$a,$b=$b,($a%$b)};$o+=!($a-1)};$o

В PowerShell нет функции GCD, поэтому мне пришлось свернуть свою собственную.

Это принимает входные данные $n, затем изменяется от и 1до $nи направляет их в цикл |%{...}. Каждая итерация мы устанавливаем два вспомогательных переменных , $aи $bзатем выполнить НОД whileпетлю. Каждая итерация мы проверить , что $bпо - прежнему не равен нулю, а затем сохранить $a%$bдо $bи предыдущее значение , $bчтобы $aдля следующего цикла. Затем мы накапливаем значение $aравно 1в нашей выходной переменной $o. Когда цикл for завершен, мы помещаем его $oв конвейер и вывод неявен.

В качестве примера того, как whileработает цикл, рассмотрим, $n=20и мы находимся $_=8. Первая проверка имеет $b=20, поэтому мы входим в цикл. Сначала мы рассчитываем $a%$bили 8%20 = 8, которое устанавливается $bв то же время, что и 20устанавливается в $a. Проверьте 8=0, и мы входим во вторую итерацию. Затем мы вычисляем 20%8 = 4и устанавливаем это значение $b, затем устанавливаем $aзначение 8. Проверьте 4=0, и мы входим в третью итерацию. Мы вычисляем 8%4 = 0и устанавливаем это значение $b, затем устанавливаем $aзначение 4. Проверьте 0=0и мы выходим из цикла, поэтому GCD (8,20) есть $a = 4. Таким образом, !($a-1) = !(4-1) = !(3) = 0так $o += 0и не считать , что один.

Фактор, 50 байтов

[ dup iota swap '[ _ gcd nip 1 = ] filter length ]

Делает диапазон ( йота ) n и карри n в функцию, которая получает gcd xn для всех значений 0 <= x <= n , проверяет, равен ли результат 1 . Фильтр оригинальный выбор на результат ли GCD хп был 1 , и взять его длину .

Japt -mx, 7 5 байт

yN ¥1

Запустите его онлайн

-2 байта благодаря Shaggy

Retina, 36 29 байт

7 байтов благодаря Мартину Эндеру.

.+
$*
(?!(11+)\1*$(?<=^\1+)).

Попробуйте онлайн!

объяснение

Есть два этапа (команды).

Начальная ступень

.+
$*

Это простая подстановка регулярных выражений, преобразовывающая входные данные во множество.

Например, 5будет преобразован в 11111.

Вторая стадия

(?!(11+)\1*$(?<=^\1+)).

Это регулярное выражение пытается сопоставить позиции, которые удовлетворяют условию (совместно с вводом), а затем возвращает количество совпадений.

05AB1E, 7 байтов

Lvy¹¿i¼

Разъяснения

Lv        # for each x in range(1,n)
  y¹¿     # GCD(x,n)
     i¼   # if true (1), increase counter
          # implicitly display counter

Попробуйте онлайн

Common Lisp, 58 байт

(defun o(x)(loop for i from 1 to x if (=(gcd x i)1)sum 1))

Это простой цикл, который подсчитывает от 1 до заданного n и увеличивает сумму, если gcd = 1. Я использую имя функции o, поскольку t является истинным логическим значением. Не самый короткий, но довольно простой.

MATLAB / Octave, 21 байт

@(n)sum(gcd(n,1:n)<2)

Создает анонимную функцию с именем, ansкоторая может быть вызвана с целым числом nв качестве единственного ввода:ans(n)

Демо онлайн

Python 2 , 44 байта

lambda n:sum(k/n*k%n>n-2for k in range(n*n))

При этом используется тот же метод для идентификации копримов, что и в моем ответе «Копримы до N» .

Попробуйте онлайн!

JavaScript (ES6), 53 байта

f=(n,k=n)=>k--&&(C=(a,b)=>b?C(b,a%b):a<2)(n,k)+f(n,k)

Попробуйте онлайн!

C (gcc) , 67 65 байт

f(x,a,b,y,z){for(z=y=x;a=y--;z-=b>1)for(b=x;a^=b^=a^=b%=a;);x=z;}

Попробуйте онлайн!

Редактировать: Удалена временная переменная.

Edit2: -1 благодаря @HowChen

Немного меньше в гольф

f(x,a,b,y,z){
  // counts y NOT coprime with x and subtract
  for(z=y=x;a=y--;z-=b>1)
    // compute GCD
    for(b=x;a^=b^=a^=b%=a;);
  x=z;
}

На самом деле, 11 байтов

;╗R`╜g`M1@c

Попробуйте онлайн!

объяснение

;╗R`╜g`M1@c   register stack             remarks

                       44
;                      44 44
 ╗            44       44
  R           44       [1 2 3 .. 44]
       M      44       10                for example
    ╜         44       10 44
     g        44       2
              44       [1 2 1 .. 44]     gcd of each with register
        1     44       [1 2 1 .. 44] 1
         @    44       1 [1 2 1 .. 44]
          c   44       20                count

Со встроенным

▒

Попробуйте онлайн!

JavaScript (ES6), 67 байт

f=n=>[...Array(n)].reduce(r=>r+=g(n,++i)<2,i=0,g=(a,b)=>b?g(b,a%b):a)

APL, 7 байт

+/1=⊢∨⍳

Это последовательность монадических функций, которая принимает целое число справа. Подход здесь очевиден: sum ( +/) - количество раз, которое GCD входа и числа от 1 до input ( ⊢∨⍳) равны 1 ( 1=).

Попробуй здесь

Haskell, 31 30 байт

\n->sum[1|x<-[1..n],gcd n x<2]

1 байт сохранен благодаря @Damien.

Выбирает значения с gcd = 1, сопоставляет каждое с 1, затем берет сумму.