Katak utama 🐸

44

"Katak utama" adalah hewan aneh yang melompat di antara bilangan bulat, sampai tiba pada 3 atau 19 ...


Program Anda harus menerima bilangan bulat nsebagai input dan output hasil dari algoritma di bawah ini ( 3atau 19).

Untuk bilangan bulat yang diberikan n >= 2:

  1. Biarlah fposisi katak. Awalnya diatur ken
  2. jika f = 3atau f = 19: katak berhenti melompat - hentikan program dan output f.
  3. if fis prime: katak melompat ke posisi 2×f-1. Kembali ke langkah 2.
  4. jika fkomposit: mari dmenjadi fpembagi utama terbesar. Katak melompat ke posisi f-d. Kembali ke langkah 2.

Contoh:

Contoh dengan n = 5:

5 > 9 > 6 > 3 stop

Program harus menampilkan 3.

Contoh lain dengan n = 23:

23 > 45 > 40 > 35 > 28 > 21 > 14 > 7 > 13 > 25 > 20 > 15 > 10 > 5 > 9 > 6 > 3 stop

Sekali lagi, program harus menampilkan 3.

Kasus uji:

10 => 3
74 => 19
94 => 3
417 => 3
991 => 19
9983 => 19

Anda dapat mengasumsikan 1 < n < 1000000(saya telah memeriksa akhir program untuk nilai-nilai ini).

Arnaud
sumber
3
3 loop adalah [3 5 9 6 3] dan 19 loop adalah [19 37 73 145 116 87 58 29 57 38 19]
Arnaud
8
Variasi Collatz keren.
Arthur
3
Jika kita tidak dapat membuktikan bahwa katak selalu datang ke 3atau 19, kita dapat mengubah item 2. dalam algoritma untuk mengatakan bahwa jika katak telah memasuki loop apa pun (menemukan posisi yang telah dilihatnya sebelumnya), maka ia berhenti melompat dan mengembalikan yang terkecil. anggota dari loop itu.
Jeppe Stig Nielsen
4
@PyRulez Jika mencapai itu, Anda mungkin harus memberi tahu OP.
mbomb007
3
@KeyuGan Mungkin ini akan menjadi hal yang baik untuk dikirim tentang di Math.SE.
mbomb007

Jawaban:

16

Python 2 , 101 93 92 90 88 87 85 byte

import sympy
n=input()
while~16&n-3:m=max(sympy.factorint(n));n-=[1-n,m][m<n]
print n

Cobalah online!

TFeld
sumber
1
while~16&n!=3menghemat satu byte.
Lynn
6
Oh, ~16&n-3bahkan berhasil!
Lynn
12

C (gcc),  87  65 byte

i,k;f(n){for(i=n;i>1;)for(k=i;k%--i;);n=~16&n-3?f(n-k?:n+n-1):n;}

Cobalah online!

Penjelasan:

i,k;
f(n)
{
    for (i=n; i>1;)              // Loop until `k` is prime (the largest positive
                                 // `i` inequal to `k` that divides `k` is 1).
        for (k=i; k%--i;);       // Find the largest factor `k`

    n =                          // Returning like this is undefined behaviour,
                                 // but happens to work with gcc. This can be
                                 // replaced with `return` at the cost of 4 bytes.

        ~16&n-3                  // If `n` is 3 or 19, this expression equals 0 and
                                 // the algorithm halts. Otherwise the function
                                 // calls itself to perform the next iteration.

        ? f(n-k ?: n+n-1)        // If `n-k` is non-zero, n is not prime.
                                 // In this case call `f` with the value of `n-k`.
                                 // (Omitting the second `n-k` between `?` and `:`
                                 // is a gcc extension)
                                 // Otherwise call `f` with `2*n-1`.

        : n;                     // All done, `n` is returned.
}

Versi portabel (72 byte):

i,k;f(n){for(i=n;i>1;)for(k=i;k%--i;);return~16&n-3?f(n-k?n-k:n+n-1):n;}

Cobalah online!

Dengan nama variabel yang lebih tepat:

f,r;o(g){for(f=g;f>1;)for(r=f;r%--f;);g=~16&g-3?o(g-r?:g+g-1):g;}

Cobalah online!

Steadybox
sumber
5
Sangat suka bermain dengan kata katak dan variabel Anda. +1.
rayryeng
10

Retina , 63 62 byte

Terima kasih kepada Neil untuk menghemat 1 byte.

{`^(11+)(?<!^\2+(11+))(?=\1+$)

^(?!(11+)\1+$|111$|1{19}$)1
$_

Cobalah online!

Input dan output dalam unary (test suite menggunakan desimal untuk kenyamanan). Solusi ini menjadi sangat lambat untuk input yang lebih besar. Waktu 9983ujian habis pada TIO.

Penjelasan

Karena itu {, kedua tahap program hanya dijalankan dalam satu lingkaran sampai mereka tidak lagi mempengaruhi string. Kami bergantian antara komposit pemrosesan panggung dan bilangan prima pemrosesan panggung. Itu memungkinkan kita menghindari persyaratan yang sebenarnya (yang tidak benar-benar ada di Retina). Jika nilai saat ini adalah jenis yang salah untuk panggung, panggung tidak melakukan apa-apa.

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

Ini memproses komposit. Kami cocok dengan pembagi potensial dengan (11+), tetapi kemudian kami memeriksa bahwa itu tidak komposit dengan (?<!^\2+(11+)), jadi kami hanya mempertimbangkan faktor prima. Karena keserakahan +, ini memprioritaskan faktor terbesar. Kemudian kami memeriksa bahwa pembagi potensial ini adalah pembagi yang sebenarnya dengan mencoba mencocokkan sisa string dengan pengulangan (?=\1+$),. Pembagi ini hanya dihapus dari string, yang merupakan cara Anda mengurangi sesuatu secara unary.

^(?!(11+)\1+$|111$|1{19}$)1
$_

Ini memproses bilangan prima, kecuali 3 dan 19 . Lookahead negatif memastikan bahwa input tidak komposit, bukan 3 dan bukan 19 . Kemudian kami mencocokkan satu 1dan menggantinya dengan seluruh string. Ini adalah bentuk unary komputasi n - 1 + n , yang tentu saja adalah 2n-1 .

Setelah kami menekan 3 atau 19 , kedua panggung tidak dapat mencocokkan string dan itu tidak akan lagi berubah.

Martin Ender
sumber
1
Tidak 1$'sama dengan $_?
Neil
4
@Neil Ya ......
Martin Ender
8

Sekam , 15 byte

Ω€p57§|o←DṠ-o→p

Cobalah online!

Penjelasan

Ω€p57§|o←DṠ-o→p  Implicit input n.
Ω                Do this to n until
 €p57            you get a prime factor of 57 (which are 3 and 19):
            o→p   Take last element of the prime factors of n
          Ṡ-      and subtract it from n,
     §|           or if this gives 0 (so n is prime),
       o←D        double and decrement n.
Zgarb
sumber
8

Jelly , 12 byte

_ÆfṂoḤ’$µÐḶṂ

Cobalah online!

Bagaimana itu bekerja

_ÆfṂoḤ’$µÐḶṂ  Maink link. Argument: n

        µ     Combine the links to the left into a chain.
         ÐḶ   Repeatedly call the chain monadically until the results are no longer
              unique. Yield the loop, i.e., the first occurrence of the first
              repeated integer, up to and excluding the repetition.
              Let's call the argument of the chain k.
_Æf             Subtract all prime factors of k from k.
   Ṃ            Take the minimum of the differences. This yields 0 iff k is prime.
     Ḥ’$        Compute 2k-1.
    o           Take the logical OR of the results.
              The result is now a rotation of either [3, 5, 9, 6] or
              [19, 37, 73, 145, 116, 87, 58, 29, 57, 38].
          Ṃ   Take the minimum, yielding either 3 or 19.
Dennis
sumber
7

Bahasa Wolfram (Mathematica) , 6566 68 byte

#//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]&
  • -1 byte, terima kasih kepada Misha Lavrov!
  • -2 byte, terima kasih untuk Martin!

Cobalah online!

Terinspirasi oleh tip . Pada dasarnya, itu hanya membuat ulang algoritma.

//.adalah RepeatedReplacedan /;sekarang Condition. Jadi, kode akan menggantikan i_(jumlah tunggal) dengan If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i], sampai i!=3&&!=19mengevaluasi True.

Benchmark:

patokan

Keyu Gan
sumber
3
fakta yang menyenangkan: kode ini tidak akan berfungsi untuk angka yang lebih besar seperti 10000000010karenamaximum number of iterations is 2^16 (= 65536)
J42161217
1
Cara yang sedikit lebih pendek untuk memeriksa 3 dan 19 adalah#//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]&
Misha Lavrov
@MishaLavrov tetapi hasilnya salah?
Keyu Gan
@KeyuGan Bagi saya, kedua fungsi memberikan hasil yang persis sama untuk bilangan bulat 1 hingga 1000.
Misha Lavrov
1
Mungkin masalah yang Anda alami adalah karakter yang tidak patut dimasukkan saat Anda menyalin dan menempel dari komentar, yang kadang-kadang terjadi.
Misha Lavrov
6

05AB1E , 19 18 17 byte

[ÐƵηfså#pi·<ëDfθ-

Cobalah online!

Penjelasan

[      #            # loop until
 Ð   så             # a copy of the current value is contained in
  Ƶηf               # the unique prime factors of 171
        pi          # if the current value is prime
          ·<        # double and decrement
            ë   -   # else subtract
             Dfθ    # the largest prime factor of a copy of the current value
Emigna
sumber
4
+1 karena memiliki katak yang sebenarnya dalam kode sumber Anda
Arnaud
Untuk 57.991 lebih dari 1 menit
RosLuP
@RosLuP: Anda lebih baik menjalankan test case yang sangat lama secara offline;)
Emigna
5

JavaScript (ES6), 73 71 69 byte

f=n=>57%n?f(n-(g=(k,d=1)=>++d<k?k%d?g(k,d):g(k/d):d<n?d:1-n)(n)):n%38

Uji kasus

Diformat dan dikomentari

f = n =>                 // given n
  57 % n ?               // if n is neither 3, 19 or 57 (and assuming that n is > 1):
    f(                   //   do a recursive call to f() with:
      n -                //     n minus
      (g = (k, d = 1) => //     the result of the recursive function g():
        ++d < k ?        //       increment d; if d is less than k:
          k % d ?        //         if d is not a divisor of k:
            g(k, d)      //           recursive call to g() with k and d unchanged
          :              //         else:
            g(k / d)     //           recursive call to g() with k = k / d, d = 1
        :                //       else, d is now the highest prime divisor of n:
          d < n ?        //         if d is less than n:
            d            //           n is composite: return d, which results in f(n - d)
          :              //         else:
            1 - n        //           n is prime: return 1 - n, which results in f(2n - 1)
      )(n)               //     initial call to g()
    )                    //   end of recursive call to f()
  :                      // else:
    n % 38               //   return n % 38 (gives 19 as expected if n = 57)
Arnauld
sumber
1
Cerdas, menggunakan 57%ndan n%38bukannya n==3|n==19. Disimpan 1 byte dalam jawaban Java saya juga, jadi terima kasih!
Kevin Cruijssen
Dalam ideone 57991 input menghasilkan prog.js: 2: 26 InternalError: terlalu banyak rekursi
RosLuP
Dalam tio f = n => 57% n? F (n- (g = (k, d = 1) => ++ d <k? K% d? G (k, d): g (k / d) : d <n? d: 1-n) (n)): n% 38 print (f (57991)) menghasilkan program berhenti bukan keluaran, menurut saya
RosLuP
1
@RosLuP Ini adalah tantangan kode-golf tanpa kendala spesifik. Konsensus saat ini adalah bahwa kecepatan atau keterbatasan memori (seperti ukuran tumpukan panggilan) dapat diabaikan kecuali secara eksplisit dinyatakan sebaliknya dalam pertanyaan. Saya menerima begitu saja bahwa batas 1000000 hanya informatif karena urutannya tidak diuji lebih dari itu. Secara kebetulan, solusi 70-byte Anda baik-baik saja dan mungkin lebih relevan daripada versi 93-byte untuk tantangan kode-golf.
Arnauld
4

Jelly , 23 19 byte

-4 byte dari mil . Masih lebih lama dari 05AB1E.

Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿

Cobalah online!

pengguna202729
sumber
1
Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿menggunakan loop sementara sebagai gantinya dan beberapa pemesanan ulang
mil
4

Python 2 , 110 105 103 101 byte

-2 byte terima kasih kepada @Lynn

f=lambda n,i=2,k=0:i/n and(n*(n&~16==3)or f((2*i-1,k-i)[k>0]))or n%i and f(n,i+1,k)or f(n/i,2,k or n)

Cobalah online!


Python 2 , 116 112 105 byte

f=lambda n,i=2:i/n*i or n%i and f(n,i+1)or f(n/i)
n=input()
while~16&n-3:n=[2*n-1,n-f(n)][f(n)<n]
print n

Cobalah online!

ovs
sumber
1
…n*(n&~16==3)or…menghemat 2 byte.
Lynn
Untuk input 57991 sys.setrecursionlimit (20000)
RosLuP
4

MATL , 22 21 byte

Terima kasih kepada @Giuseppe karena menghapus 1 byte!

`tZp?Eq}tYfX>-]tI19h-

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

`           % Do...while
  t         %   Duplicate. Takes (implicit) input the first time
  Zp        %   Is it prime? 
  ?         %   If so
    Eq      %     Times 2, minus 1
  }         %   Else
    t       %     Duplicate
    YfX>-   %     Prime divisors, maximum, subtract
  ]         %   End
  t         %   Duplicate
  I19h      %   Push array [3 19]
  -         %   Subtract, element-wise. The result is truthy if and only if
            %   it doesn't contain any zero
            % End (implicit). Next iteraton if top of the stack is truthy
            % Display (implicit)
Luis Mendo
sumber
4

Haskell - 154 byte

f 3=3
f 19=19
f n
 |(c==[1])=f$2*n-1
 |True=f$n-head c
 where c=z n;v b=reverse[x|x<-[1..(b-1)],b`rem`x==0];z j=case v j of[1]->[1];s->filter((==[1]).v)$s

Mungkin melewatkan beberapa trik golf di sini, ini adalah usaha pertama saya di haskell golf.

Besi GREMLIN
sumber
Halo dan selamat datang di situs ini. Anda tidak perlu baris baru dan spasi untuk penjaga pola. Anda juga dapat menggunakan 1>0untuk Truesebagian besar kali tetapi sering mungkin lebih baik untuk menggunakan sebuah tugas, misalnya c<-z n.
Wheat Wizard
1
[x|x<-[b-1,b-2..1],rem b x==0]juga pendek dari reverse[x|x<-[1..(b-1)],brem x==0].
Wheat Wizard
2
Dan satu hal lagi, jika Anda ingin mendiskusikan golf haskell, Anda dapat bergabung dengan kami di Of Monads and Men .
Wheat Wizard
3

Neim , 17 16 byte

ͻY𝐏𝕚÷D𝐌Ξᚫ<#D𝐏𝐠𝕊

Penjelasan:

ͻ                   Start infinite loop
 D                  Duplicate
  Y                 Push 57
   𝐏                Prime factors: [3 19]
     𝕚              If the second-to-top of stack is in the list
      ÷             Break the loop
       D            Duplicate
        𝐌Ξᚫ<       If prime, double and decrement
            #D𝐏𝐠𝕊   Otherwise, subtract the largest prime factor

Cobalah online!

Okx
sumber
3

Angka R + , 102 99 byte

function(n){while(!n%in%c(3,19))n="if"(isPrime(n),2*n-1,n-max(primeFactors(n)))
n}
library(numbers)

Cobalah online!

R tidak dikenal dengan built-in pendek, dan bahkan paket pun mengikutinya!

Giuseppe
sumber
3

Java 8, 140 135 134 94 byte

n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;t/=m=f);return n%38;}

-5 byte mengkonversi metode Java 7 rekursif ke Java 8 lambda dengan loop.
-1 byte secara implisit berkat jawaban JavaScript @Arnauld dengan mengubah n!=3&n!=19dan return n;ke 57%n>0dan return n%38;.
Saya pikir itu mungkin untuk menggabungkan kedua loop dan memeriksa apakah nitu prima, dan mendapatkan faktor prima terbesar pada saat yang sama, tetapi saya belum bisa mengetahuinya (belum). Jadi ini akan menjadi versi awal untuk saat ini.
-40 byte kekalahan berkat @Nevay, dengan melakukan apa yang tidak bisa saya lakukan: menggabungkan loop untuk memeriksa bilangan prima dan faktor prima terbesar sekaligus.

Penjelasan:

Cobalah di sini (jalankan bahkan 999999dalam waktu kurang dari 1 detik).

n->{                  // Method with integer as both parameter and return-type
  for(int f,          //  Flag-integer
          t,          //  Temp-integer
          m=1;        //  Max prime factor integer, starting at 0
      57%n>0;         //  Loop (1) as long as `n` is not 3, not 19 and not 57:
      n=f>n?          //    After every iteration: if `f` is larger than `n`:
         2*n-1        //     Change `n` to `2*n-1`
        :             //    Else:
         n-m)         //     Change `n` to `n-m`
    for(t=n,          //   Reset `t` to `n`
        f=1;          //   Reset `f` to 1
        f++<t;)       //   Inner loop (2) from 2 to `t` (inclusive)
      for(;t%f<1;     //    Inner loop (3) as long as `t` is divisible by `f`
        t/=m=f;       //     Set `m` to `f`, and set `t` to `t/f`
      );              //    End of inner loop (3)
                      //   End of inner loop (2) (implicit / single-line body)
                      //  End of loop (1) (implicit / single-line body)
  return n%38;        //  Return `n%38`, which is now either 3 or 19
}                     // End of method
Kevin Cruijssen
sumber
1
1 karakter singkat sebagai C # polyglot :(
Ian H.
@IanH. Hehe, ya, itu biasanya masalahnya: n=>bukannya n->. Dan terkadang panggilan huruf kecil / besar. ;)
Kevin Cruijssen
1
94 byte:n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;)t/=m=f;return n%38;}
Nevay
@Tidak, Terima kasih! Saya hanya tahu itu mungkin untuk menggabungkan loop, tetapi tidak bisa mengetahuinya. 40 byte kekalahan disimpan berkat Anda!
Kevin Cruijssen
3

Bash, 73 byte

((57%$1))&&$0 $[(x=$1-`factor $1|sed 's/.* //'`)?x:2*$1-1]||echo $[$1%38]

Cobalah online! Dimodifikasi sedikit agar bekerja di TIO.

Secara rekursif memanggil file skrip sendiri menggunakan $0, yang tidak berfungsi di TIO karena harus dijalankan sebagai./filename.sh . Menerima input sebagai argumen baris perintah.

Menggunakan trik modulus yang sama dengan jawaban JS @ Arnauld .

Uji Kasus

$ for t in 5 23 10 74 94 417 991 9983;{ echo -n "$t -> "; ./prime-frog.sh $t; }
5 -> 3
23 -> 3
10 -> 3
74 -> 19
94 -> 3
417 -> 3
991 -> 19
9983 -> 19
Justin Mariner
sumber
2

Python 3 , 97 byte

f=lambda n:n*(n&-17==3)or f(n-max(k*all(n%k<k%j for j in range(2,k))for k in range(n+1))or 2*n-1)

Cobalah online!

Dennis
sumber
Untuk 57.991 input 1 menit tidak cukup
RosLuP
1

Pyth , 19 byte

.W!/P57H?P_ZtyZ-ZeP

Verifikasi semua kasus uji!

The Husk jawaban mengilhami saya untuk menyimpan 2 bytes ( ,3 19untuk P57).

Bagaimana ini bekerja?

.W! / P57H? P_ZtyZ-ZeP - Program lengkap.

.W - Sementara fungsional. Sementara A (nilai) benar, nilai = B (nilai). Mengembalikan nilai terakhir.
    P57 - Faktor utama 57 ([3, 19]).
   / H - Hitung kejadian dari nilai saat ini.
  ! - TIDAK logis. 0 -> Sejujurnya, hal lain -> Falsy.
        ? P_Z - Jika nilai saat ini prima, maka:
            tyZ - Gandakan nilai saat ini, penurunan.
               -ZeP - Lain-lain, kurangi faktor prima maksimal dari nilai saat ini dari dirinya sendiri.
                     - Cetak secara implisit.
Tuan Xcoder
sumber
1

PowerShell , 150 126 byte

for($n="$args";57%$n){$a=$n;$d=for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}};if($n-in$d){$n+=$n-1}else{$n-=$d[-1]}}$n%38

Cobalah online! (peringatan: lambat untuk jumlah yang lebih besar)

Metode berulang. PowerShell tidak memiliki built-in faktorisasi prima, jadi ini meminjam kode dari jawaban saya pada Prime Factors Buddies .

Pertama adalah forloop kami . Pengaturan ditetapkan $nsebagai nilai input, dan kondisi membuat loop tetap selama 57%$ntidak nol (terima kasih kepada Arnauld untuk trik itu). Di dalam loop pertama-tama kita mendapatkan daftar faktor prima $a(diatur ke $n). Ini adalah kode yang dipinjam dari Prime Factors Buddies. Jika input $asudah prima, ini akan kembali hanya $a(penting nanti). Itu (berpotensi adil $a) disimpan ke dalam $d.

Berikutnya adalah if/ elsekondisional. Untuk ifbagian itu, kami memeriksa apakah $nada -in $d. Jika ya, itu berarti yang $nutama, jadi kita ambil $n=2*$n-1atau $n+=$n-1. Kalau tidak, itu komposit, jadi kita perlu menemukan faktor prima terbesar. Itu berarti kita perlu mengambil yang terakhir [-1]dari $ddan kurangi yang dari $ndengan $n-=. Ini berfungsi karena kita beralih dari 2dan dengan demikian elemen terakhir $dsudah akan menjadi yang terbesar.

Setelah kami selesai mengulang, kami hanya menempatkan $n%38(sekali lagi, terima kasih Arnauld) pada pipeline dan output tersirat.

AdmBorkBork
sumber
1

APL (Dyalog Unicode) , 113 90 59 byte

CY 'dfns'
g←{1pco ⍵:f(2×⍵)-1f⍵-⊃⌽3pco ⍵}
f←{⍵∊3 19:⍵⋄g ⍵}

Cobalah online!

TIO bekerja dengan nilai hingga ~ 3200. Diuji pada PC saya untuk test case terakhir. Untuk mengujinya di TIO, cukup tambahkan f valueke bagian bawah kode. Tidak berlaku lagi, terima kasih kepada @ Adám karena telah menunjukkan bahwa algoritma pemeriksaan keaslian saya benar-benar buruk dan memberi saya pengganti; juga untuk menghemat 23 byte.

Diedit untuk memperbaiki jumlah byte.

Bagaimana itu bekerja

CY 'dfns'                      # Imports every Defined Function, which is shorter than importing just the function I used (pco).

g←{1pco ⍵:f(2×⍵)-1f⍵-⊃⌽3pco ⍵} 
g                              # define g as
   1pco ⍵:                      # if the argument ⍵ is prime
          f(2×⍵)-1              # Call f over 2×⍵-1
                  f            # else, call f over
                               # the first element of the
                      3pco     # list of prime factors of ⍵
                               # reversed

f←{⍵∊3 19:⍵⋄g ⍵}
f                              # Define f as
        :                      # if the argument ⍵
                               # is in
     3 19                       # the list [3, 19]
                               # return the argument ⍵
                               # else
            g                  # call g over the argument ⍵
J. Sallé
sumber
1

Aksioma, 93 byte

h(n)==(repeat(n=3 or n=19 or n<2=>break;prime? n=>(n:=2*n-1);n:=n-last(factors(n)).factor);n)

uji:

(4) -> [[i,h(i)] for i in [10,74,94,417,991,9983]]
   (4)  [[10,3],[74,19],[94,3],[417,3],[991,19],[9983,19]]
                                                  Type: List List Integer

Akan ada fungsi 68 byte

q x==(n<4=>3;n=19=>n;prime? n=>q(2*n-1);q(n-last(factors n).factor))

tetapi untuk n = 57991 (jika saya ingat dengan baik) itu keluar dari ruang stack dicadangkan.

RosLuP
sumber
0

Python 2 , 93 byte

Port dari jawaban TFeld tanpa lib eksternal.

n=input()
while~16&n-3:
 f=n;i=2
 while i<f:
	if f%i:i+=1
	else:f/=i
 n-=[1-n,f][f<n]
print n

Cobalah online!

Felipe Nardi Batista
sumber