Latar Belakang

Euler totient fungsi φ(n)didefinisikan sebagai jumlah bilangan bulat kurang dari atau sama dengan nyang relatif prima untuk n, yaitu, jumlah nilai yang mungkin dari xdalam 0 < x <= nyang gcd(n, x) == 1. Kami sudah sebuah beberapa totient - terkait tantangan sebelumnya, tapi tidak pernah satu yang hanya menghitung itu.

Pemetaan fungsi totient ke seluruh angka adalah OEIS A000010 .

Tantangan

Diberikan bilangan bulat n > 0, hitung φ(n). Anda dapat mengambil input melalui argumen baris perintah, input standar, argumen fungsi, atau hal lain yang masuk akal. Anda dapat memberikan output melalui output standar, nilai pengembalian, atau hal lain yang masuk akal. Fungsi anonim dapat diterima. Anda dapat berasumsi bahwa input tidak akan meluap metode alami Anda menyimpan bilangan bulat, misalnya intdalam C, tetapi Anda harus mendukung input hingga 255. Jika bahasa Anda memiliki fungsi totient bawaan, Anda tidak boleh menggunakannya.

Contohnya

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

Jawaban terpendek dalam byte menang. Jika bahasa Anda menggunakan penyandian selain UTF-8, sebutkan itu dalam jawaban Anda.

Mathematica, 27 22 byte

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

Fungsi tanpa nama yang mengambil dan mengembalikan integer.

Tidak banyak yang dijelaskan di sini, kecuali yang @notasi awalan untuk panggilan fungsi dan notasi ~...~(asosiatif-kiri), sehingga di atas sama dengan:

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

MATL, 7 byte

t:Zd1=s

Anda dapat TryItOnline . Ide paling sederhana, buatlah vektor 1 ke N, dan ambil gcd dari setiap elemen dengan N ( Zdjangan gcd). Kemudian, cari elemen mana yang sama dengan 1, dan jumlah vektor untuk mendapatkan jawabannya.

J, 9 byte

(-~:)&.q:

Ini didasarkan pada esai Jsoftware tentang fungsi totient.

Diberikan n = p ₁ ^{e ₁} ∙ p ₂ ^{e ₂} ∙∙∙ p _k ^{e _{k di}} mana p _k adalah faktor utama dari n , fungsi total φ ( n ) = φ ( p ₁ ^{e ₁} ) ∙ φ ( p ₂ ^{e ₂} ) ∙∙∙ φ ( p _k ^{e _k} ) = ( p ₁ - 1) p ₁ ^{e ₁ - 1} ∙ ( p ₂ - 1) p ₂^{e ₂ - 1} ∙∙∙ ( p _k - 1) p _k ^{e _k - 1} .

Pemakaian

   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

Penjelasan

(-~:)&.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)

Jelly, 4 byte

Rgċ1

Cobalah online!

Penjelasan

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.

Dengan built-in

ÆṪ

Cobalah online!

Penjelasan

ÆṪ   Main monadic chain. Argument: z

ÆṪ   Totient of z.

Haskell, 28 byte

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

Menggunakan pola konstanta yang cocok dengan Haskell . Trik di sini cukup standar untuk bermain golf, tetapi saya akan menjelaskan kepada khalayak umum.

Ekspresi gcd n<$>[1..n]memetakan gcd nke [1..n]. Dengan kata lain, itu menghitung gcddengan nsetiap nomor dari 1ke n:

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

Dari sini, output yang diinginkan adalah jumlah 1entri, tetapi Haskell tidak memiliki countfungsi. Cara idiomatis filteruntuk mempertahankan hanya 1, dan mengambil hasilnyalength , yang terlalu lama untuk bermain golf.

Sebaliknya, filterdisimulasikan oleh pemahaman daftar [1|1<-l]dengan daftar yang dihasilkan l. Biasanya, daftar pemahaman mengikat nilai ke variabel seperti di [x*x|x<-l], tetapi Haskell memungkinkan pola untuk dicocokkan, dalam hal ini konstanta1 .

Jadi, [1|1<-l]menghasilkan 1pada setiap pertandingan 1, secara efektif mengekstraksi hanya 1dari daftar asli. Memanggilnya summemberikan panjangnya.

Python 2, 44 byte

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

Kurang bermain golf:

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

Menggunakan formula yang Euler totients dari pembagi nmemiliki jumlah n:

Nilai ϕ(n)kemudian dapat dihitung secara rekursif sebagai nminus jumlah di atas pembagi nontrivial. Secara efektif, ini melakukan inversi Möbius pada fungsi identitas. Saya menggunakan metode yang sama dalam golf untuk menghitung fungsi Möbius .

Terima kasih kepada Dennis untuk menghemat 1 byte dengan case dasar yang lebih baik, menyebarkan nilai awal +nke dalam +1untuk setiap nloop, dilakukan sebagai -~.

Pyke, 5 byte

m.H1/

Coba di sini!

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

J, 11 byte

+/@(1=+.)i.

Pemakaian

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

di mana >>STDIN dan <<STDOUT.

Penjelasan

+/ @ ( 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 byte

Terima kasih kepada LeakyNun untuk bermain golf dengan 12 (!) Byte.

Berkat Sp3000 untuk bermain golf 6 byte.

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

Saya suka bagaimana Python dibaca. Ini masuk akal, bahkan melalui golf.

Regex (ECMAScript), 131 byte

Setidaknya -12 byte berkat Deadcode (dalam obrolan)

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

Cobalah online!

Output adalah panjang pertandingan.

Regex ECMAScript membuatnya sangat sulit untuk menghitung apa pun. Setiap backref yang didefinisikan di luar loop akan konstan selama loop, setiap backref yang didefinisikan di dalam loop akan direset ketika looping. Dengan demikian, satu-satunya cara untuk membawa status melintasi loop berulang adalah menggunakan posisi kecocokan saat ini. Itu bilangan bulat tunggal, dan itu hanya bisa berkurang (well, posisinya meningkat, tetapi panjang ekornya berkurang, dan itulah yang bisa kita lakukan dengan matematika).

Mengingat pembatasan-pembatasan itu, menghitung angka-angka coprime tampaknya mustahil. Sebagai gantinya, kami menggunakan formula Euler untuk menghitung angka total.

Begini tampilannya di pseudocode:

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

Ada dua hal yang meragukan tentang ini.

Pertama, kita tidak menyimpan input, hanya produk saat ini, jadi bagaimana kita bisa sampai pada faktor utama input? Triknya adalah bahwa (N - (N / P)) memiliki faktor prima yang sama> P dengan N. Ini mungkin mendapatkan faktor prima baru <P, tetapi kita tetap mengabaikannya. Perhatikan bahwa ini hanya berfungsi karena kita beralih pada faktor utama dari yang terkecil hingga yang terbesar, sebaliknya akan gagal.

Kedua, kita harus mengingat dua angka di seluruh iterasi loop (P dan N, Z tidak dihitung karena konstan), dan saya hanya mengatakan itu tidak mungkin! Syukurlah, kita dapat memutar dua angka itu dalam satu. Perhatikan bahwa, pada awal loop, N akan selalu menjadi kelipatan Z, sedangkan P akan selalu kurang dari Z. Dengan demikian, kita bisa mengingat N + P, dan mengekstrak P dengan modulo.

Berikut kode semu yang sedikit lebih detail:

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

Dan inilah regex yang dikomentari:

# \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

Dan sebagai bonus ...

Regex (ECMAScript 2018, jumlah kecocokan), 23 byte

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

Cobalah online!

Output adalah jumlah kecocokan. ECMAScript 2018 memperkenalkan variabel-panjang melihat-belakang (dievaluasi dari kanan ke kiri), yang memungkinkan untuk hanya menghitung semua angka coprime dengan input.

Ternyata ini adalah metode independen yang sama yang digunakan oleh solusi Retina Leaky Nun , dan regex bahkan memiliki panjang yang sama ( dan dapat dipertukarkan ). Saya meninggalkannya di sini karena mungkin menarik bahwa metode ini berfungsi di ECMAScript 2018 (dan bukan hanya .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

Perl 6 ,  26 24  22 byte

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

Penjelasan:

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

Contoh:

#! /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

Julia, 25 byte

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

Sederhana - sumfungsi ini memungkinkan Anda untuk memberikannya fungsi untuk diterapkan sebelum dijumlahkan - pada dasarnya setara dengan menjalankan mapdan kemudian sum. Ini secara langsung menghitung jumlah bilangan prima yang relatif kurang n.

Python 2, 57 byte

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

Uji di Ideone .

Latar Belakang

Dengan formula produk Euler ,

di mana φ menunjukkan fungsi total Euler dan p bervariasi hanya pada bilangan prima.

Untuk mengidentifikasi bilangan prima, kami menggunakan wajar teorema Wilson :

Bagaimana itu bekerja

Setiap saat, variabel m akan sama dengan kuadrat faktorial dari k - 1 . Bahkan, kami menamai argumen default ke k = 1 dan m = 0! ² = 1 .

Selama k ≤ n , n*(k>n)dievaluasi menjadi 0 dan kode berikut ordijalankan.

Ingat bahwa m%kakan menghasilkan 1 jika m adalah prima dan 0 jika tidak. Ini berarti bahwa x%k<m%kakan menghasilkan True jika dan hanya jika kedua k adalah bilangan prima dan x dapat dibagi oleh k .

Dalam hal ini, (n%k<m%k)*n/khasilkan n / k , dan kurangi dari n menggantikan nilai sebelumnya dengan n (1 - 1 / k) , seperti dalam formula produk Euler. Jika tidak, (n%k<m%k)*n/khasil 0 dan n tetap tidak berubah.

Setelah menghitung di atas, kami menambah k dan mengalikan m dengan nilai "lama" dari k ² , dengan demikian mempertahankan hubungan yang diinginkan antara k dan m , kemudian memanggil f secara rekursif dengan argumen yang diperbarui.

Setelah k melebihi n , n*(k>n)evaluasi ke n , yang dikembalikan oleh fungsi.

Ruby, 32 byte

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

sebuah lambda yang mengambil bilangan bulat n, dan mengembalikan jumlah berapa banyak bilangan bulat dalam rentang (1..n) yang coprime dengan n.

Brachylog , 25 byte

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

Penjelasan

Brachylog belum memiliki built-in GCD, jadi kami memeriksa bahwa kedua angka tersebut tidak memiliki faktor utama yang sama.

• Predikat utama:

  :{...}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
  

• Predikat 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 byte

smq1iQ

Cobalah online!

/iLQQ1

Cobalah online!

Penjelasan

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 byte

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

PowerShell tidak memiliki fungsi GCD yang tersedia, jadi saya harus memutar sendiri.

Ini membutuhkan input $n, kemudian berkisar dari 1ke $ndan menyalurkannya ke dalam satu lingkaran |%{...}. Setiap iterasi kami menetapkan dua variabel penolong $adan $bkemudian mengeksekusi GCD whilelingkaran. Setiap iterasi yang kami periksa $bmasih non-nol, dan kemudian disimpan $a%$bke $bdan nilai sebelumnya $buntuk $auntuk loop berikutnya. Kami kemudian mengakumulasikan apakah $asama dengan 1variabel output kami $o. Setelah for loop selesai, kita menempatkan $opada pipeline dan output tersirat.

Sebagai contoh cara kerja whileloop, pertimbangkan $n=20dan kita aktif $_=8. Cek pertama sudah $b=20, jadi kita masuk ke loop. Kami pertama-tama menghitung $a%$batau 8%20 = 8, yang ditetapkan $bpada saat yang sama dengan yang 20ditetapkan $a. Periksa 8=0, dan kami memasuki iterasi kedua. Kami kemudian menghitung 20%8 = 4dan mengaturnya $b, kemudian mengatur $ake 8. Periksa 4=0, dan kami masukkan iterasi ketiga. Kami menghitung 8%4 = 0dan mengaturnya menjadi $b, lalu mengatur $ake 4. Periksa 0=0dan kita keluar dari loop, jadi GCD (8,20) adalah $a = 4. Jadi, !($a-1) = !(4-1) = !(3) = 0jadi $o += 0dan kami tidak menghitungnya.

Faktor, 50 byte

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

Membuat rentang ( iota ) n , dan menyematkan n ke dalam fungsi yang mendapat gcd xn untuk semua nilai 0 <= x <= n , menguji jika hasilnya 1 . Saring rentang asli pada apakah hasil gcd xn adalah 1 , dan ambil panjangnya .

Japt -mx, 7 5 byte

yN ¥1

Jalankan secara online

-2 byte terima kasih kepada Shaggy

Retina, 36 29 byte

7 byte berkat Martin Ender.

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

Cobalah online!

Penjelasan

Ada dua tahap (perintah).

Tahap pertama

.+
$*

Ini adalah penggantian regex sederhana, mengubah input menjadi banyak.

Misalnya, 5akan dikonversi menjadi 11111.

Tahap kedua

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

Regex ini mencoba mencocokkan posisi yang memenuhi kondisi (co-prime dengan input), dan kemudian mengembalikan jumlah kecocokan.

Gangguan Umum, 58 byte

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

Ini adalah loop sederhana yang menghitung hingga 1 sampai n yang diberikan dan menambah jumlah jika gcd = 1. Saya menggunakan nama fungsi o karena t adalah nilai boolean yang sebenarnya. Bukan yang terpendek tapi cukup sederhana.

MATLAB / Oktaf, 21 byte

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

Membuat fungsi anonim bernama ansyang dapat dipanggil dengan integer nsebagai satu-satunya input:ans(n)

Demo online

Python 2 , 44 byte

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

Ini menggunakan metode yang sama untuk mengidentifikasi coprime jawaban saya untuk “Coprimes hingga N” .

Cobalah online!

JavaScript (ES6), 53 byte

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

Cobalah online!

Sebenarnya, 11 byte

;╗R`╜g`M1@c

Cobalah online!

Penjelasan

;╗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

Dengan built-in

▒

Cobalah online!

JavaScript (ES6), 67 byte

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

05AB1E, 7 byte

Lvy¹¿i¼

Dijelaskan

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

Cobalah online

APL, 7 byte

+/1=⊢∨⍳

Ini adalah kereta fungsi monadik yang mengambil bilangan bulat di sebelah kanan. Pendekatan di sini adalah yang jelas: jumlah (+/ ) berapa kali GCD dari input dan angka dari 1 ke input ( ⊢∨⍳) sama dengan 1 ( 1=).

Coba di sini

Haskell, 31 30 byte

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

1 byte disimpan, terima kasih kepada @Damien.

Pilih nilai dengan gcd = 1, petakan masing-masing ke 1, lalu ambil jumlah.

Batch, 151 145 144 byte

@echo off
set t=
for /l %%i in (1,1,%1)do call:g %1 %%i
echo %t%
exit/b
:g
set/ag=%1%%%2
if not %g%==0 call:g %2 %g%
if %2%==1 set/at+=1

Sunting: Disimpan 4 byte dengan menghapus spasi yang tidak perlu. Disimpan 1 byte dengan menggunakan +=. Disimpan 1 byte dengan mengosongkan tsebagaimana +=akan menafsirkannya sebagai 0pula. Disimpan 1 byte berkat @ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ.