Apakah saya nomor 'Redivosit'?

26

Redivosite adalah kata portmanteau yang diciptakan untuk tujuan tunggal tantangan ini. Ini campuran Reduksi, Divisi dan Komposit.

Definisi

Diberikan bilangan bulat N> 6 :

  • Jika N adalah prima, N bukan Nomor Redivosite.
  • Jika N adalah komposit:
    • berulang kali menghitung N '= N / d + d + 1 sampai N' adalah prima, di mana d adalah pembagi terkecil dari N lebih besar dari 1
    • N adalah Nomor Redivosite jika dan hanya jika nilai akhir N ' adalah pembagi N

Di bawah ini adalah 100 Nomor Redivosite pertama (tidak ada entri OEIS pada saat posting):

14,42,44,49,66,70,143,153,168,169,176,195,204,260,287,294,322,350,414,462,518,553,572,575,592,629,651,702,726,735,775,806,850,869,889,891,913,950,1014,1023,1027,1071,1118,1173,1177,1197,1221,1235,1254,1260,1302,1364,1403,1430,1441,1554,1598,1610,1615,1628,1650,1673,1683,1687,1690,1703,1710,1736,1771,1840,1957,1974,2046,2067,2139,2196,2231,2254,2257,2288,2310,2318,2353,2392,2409,2432,2480,2522,2544,2635,2640,2650,2652,2684,2717,2758,2760,2784,2822,2835

Contohnya

  • N = 13:13 adalah bilangan prima, jadi 13 bukan Angka Redivosite
  • N = 32 : 32/2 + 3 = 19; 19 bukan pembagi atau 32, jadi 32 bukan Nomor Redivosite
  • N = 260 : 260/2 + 3 = 133, 133/7 + 8 = 27, 27/3 + 4 = 13; 13 adalah pembagi atau 260, jadi 260 adalah Nomor Redivosite

Tugas Anda

  • Dengan bilangan bulat N , kembalikan nilai kebenaran jika itu adalah Nomor Redivosite atau nilai palsu. (Anda juga dapat menampilkan dua nilai yang berbeda, asalkan konsisten.)
  • Input dijamin lebih besar dari 6 .
  • Ini kode-golf , jadi jawaban tersingkat dalam byte menang!
code-golf decision-problem integer division Arnauld
sumber
13
Saya benar-benar berharap semua tantangan "urutan nomor" yang hanya urutan angka dengan properti tertentu hanya akan ditanyakan sebagai masalah keputusan. Saya sangat ragu ada cara untuk menghasilkan ini secara langsung, jadi satu-satunya solusi yang mungkin adalah menyelesaikan masalah keputusan dan kemudian membungkusnya dalam satu lingkaran yang menemukan N atau N pertama atau semua bilangan bulat yang memenuhi properti ini.
Martin Ender
3
Saya suka tantangan urutan yang bukan masalah keputusan secara umum, tetapi untuk yang ini saya pikir masalah keputusan akan lebih cocok. Saya tidak melihat hubungan antara istilah sehingga Anda mencetak n th atau yang pertama n dengan cara yang cerdas, jadi mungkin memungkinkan mengambil n sebagai masukan dan memeriksa jika redivosite ?
Tn. Xcoder
1
@ MartinEnder & Mr.Xcoder Itulah niat awal saya (maka judul aslinya yang baru saja saya kembalikan) dan saya berubah pikiran. Saya kira ini seharusnya tidak merusak solusi WIP (untuk alasan yang Anda katakan), jadi saya sudah mengeditnya.
Arnauld
5
@ Mr.Xcoder Ya, itulah yang saya maksud. Saya tidak keberatan dengan urutan tantangan yang sebenarnya masuk akal sebagai urutan (baik karena Anda dapat menghitung a(n)secara langsung, atau karena Anda dapat menghitung istilah dari yang sebelumnya). Terima kasih, Arnauld, untuk mengubah tantangan. :)
Martin Ender

Jawaban:

9

Haskell, 91 85 83 80 75 74 byte

n#m=([n#(div m d+d+1)|d<-[2..m-1],mod m d<1]++[mod n m<1&&m<n])!!0
f x=x#x

Cobalah online!

f x=x#x                           -- call # with x for both parameters
n#m               
         |d<-[2..m-1],mod m d<1   -- for all divisors d of m
    [n#(div m d+d+1)           ]  -- make a list of recursive calls to #,
                                  -- but with m set to m/d+d+1
   ++ [mod n m<1&&m<n]            -- append the Redivosite-ness of n (m divides n,
                                  -- but is not equal to n)
                           !!0    -- pick the last element of the list
                                  -- -> if there's no d, i.e. m is prime, the
                                  --    Redivosite value is picked, else the
                                  --    result of the call to # with the smallest d

Sunting: -2 bytes berkat @BMO, -3 bytes berkat @ H.PWiz dan -5 -6 bytes berkat @ Ørjan Johansen

nimi
sumber
2
75 byte
Ørjan Johansen
Sebenarnya, buatlah 74
Ørjan Johansen
@ ØrjanJohansen: Terima kasih lagi.
nimi
6

Sekam , 14 byte

?¬Ṡ¦ΩṗoΓ~+→Πpṗ

Cobalah online!

-3 Terima kasih kepada H.PWiz .

Erik the Outgolfer
sumber
14 byte dengan fungsi pembersih di dalamΩ
H.PWiz
@ H.PWiz tidak bisa mengerti Γ...
Erik the Outgolfer
Di sini Γ, diberikan daftar [a, b, c ...] akan berlaku ~+→Πuntuk adan [b,c...]. ~+→Πmenambahkan a+1ke product[b,c...]. aadalah pembagi terkecil, product[b,c...]adalahN/d
H.PWiz
@ H.PWiz Dan saya memang berpikir untuk menggunakan faktor prima ...
Erik the Outgolfer
6

C (gcc) , 94 89 byte

m,n;o(k){for(m=1;m++<k;)if(k%m<1)return m;}
F(N){for(n=N;m=o(n),m-n;n=n/m-~m);N=m<N>N%n;}

Cobalah online!

Penjelasan

m,n;                  // two global integers
o(k){                 // determine k's smallest divisor
 for(m=1;m++<k;)      // loop through integers 2 to n (inclusive)
  if(k%m<1)return m;} // return found divisor
F(N){                 // determine N's redivosity
 for(n=N;             // save N's initial value
  m=o(n),             // calculate n's smallest divisor (no name clash regarding m)
  m-n;                // loop while o(n)!=n, meaning n is not prime
                      //  (if N was prime, the loop will never be entered)
  n=n/m-~m);          // redivosite procedure, empty loop body
 N=m<N>N%n;}          // m<N evaluates to 0 or 1 depending on N being prime,
                      //  N%n==0 determines whether or not N is divisible by n,
                      //  meaning N could be redivosite => m<N&&N%n==0
                      //  <=> m<N&&N%n<1 <=> m<N&&1>N%n <=> (m<N)>N%n <=> m<N>N%n
Jonathan Frech
sumber
4

Jelly , 14 byte

ÆḌḊ
Ç.ịS‘µÇ¿eÇ

Cobalah online!

Bagaimana itu bekerja

ÆḌḊ         Helper link. Argument: k

ÆḌ          Yield k's proper (including 1, but not k) divisors.
  Ḋ         Dequeue; remove the first element (1).


Ç.ịS‘µÇ¿eÇ  Main link. Argument: n

     µ      Combine the links to the left into a chain.
      Ç¿    While the helper link, called with argument n, returns a truthy result,
            i.e., while n is composite, call the chain to the left and update n.
Ç             Call the helper link.
 .ị           At-index 0.5; return the elements at indices 0 (last) and 1 (first).
              This yields [n/d, d].
   S          Take the sum.
    ‘         Increment.
        Ç   Call the helper link on the original value of n.
       e    Test if the result of the while loop belongs to the proper divisors.
Dennis
sumber
4

Python 2 , 97 91 byte

r=0;e=d=i=input()
while r-e:e=i;r=[j for j in range(2,i+1)if i%j<1][0];i=i/r-~r
d%e<1<d/e<q

Cobalah online!

Keluaran melalui kode keluar.

Tidak Disatukan:

r = 0                             # r is the lowest divisor of the current number,
                                  # initialized to 0 for the while loop condition.
e = d = i = input()               # d remains unchanged, e is the current number
                                  # and i is the next number.
while r != e:                     # If the number is equal to its lowest divisor,
                                  # it is prime and we need to end the loop.
    e = i                         # current number := next number
    r = [j for j in range(2, i+1) # List all divisors of the number in the range [2; number + 1)
         if i%j < 1][0]           # and take the first (lowest) one.
    i = i/r+r+1                   # Calculate the next number.
                                  # We now arrived at a prime number.
print d%e == 0 and d != e         # Print True if our current number divides the input
                                  # and is distinct from the input.
                                  # If our current number is equal to the input,
                                  # the input is prime.

Cobalah online!

ovs
sumber
3

05AB1E , 17 16 byte

[Dp#Òć©sP+>]Ö®p*

Cobalah online!

Penjelasan

[                  # start loop
 Dp#               # break if current value is prime
    Ò              # get prime factors of current value
     ć©            # extract the smallest (d) and store a copy in register
       sP          # take the product of the rest of the factors
         +>        # add the smallest (d) and increment
           ]       # end loop
            Ö      # check if the input is divisible by the resulting prime
             ®p    # check if the last (d) is prime (true for all composite input)
               *   # multiply
Emigna
sumber
2

Pyth , 20 byte

<P_QiI.WtPHh+/ZKhPZK

Coba di sini!

Bagaimana itu bekerja

iI.WtPHh + / ZKhPZK || Program lengkap.

  .W || Sementara fungsional. Dibutuhkan dua fungsi sebagai argumen, A dan B.
                 || Sementara A (nilai) benar, ubah nilainya menjadi B (nilai). Itu
                 || nilai awal adalah input.
    tPH || Fungsi pertama, A. Membawa argumen tunggal, H.
     PH || .. Faktor utama faktor H.
    t || .. Tail (hapus elemen pertama). Sedangkan kebenaran (H adalah gabungan):
       h + / ZKhPZK || Fungsi kedua, B. Membawa argumen tunggal, Z:
         / Z || .. Divide Z, oleh:
           KhP || .. Faktor prima terendah, dan menetapkan itu untuk K.   
       h || .. Penambahan.
        + K || Dan tambahkan K.
iI || Periksa apakah hasilnya (nilai terakhir) membagi input.

Dan 4 byte pertama ( <P_Q) cukup periksa apakah inputnya tidak prima.

Dengan bantuan dari Emigna , saya berhasil menghemat 3 byte.

Tuan Xcoder
sumber
Bisakah Anda menggunakan sesuatu seperti head(P)bukan fiITZ2bagian, karena pembagi terkecil yang lebih besar dari 1 akan selalu menjadi prima?
Emigna
@Emigna Ninja, diperbaiki dan terima kasih!
Tn. Xcoder
2

Python 3 , 149 byte

def f(N):
	n=N;s=[0]*-~N
	for p in range(2,N):
		if s[p]<1:
			for q in range(p*p,N+1,p):s[q]=s[q]or p
	while s[n]:n=n//s[n]-~s[n]
	return s[N]>1>N%n

Cobalah online!

Menggunakan pendekatan saringan. Harus cepat ( O(N log log N)= kompleksitas waktu saringan Eratosthenes) bahkan dengan besar N(tetapi menyimpan O(N)bilangan bulat dalam memori)

catatan:

  • Dapat dibuktikan bahwa semua nilai antara ntidak melebihi N, dan untuk N > 7 pdapat di range(2,N)bukan range(2,N+1)untuk pengayakan.
  • /tidak berfungsi, //harus digunakan, karena indeks daftar.
  • Menyimpan rangeke variabel lain tidak membantu, sayangnya.

Penjelasan:

  • -~N== N+1.
  • Pada awalnya, array sdiinisialisasi dengan N+1nol (Python adalah pengindeksan 0, jadi indeksnya adalah 0..N)
  • Setelah inisialisasi, s[n]diharapkan 0jika nperdana, dan puntuk pperdana minimum yang membagi njika nmerupakan komposit. s[0]dan s[1]nilai tidak penting.

  • Untuk masing-masing pdalam kisaran [2 .. N-1]:

    • Jika s[p] < 1(yaitu, s[p] == 0), maka padalah bilangan prima, dan untuk masing-masing qmerupakan kelipatan dari pdan s[q] == 0, tetapkan s[q] = p.

  • 2 baris terakhir mudah, kecuali n//s[n]-~s[n]== (n // s[n]) + s[n] + 1.

Python 3 , 118 byte

def f(N):
	n=N;s=[0]*-~N
	for p in range(N,1,-1):s[2*p::p]=(N-p)//p*[p]
	while s[n]:n=n//s[n]-~s[n]
	return s[N]>1>N%n

Cobalah online!

Dengan biaya kinerja yang sedikit lebih buruk. (Yang ini berjalan dalam O(N log N)kompleksitas waktu, menganggap implementasi yang wajar dari irisan Python)

Program lengkap yang setara adalah 117 byte .

pengguna202729
sumber
Anda dapat menggunakan n//s[n]-~s[n]alih-alih n//s[n]+s[n]+1untuk 149 byte.
Tn. Xcoder
@ Mr.Xcoder Terima kasih!
user202729
Saya pikir or pjuga bisa|p
Tn. Xcoder
@ Mr.Xcoder Tidak, or pmelakukan logis atau, saat |pmelakukan bitwise atau. Artinya, a or badalah b if a == 0 else a.
user202729
Anda dapat memodifikasi bagian luar foruntuk menggunakan irisan yang lainfor . The rangedibalik, sehingga indeks lebih rendah akan menimpa orang-orang yang lebih besar, dan mulai slice di 2*pAnda tidak akan mengganti s[0]atau s[p].
Rod
1

Haskell , 110 byte

f n|mod(product[1..n-1]^2)n>0=1<0|1>0=n`mod`u n<1
u n|d<-[i|i<-[2..],n`mod`i<1]!!0=last$n:[u$n`div`d+d+1|d/=n]

Cobalah online!

Tidak terlalu senang ...

benar-benar manusiawi
sumber
1

Oktaf , 92 byte

function r=f(n)k=n;while~isprime(k)l=2:k;d=l(~mod(k,l))(1);k=k/d+d+1;end;r=~mod(n,k)&k<n;end

Cobalah online!

Steadybox
sumber
1

Japt, 25 24 byte

Saya khawatir saya mungkin salah arah dengan ini, tetapi saya kehabisan waktu untuk mencoba pendekatan yang berbeda.

Output 0untuk false atau 1true.

j ?V©vU :ßU/(U=k g)+°UNg

Cobalah

Shaggy
sumber
0

Perl 5 , 291 +1 (-a) = 292 byte

Sial Perl karena tidak memiliki pemeriksa prima asli. 

use POSIX;&r($_,$_);
sub p{$n=shift;if($n<=1){return;}if($n==2||$n==3){return 1;}if($n%2==0||$n%3==0){return;}for(5..ceil($n/2)){if($n%$_==0){return;}}return 1;}
sub r{$n=shift;$o=shift;if(&p($n)){print $o%$n==0&&$n!=$o?1:0;last;}for(2..ceil($n/2)){if($n%$_==0){&r(($n/$_)+$_+1, $o);last;}}}

Versi tidak disatukan,

use POSIX;
&r($_,$_);
sub p{
    my $n=shift;
    if($n<=1){
        return;
    }
    if($n==2||$n==3){
        return 1;
    }
    if($n%2==0||$n%3==0){
        return;
    }
    for(5..ceil($n/2)){
        if($n%$_==0){
            return;
        }
    }
    return 1;
}
sub r{
    my $n=shift;
    my $o=shift;
    if(&p($n)){
        print $o%$n==0&&$n!=$o ? 1 : 0;
        last;
    }
    for(2..ceil($n/2)){
        if($n%$_==0){
            &r(($n/$_)+$_+1, $o);
            last;
        }
    }
}

Cobalah online!

Geoffrey H.
sumber
0

Bahasa Wolfram (Mathematica) , 64 byte

Implementasi langsung menggunakan penggantian pola rekursif

(mengganti "\ [Membagi]" dengan simbol "∣" menghemat 7 byte)

(g=!PrimeQ@#&)@#&&(#//.x_/;g@x:>x/(c=Divisors[x][[2]])+c+1)\[Divides]#&

Cobalah online!

Kelly Lowder
sumber
0

Bersih , 128 117 114 byte

import StdEnv
@n#v=hd[p\\p<-[2..]|and[gcd p i<2\\i<-[2..p-1]]&&n rem p<1]
|v<n= @(n/v+v+1)=n
?n= @n<n&&n rem(@n)<1

Cobalah online!

Suram
sumber
0

J , 35 byte

(~:*0=|~)(1+d+]%d=.0{q:)^:(0&p:)^:_

Cobalah online!

Pembagi minimum yang menjadi faktor utama pertama dicuri dari solusi @ Dennis's Jelly (sebelumnya saya gunakan <./@q:).

Seharusnya ada cara yang lebih baik untuk melakukan iterasi, tetapi sepertinya saya tidak dapat menemukannya. Saya berpikir untuk menghindari melakukan tes primality ( ^:(0&p:)) dan bukannya menggunakan yang merugikan tetapi sepertinya itu akan sedikit lebih lama karena Anda akan membutuhkan _2{dan beberapa perubahan yang mungkin tidak memberikan pengurangan bersih.

Saya benar-benar merasa harus ada cara untuk menghindari memiliki orang tua di sekitar pemeriksaan primality juga.

Penjelasan (diperluas)

(~: * 0 = |~)(1 + d + ] % d =. 0 { q:) ^: (0&p:) ^:_ Input: N
             (1 + d + ] % d =. 0 { q:) ^: (0&p:) ^:_ Find the final N'
                                       ^:        ^:_  Do while
                                           0&p:       N is not prime
                                   q:                 Get prime factors (in order)
                               0 {                    Take first (smallest divisor)
                          d =.                        Assign this value to d
             1 + d + ] %  d                           Compute (N/d) + 1 + d
(~: * 0 = |~)                                        Is it redivosite?
      0 = |~                                          N = 0 (mod N'), i.e. N'|N
    *                                                 And
 ~:                                                   N =/= N', i.e. N is not prime
cole
sumber
0

APL NARS, 43 karakter, 85 byte

{(⍵≤6)∨0π⍵:0⋄⍵{1=⍴t←π⍵:0=⍵|⍺⋄⍺∇1+↑t+⍵÷↑t}⍵}

(berharap konvergen untuk semua angka> 6) menguji:

h←{(⍵≤6)∨0π⍵:0⋄⍵{1=⍴t←π⍵:0=⍵|⍺⋄⍺∇1+↑t+⍵÷↑t}⍵}
v←⍳100     
v,¨h¨v
   1 0  2 0  3 0  4 0  5 0  6 0  7 0  8 0  9 0  10 0  11 0
   12 0  13 0  14 1  15 0  16 0  17 0  18 0  19 0  20 0  
   21 0  22 0  23 0  24 0  25 0  26 0  27 0  28 0  29 0  
   30 0  31 0  32 0  33 0  34 0  35 0  36 0  37 0  38 0  
   39 0  40 0  41 0  42 1  43 0  44 1  45 0  46 0  47 0  
   48 0  49 1  50 0  51 0  52 0  53 0  54 0  55 0  56 0  
   57 0  58 0  59 0  60 0  61 0  62 0  63 0  64 0  65 0  
   66 1  67 0  68 0  69 0  70 1  71 0  72 0  73 0  74 0  
   75 0  76 0  77 0  78 0  79 0  80 0  81 0  82 0  83 0  
   84 0  85 0  86 0  87 0  88 0  89 0  90 0  91 0  92 0  
   93 0  94 0  95 0  96 0  97 0  98 0  99 0  100 0

Gagasan menggunakan 2 fungsi anonim saya dapatkan untuk solusi APL lainnya.

 {(⍵≤60)∨π⍵:0⋄ -- if arg ⍵ is prime or <=6 return 0
  ⍵{1=⍴t←π⍵:0=⍵|⍺⋄ -- if list of factors ⍵ has length 1 (it is prime)
                    -- then return ⍺mod⍵==0
  ⍺∇1+↑t+⍵÷↑t}⍵}   -- else recall this function with args ⍺ and 1+↑t+⍵÷↑t
RosLuP
sumber
0

Pyt , 44 byte

←⁻0`ŕ⁺ĐĐϼ↓Đ3Ș⇹÷+⁺Đṗ¬⇹⁻⇹łŕáĐ0⦋Đ↔ĐŁ⁻⦋⁺|¬⇹ṗ⇹3Ș⊽

Lihat kode di bawah ini untuk penjelasan - satu-satunya perbedaan adalah (1) bahwa N dikurangi sebelum memperhitungkan kenaikan pada awal loop, dan (2) menggunakan NOR bukannya OR.

Cobalah online!


Saya membuat ini sebelum saya membaca kembali pertanyaan dan memperhatikan bahwa itu hanya ingin benar / salah.

Pyt, 52 byte

60`ŕ⁺ĐĐϼ↓Đ3Ș⇹÷+⁺Đṗ¬⇹⁻⇹łŕáĐ0⦋Đ↔ĐŁ⁻⦋⁺|¬⇹Đṗ⇹3Ș∨ł⇹Đƥ⇹ŕ1ł

Mencetak daftar angka Redivosite yang tak terbatas.

Penjelasan:

6                                                            Push 6
 0                                                           Push unused character
  `                   ł                     ł      ł         Return point for all three loops
   ŕ                                                         Remove top of stack
    ⁺                                                        Increment top of stack (n)
     ĐĐ                                                      Triplicate top of stack (n)
       ϼ↓                                                    Get smallest prime factor of n (returns 1 if n is prime) 
         Đ                                                   Duplicate top of stack
          3Ș⇹                                                Manipulate stack so that the top is (in descending order): [d,(N,N'),d]
             ÷+⁺                                             Calculates N'=(N,N')/d+d+1
                Đṗ¬                                          Is N' not prime?
                   ⇹⁻⇹                                       Decrement N' (so the increment at the beginning doesn't change the value), and keep the boolean on top - end of innermost loop (it loops if top of stack is true)
                       ŕ                                     Remove top of stack
                        á                                    Convert stack to array
                         Đ                                   Duplicate array
                          0⦋Đ                                Get the first element (N)
                             ↔ĐŁ⁻⦋                           Get the last element ((final N')-1)
                                  ⁺                          Increment to get (final N')
                                   |¬                        Does N' not divide N?
                                     ⇹Đṗ                     Is N prime?
                                        ⇹3Ș∨                 Is N prime or does N' not divide N? - end of second loop (loops if top of stack is true)
                                             ⇹Đƥ⇹ŕ           Print N, and reduce stack to [N]
                                                  1          Push garbage (pushes 1 so that the outermost loop does not terminate)


Cobalah online!

mudkip201
sumber