Bisakah angka tersebut mencapai 1 dengan berulang kali mengurangi prime terbesar kurang dari itu?

27

Tantangan:

Diberi nomor, ambil bilangan prima terbesar benar-benar kurang dari itu, kurangi dari bilangan ini, lakukan ini lagi ke bilangan baru ini dengan bilangan prima terbesar lebih sedikit daripada itu, dan terus lakukan ini sampai kurang dari 3. Jika mencapai 1, Anda program harus menampilkan nilai yang benar, jika tidak, program harus menampilkan nilai yang salah.

Contoh:

Semua ini harus memberikan nilai kebenaran:

3
4
6
8
10
11
12
14
16
17
18
20
22
23
24
26
27
29
30
32
34
35
37
38
40
41
42
44
46
47
48
50

Semua ini harus memberikan nilai falsey:

5
7
9
13
15
19
21
25
28
31
33
36
39
43
45
49

Aturan:

  • Anda dapat menulis suatu program atau fungsi.
  • Anda dapat mengasumsikan bahwa input lebih besar dari 2.
  • Celah standar berlaku
  • Ini adalah sehingga jawaban terpendek menang!
Loovjo
sumber
terkait oeis.org/A175071
flawr
1
5-3 = 2, 2 - (- 2) = 4, 4-3 = 1. (/
@Hurkyl -2 = -1 × 2, jadi tidak prima ;-)
ETHproduksi
1
@ ETHProduksi: Ah, tapi -1 adalah satu unit; faktorisasi yang tidak bertentangan dengan keutamaan -2 tidak lebih dari 2 = (- 1) × (-2) tidak dari 2. (atau bahkan 2 = 1 × 2)
3
@ ETHproductions: Angka-angka rasional menarik karena ada dua pendekatan yang sangat berbeda yang berguna dalam praktik! Bilangan rasional tidak memiliki bilangan prima (bahkan 2!) Karena semuanya adalah satu unit. Namun, Anda juga dapat melihat rasional sebagai konstruksi yang dibuat dari bilangan bulat dan mempelajarinya menggunakan bilangan prima dari bilangan bulat. (mis. siapa pun yang meminta faktorisasi utama dari 9/10apa 2^(-1) 3^2 5^(-1)yang dipikirkan dalam istilah yang terakhir)

Jawaban:

8

Jelly , 9 8 byte

’ÆRṪạµ¡Ḃ

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

’ÆRṪạµ¡Ḃ  Main link. Argument: n

     µ    Combine all atoms to the left into a chain.
’           Decrement; yield n - 1.
 ÆR         Prime range; yield all primes in [2, ..., n -1].
   Ṫ        Tail; yield p, the last prime in the range.
            If the range is empty, this yields p = 0.
    ạ       Compute the absolute difference of p and n.
      ¡   Call the chain to the left n times.
          This suffices since each iteration decreases n, until one of the fixed
          points (1 or 2) is reached.
       Ḃ  Bit; return the parity of the fixed point.
Dennis
sumber
11

Retina , 31 byte

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

Cetakan 0(falsy) atau 1(kebenaran).

Cobalah online! (Baris pertama memungkinkan suite tes yang dipisahkan dengan linefeed.)

Penjelasan

.+
$*

Konversi input ke unary dengan mengubah input Nmenjadi Nsalinan 1.

+`1(?!(11+)\1+$)11+
1

Secara berulang menghapus prime terbesar kurang dari input. Ini didasarkan pada uji primality standar dengan regex .

^1$

Periksa apakah hasilnya tunggal 1.

Martin Ender
sumber
Bagaimana Anda bisa menggunakan Retina tanpa unary? Oo
Addison Crump
@Syxer dua baris pertama mengkonversi input ke unary.
Martin Ender
Tidakkah itu berarti Anda dapat menghapusnya dan meminta masukan yang tidak masuk?
Addison Crump
2
@Syxer saya bisa, tapi saya agak berhenti melakukan itu. Sepertinya format I / O yang cerdik, dan sekarang konversi adalah 6 byte (berbeda dengan ~ 200 sebelumnya), saya tidak berpikir Retina dianggap sebagai "tidak bisa mengambil input dalam desimal".
Martin Ender
Ah, begitu. Saya hanya pernah melihat input unary di Retina, jadi kebingungan saya.
Addison Crump
8

Pyth, 18 15 14 byte

Terima kasih kepada @Maltysen untuk -1 byte

#=-QefP_TUQ)q1

Suatu program yang mengambil input pada STDIN dan mencetak Trueatau Falsejika perlu.

Cobalah online

Bagaimana itu bekerja

#=-QefP_TUQ)q1  Program. Input: Q
#          )    Loop until error statement (which occurs when Q<3):
         UQ      Yield [0, 1, 2, 3, ..., Q-1]
     fP_T        Filter that by primality
    e            Yield the last element of that
 =-Q             Q = Q - that
            q1  Q is 1 (implicit variable fill)
                Implicitly print

Versi lama dengan pengurangan, 18 byte

qu-G*<HGH_fP_TSQQ1

Cobalah online

Bagaimana itu bekerja

qu-G*<HGH_fP_TSQQ1  Program. Input: Q
              SQ    Yield [1, 2, 3, ..., Q]
          fP_T      Filter that by primality
         _          Reverse it
 u                  Reduce it:
                Q    with base case Q and
                     function G, H -> 
     <HG              H<G
    *   H             *H (yields H if H<G, else 0)
  -G                  Subtract that from G
q                1  The result of that is 1
                    Implicitly print
TheBikingViking
sumber
Stis U15 chars
Maltysen
7

JavaScript (ES6), 64 63 byte

Disimpan 1 byte berkat @Neil

g=(x,n=x-1)=>n<2?x:x%n?g(x,n-1):g(x-1)
f=x=>x<3?x%2:f(x-g(x-1))

Saya menulis ini dalam 2 menit ... dan itu bekerja sempurna pertama kali. Pengguna pertama yang menemukan bug yang tidak terhindarkan akan menang ....

Cobalah

Bagaimana itu bekerja

Pertama kita mendefinisikan g (x) sebagai fungsi yang menemukan bilangan prima pertama p <= x . Ini dilakukan dengan menggunakan proses berikut:

  1. Mulai dengan n = x-1 .
  2. Jika n <2 , x adalah bilangan prima; kembali x .
  3. Jika x dapat dibagi dengan n , kurangi x dan lanjutkan ke langkah 1.
  4. Jika tidak, kurangi n dan lanjutkan ke langkah 2.

Solusi untuk tantangan ini, f (x) , sekarang cukup mudah:

  1. Jika x <3 , kembalikan x = 1 .
  2. Jika tidak, kurangi g (x-1) dan coba lagi.
Produksi ETH
sumber
4326, yang seharusnya mengembalikan true tampaknya tidak kembali, tetapi 4328 (benar) dan 4329 (salah) lakukan, apakah ini pembatasan JS atau bug?
Jonathan Allan
@JonathanAllan 4326 melempar too much recursionke konsol browser di Firefox 48, jadi saya kira rekursi melewati batas rekursi FF.
ETHproduksi
Yap, prime down berikutnya adalah 4297 (dan selanjutnya adalah 4327), itulah sebabnya 4328 bekerja.
Jonathan Allan
4
x%2akan menghemat lebih dari satu byte x==1.
Neil
@Neil Saya tidak akan pernah memikirkan itu :-)
ETHproduksi
6

Pyke, 15 11 byte

WDU#_P)e-Dt

Coba di sini!

            - stack = input
W           - while continue:
  U#_P)     -     filter(is_prime, range(stack))
       e    -    ^[-1]
 D      -   -   stack-^
         Dt -  continue = ^ != 1

Mengembalikan 1jika benar dan memunculkan pengecualian jika salah

Biru
sumber
5

Julia, 32 byte

Meskipun tidak akan menjadi solusi terpendek di antara bahasa, ini mungkin yang terpendek dari yang dapat dibaca manusia ...

!n=n>2?!(n-primes(n-1)[end]):n<2

Atau, dengan kata-kata yang sedikit lebih jelas

function !(n)
  if n>2
    m=primes(n-1)[end]   # Gets largest prime less than n
    return !(n-m)        # Recurses
  else
    return n<2           # Gives true if n is 1 and false if n is 2
  end
end

Dipanggil dengan, misalnya !37,.

Glen O
sumber
3

Mathematica, 32 byte

2>(#//.x_/;x>2:>x+NextPrime@-x)&

Ini adalah fungsi tanpa nama yang mengambil integer dan mengembalikan boolean.

Penjelasan

Ada banyak sintaks dan urutan bacaan lucu di sini, jadi ...

   #                               This is simply the argument of the function.
    //.                            This is the 'ReplaceRepeated' operator, which applies
                                   a substitution until the its left-hand argument stops
                                   changing.
       x_/;x>2                     The substitution pattern. Matches any expression x as
                                   long as that expression is greater than 2.
              :>                   Replace that with...
                  NextPrime@-x     Mathematica has a NextPrime built-in but no
                                   PreviousPrime built-in. Conveniently, NextPrime
                                   works with negative inputs and then gives you the 
                                   next "negative prime" which is basically a
                                   PreviousPrime function (just with an added minus sign).
                x+                 This gets added to x, which subtracts the previous
                                   prime from it.
2>(                           )    Finally, we check whether the result is less than 2.
Martin Ender
sumber
Ketukan dekat #+0~Min~NextPrime@-#&~FixedPoint~#==1&(36 byte). Penggunaan yang bagus //.!
Greg Martin
1
@GregMartin 35 saat Anda menggunakannya <2di akhir.
Martin Ender
3

Python3, 102 92 90 89 88 byte

f=lambda n:n<2if n<3else f(n-[x for x in range(2,n)if all(x%y for y in range(2,x))][-1])

Selamat datang saran bermain golf! Saya melihat bahwa itu gmpymengandung fungsi next_prime, tetapi saya belum bisa mengujinya :(

-2 byte, terima kasih kepada @JonathanAllan !

-1 byte, terima kasih kepada @Aaron !

Testcases

f=lambda n:n<2if n<3else f(n-[x for x in range(2,n)if all(x%y for y in range(2,x))][-1])

s="3 4 6 8 10 11 12 14 16 17 18 20 22"
h="5 7 9 13 15 19 21 25 28 31 33 36 39"

for j in s.split(" "):print(f(int(j)))
for j in h.split(" "):print(f(int(j)))

Outputnya adalah 13 nilai kebenaran dan 13 nilai palsu. sberisi kasus hkebenaran dan kesalahan.

Yytsi
sumber
1
if all(x%y for...bekerja
Jonathan Allan
1
n<3 else-> n<3elseuntuk mendapatkan panjang yang sama dengan milikku;)
Aaron
2

Python, dengan sympy, 60 byte

import sympy
f=lambda n:n>2and f(n-sympy.prevprime(n))or n<2

Metode saya sebelumnya adalah 83 byte tanpa sympy menggunakan rekursi, tetapi saya menganggap kebenaran / falsey berarti dapat dibedakan dan konsisten, tetapi saya telah diberitahu bahwa itu adalah interpretasi yang salah. Saya tidak bisa menyelamatkannya karena ekornya, tapi saya akan meninggalkannya di sini kalau-kalau ada yang tahu bagaimana melakukannya:

f=lambda n,p=0:n>2and(any(p%x==0for x in range(2,p))and f(n,p-1)or f(n-p,n+~p))or n
Jonathan Allan
sumber
@ mbomb007 Saya pikir spesifikasi "benar atau salah" jika itu diperlukan, sedangkan "benar atau salah" berarti dapat dibedakan dan konsisten?
Jonathan Allan
1
Nggak. Mereka didefinisikan saat kami memutuskan situs meta. Setiap pertanyaan yang memungkinkan output "dapat dibedakan dan konsisten" harus menentukan itu, alih-alih kebenaran / kesalahan.
mbomb007
OK saya membaca ini , akan memperbarui di beberapa titik ...
Jonathan Allan
1

Vitsy, 28 26 byte

Ini pasti bisa dipersingkat.

<]xN0)l1)-1[)/3D-];(pD-1[D

<                    Traverse the code in this direction, rotating on the line.
                     For the sake of reading the code easier, I'm reversing the
                     code on this line. This will be the order executed.

 D[1-Dp(;]-D3/)[1-)1l)0Nx]
 D                         Duplicate the top member of the stack.
  [      ]                 Do the stuff in brackets until break is called.
   1-                      Subtract 1 from the top item of the stack.
     D                     Duplicate the top member of the stack.
      p(                   If the top member is a prime...
        ;                  break;
          -                Pop a, b, push a - b.
           D3/)[         ] If this value is less than 3, do the bracketed code.
                1-         Subtract the top item of the stack by 1.
                  )        If the top item is zero...
                   1       Push 1.
                    l)     If the length of the stack is zero...
                      0    Push 0.
                       N   Output the top member of the stack.
                        x  System.exit(0);

Cobalah online!

Addison Crump
sumber
1

MATL , 13 byte

`tqZq0)-t2>}o

Cobalah online! Atau verifikasi semua kasus uji sekaligus .

Penjelasan

`        % Do...while
  t      %   Duplicate. Takes input implicitly in the first iteration
  qZq    %   All primes less than that
  0)     %   Get last one
  -      %   Subtract (this result will be used in the next iteration, if any)
  t      %   Duplicate
  2>     %   Does it exceed 2? If so: next iteration. Else: execute the "finally" 
         %   block and exit do...while loop
}        % Finally
  o      %   Parity. Transforms 2 into 0 and 1 into 1
         % End do...while implicitly
         % Display implicitly
Luis Mendo
sumber
1

CJam , 21 16 byte

Terima kasih kepada Dennis karena telah menghemat 4 byte.

ri{_1|{mp},W=-}h

Cobalah online!

Penjelasan

ri       e# Read input and convert to integer N.
{        e# Run this block as long as N is positive (or until the program aborts
         e# with an error)...
  _1|    e#   Duplicate and OR 1. This rounds up to an odd number. For N > 2, this
         e#   will never affect the greatest prime less than N.
  {mp},  e#   Get all primes from 0 to (N|1)-1.
         e#   For N > 2, this will contain all primes less than N.
         e#   For N = 2, this will contain only 2.
         e#   For N = 1, this will be empty.
  W=     e#   Select the last element (largest prime up to (N|1)-1).
         e#   For N = 1, this will result in an error and terminate the program, which
         e#   still prints the stack contents though (which are 1, the desired output).
  -      e#   Subtract from N. Note that this gives us 0 for N = 2, which terminates the 
         e#   loop.
}h
Martin Ender
sumber
ri_{_1|{mp},W=-}*harus bekerja.
Dennis
@ Dennis Terima kasih, 1|ini sangat pintar. :) (Dan saya selalu lupa bahwa {...},ada rentang implisit ...)
Martin Ender
1

Perl, 42 byte

Termasuk +1 untuk -p

Jalankan dengan input pada STDIN

reach1.pl:

#!/usr/bin/perl -p
$_=1x$_;$_=$`while/\B(?!(11+)\1+$|$)|11$/

Menggunakan regex primality klasik

Ton Hospel
sumber
1

.NET Regex, 38 byte

Hanya untuk menunjukkan bahwa itu dapat diperiksa dalam satu regex.

^(?>(?<=(.*))..+(?<!^\1\2+(.+.)|$))+.$

Input diasumsikan unary.

Penjelasan

Ini hanya mengimplementasikan persyaratan pada kata, berulang kali menghilangkan prime terbesar dan memeriksa apakah ada yang tersisa 1.

  • (?>(?<=(.*))..+(?<!^\1\2+(.+.)|$))+: Grup non-mundur memastikan prime terbesar yang kami temukan tidak diganti, dan +cukup ulangi proses pencocokan prime terbesar.

    • (?<=(.*))..+(?<!^\1\2+(.+.)|$): Cocokkan prime terbesar kurang dari jumlah yang tersisa

      • (?<=(.*)): Catat berapa banyak yang telah kita kurangi untuk menetapkan titik "jangkar" untuk penegasan.

      • ..+: Cari jumlah terbesar ...

      • (?<!^\1\2+(.+.)|$): ... yang utama dan kurang dari jumlah yang tersisa.
        • (?<!^\1\2+(.+.)): Rutin tes prima biasa, dengan ^\1ditempel di depan untuk memastikan kami memeriksa jumlah yang cocok..+
        • (?!<$): Menyatakan kurang dari jumlah yang tersisa
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
sumber
Bagian (?<=(.*))ini agak canggung. Tidak yakin apakah ada cara yang lebih baik. Saya juga ingin tahu apakah ada solusi di PCRE.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
0

Perl 6 ,  54 53 52  51 byte

{($_,{$_-($_-1...2).first: *.is-prime}...3>*)[*-1]==1}
{($_,{$_-($_-1...2).first: *.is-prime}...3>*).any==1}
{any($_,{$_-($_-1...2).first: *.is-prime}...3>*)==1}
{any($_,{$_-(^$_).grep(*.is-prime)[*-1]}...3>*)==1}

Penjelasan:

# bare block lambda with implicit parameter 「$_」
# used to generate all of the rest of the elements of the sequence
{
  # create an any Junction of the following list
  any(
    $_, # initialize sequence with the inner block's argument

    # bare block lambda with implicit parameter 「$_」
    {
      # take this inner block's argument and subtract
      $_ -

      ( ^$_ )            # Range up-to and excluding 「$_」
      .grep(*.is-prime)\ # find the primes
      [ * - 1 ]          # return the last value
    }

    ...   # keep doing that until

    3 > * # the result is less than 3

  # test that Junction against 「1」
  # ( returns an 「any」 Junction like 「any(False, False, True)」 )
  ) == 1
}

Contoh:

# show what is returned and if it is truthy
sub show ($_) {
  # 「.&{…}」 uses the block as a method and implicitly against 「$_」
  my $value = .&{any($_,{$_-(^$_).grep(*.is-prime)[*-1]}...3>*)==1}
  say join "\t", $_, ?$value, $value.gist;
}

show 3;  # 3    True    any(False, True)
show 4;  # 4    True    any(False, True)
show 5;  # 5    False   any(False, False)
show 10; # 10   True    any(False, False, True)
show 28; # 28   False   any(False, False, False)
show 49; # 49   False   any(False, False)
show 50; # 50   True    any(False, False, True)
Brad Gilbert b2gills
sumber
0

Tidak teratur , 63 byte

p~?1_$-1p:;
n=i(0)?1_$-1p:;
_~
N=n
1(?!(11+)\1+$)11+~1
^11$~0
N

Saya membuat bahasa ini dua hari yang lalu, dan premis dasarnya adalah bahwa tidak ada loop bawaan, satu-satunya fitur adalah aritmatika dasar dan pengambilan keputusan, dan evaluasi program didasarkan pada ekspresi reguler.

Penjelasan

p~?1_$-1p:;
n=i(0)?1_$-1p:;
_~
N=n

Bagian ini mengubah input menjadi unary. Itu berulang kali mengurangi 1 dari input sampai sama dengan 0, prapengganti 1_setiap waktu. Itu kemudian menghapus semua _s. Jika saya tidak lupa a breakdalam kode saya itu bisa ditulis sebagai:

p~?1_$-1p:;
_~
n=i(0)?1_$-1p:;

Bagian berikutnya berulang kali menghapus perdana terbesar dari input sampai sama dengan 1atau 11, dengan 11diganti 0.

1(?!(11+)\1+$)11+~1
^11$~0
N

Saya menggunakan regex dari jawaban Martin Ender .

DanTheMan
sumber
0

Haskell, 79 byte

Tidak terlalu pendek tapi pointfree :)

(<2).until(<3)(until(flip(`until`(+1))2.(.)(<1).mod>>=(==))pred.pred>>=flip(-))
Damien
sumber
0

PowerShell v2 +, 81 byte

param($n)while($n-gt2){$n-=(($n-1)..2|?{'1'*$_-match'^(?!(..+)\1+$)..'})[0]}!--$n

Mengambil input $n. Memasuki whileloop selama $nmasih 3atau lebih besar. Setiap iterasi, kurangi satu angka dari $n. Angka tersebut adalah hasil uji primality regex yang diterapkan terhadap suatu rentang ($n-1)..2melalui operator Where-Object( ?), kemudian yang pertama [0]dari hasil (karena kisarannya menurun, ini menghasilkan yang terbesar yang dipilih). Setelah menyimpulkan loop, $napakah akan menjadi 1atau 2, dengan definisi, jadi kita pra-pengurangan $n(mengubahnya menjadi salah satu 0atau 1), dan mengambil Boolean-bukan !darinya. Yang tersisa pada pipa dan output tersirat.

Contohnya

PS C:\Tools\Scripts\golfing> 3..20|%{"$_ --> "+(.\can-the-number-reach-one.ps1 $_)}
3 --> True
4 --> True
5 --> False
6 --> True
7 --> False
8 --> True
9 --> False
10 --> True
11 --> True
12 --> True
13 --> False
14 --> True
15 --> False
16 --> True
17 --> True
18 --> True
19 --> False
20 --> True
AdmBorkBork
sumber
0

Matlab, 51 byte

v=@(x)x-max(primes(x-1));while(x>=3)x=v(x);end;x==1

Ini SANGAT mirip dengan solusi JS6 oleh ETHProductions , tetapi perlu variabel berada di ruang kerja.

ptev
sumber
0

Python 2.7: 88 87 Bytes

r=lambda n:n>2and r(n-[a for a in range(2,n)if all(a%b for b in range(2,a))][-1])or n<2

Thx @TuukkaX untuk -1 byte lebih banyak!

Harun
sumber
1
Perbarui deskripsi Anda;) Juga, Anda dapat menyimpan satu byte dengan mengatakan n<2alih-alih n==1.
Yytsi
0

Floroid , 45 30 29 byte

f=Bb:b<2Fb<3Gf(b-en(b-1)[-1])
Yytsi
sumber
0

Clojure, 125 byte

#(loop[x %](if(> x 2)(recur(- x(loop[y(dec x)](if(some zero?(vec(for[z(range 2 y)](mod y z))))(recur(dec y))y))))(quot 1 x)))

Astaga, itu adalah sepotong kode. Bahasa yang paling verbal menyerang lagi!

Tidak Disatukan:

(defn subprime [n]
  (loop [x n]
    (if (> x 2)
      (recur
        (- x
          (loop [y (dec x)]
            (if (some zero? (vec (for [z (range 2 y)] (mod y z))))
              (recur (dec y)) y))))
      (quot 1 x))))
clismique
sumber