Basis Tanpa Kekeruhan Terkecil

28

Diberikan bilangan bulat positif n, output basis terkecil di b >= 2mana representasi ndalam basis btanpa nol terkemuka tidak mengandung a 0. Anda dapat mengasumsikan bahwa b <= 256untuk semua input.

Uji Kasus

1 -> 2 (1)
2 -> 3 (2)
3 -> 2 (11)
4 -> 3 (11)
5 -> 3 (12)
6 -> 4 (12)
7 -> 2 (111)
10 -> 4 (22)
17 -> 3 (122)
20 -> 6 (32)
50 -> 3 (1212)
100 -> 6 (244)
777 -> 6 (3333)
999 -> 4 (33213)
1000 -> 6 (4344)
1179360 -> 23 ([12, 9, 21, 4, 4])
232792560 -> 23 ([15, 12, 2, 20, 3, 13, 1])
2329089562800 -> 31 ([20, 3, 18, 2, 24, 9, 20, 22, 2])
69720375229712477164533808935312303556800 -> 101 ([37, 17, 10, 60, 39, 32, 21, 87, 80, 71, 82, 14, 68, 99, 95, 4, 53, 44, 10, 72, 5])
8337245403447921335829504375888192675135162254454825924977726845769444687965016467695833282339504042669808000 -> 256 ([128, 153, 236, 224, 97, 21, 177, 119, 159, 45, 133, 161, 113, 172, 138, 130, 229, 183, 58, 35, 99, 184, 186, 197, 207, 20, 183, 191, 181, 250, 130, 153, 230, 61, 136, 142, 35, 54, 199, 213, 170, 214, 139, 202, 140, 3])
Mego
sumber
1
Apa nilai untuk sepuluh, sebelas, dll. Di pangkalan yang lebih tinggi yang Anda gunakan? Apakah mengandung nol?
Stephen
19
@Stephen Nilai yang dipilih untuk digit di atas 9tidak masalah, karena tidak 0.
Mego
9
Ini adalah OEIS A106370 .
Engineer Toast
1
@Itus Itu poin yang bagus. Saya akan membatasi basis untuk sesuatu yang masuk akal.
Mego
1
@Mego: Coba 232792560. Ini adalah lcm dari 2,3, ..., 20, jadi di setiap basis <= 20 memiliki 0 sebagai digit paling tidak signifikan.
Nate Eldredge

Jawaban:

15

Pyth , 6 byte

f*FjQT

Verifikasi semua kasus uji.

Bagaimana itu bekerja

f * FjQT ~ Program lengkap.

f ~ bilangan bulat positif pertama yang kondisinya benar.
   jQT ~ Input dikonversi ke basis elemen saat ini.
 * F ~ Produk. Jika daftar itu berisi 0, maka itu 0, kalau tidak itu pasti positif.
          0 -> Falsy; > 0 -> Sebenarnya.
        ~ Keluarkan hasilnya secara implisit.

Meskipun Pyth fberoperasi pada 1, 2, 3, 4, ...(mulai dari 1), Pyth memperlakukan angka dalam basis 1 (unary) sebagai sekelompok nol, sehingga basis 1 diabaikan.

Tuan Xcoder
sumber
Penyalahgunaan fakta bahwa representasi base-1 Pyth bagus sekali.
Erik the Outgolfer
@EriktheOutgolfer Terima kasih! Saya akan menambahkan penjelasan tentang itu.
Tn. Xcoder
Pyth bukan satu-satunya bahasa yang perwakilan unarynya menggunakan nol sebagai petunjuk angka : P
Mego
Anda menulis 0 -> Falsy; > 0 -> Truthy. Apakah itu disengaja yang 0bersifat Truthydan Falsydalam situasi itu?
Brian J
@BrianJ Ada >tanda di depan yang kedua 0, yang berarti segala sesuatu yang lebih tinggi dari 0 adalah benar.
Tn. Xcoder
11

C,  52  50 byte

i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;return i;}

Cobalah online!

C (gcc),  47  45 byte

i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;n=i;}

Cobalah online!


Dua byte disimpan berkat saran @ Nevay pada jawaban @Kevin Cruijssen!

Steadybox
sumber
2
Versi terakhir hanya berfungsi dengan keberuntungan acak, bahkan jika Anda bersikeras pada kompiler tertentu. Dan, tentu saja, tidak ada versi yang benar-benar C.
AnT
3
@ ANT itu C .. itu akan memberikan banyak peringatan tetapi akan dikompilasi. selama Anda menemukan kompiler yang berfungsi untuk kode Anda, Anda baik
Felipe Nardi Batista
1
@ Blacksilver k%iadalah cek ternary di sini. Sebuah varian lebih mudah dibaca akan k=(k%i?k:n*++i);atau bahkan lebih jelas: if(k%i){k=k;}else{k=n*++i;}.
Kevin Cruijssen
1
Anda juga dapat bermain golf dengan 2 byte: i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;return i;}dan i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;n=i;}. Semua kredit jatuh ke @Nevay yang memposting saran ini pada jawaban Java 8 porting saya .
Kevin Cruijssen
1
@Felipe Nardi Batista: Saya mengetahui fakta bahwa aturan CodeGolf mengatakan "selama dikompilasi" dan seterusnya. Namun, fakta bahwa ia "mengkompilasi" tidak dengan cara apa pun membuktikan bahwa itu adalah C. Ini bukan C. Deklarasi tipikal seperti i, k;dan f(n)ada dalam versi kuno C (K&R), tetapi hanya di era ketika returndiperlukan tanda kurung bundar di sekelilingnya. argumen. Jika Anda ingin menggunakan K&R i,k;, Anda juga harus menggunakannya return(i);. Di atas mungkin gnuc, tetapi bukan C.
AnT
8

Haskell , 56 52 48 byte

b#n=n<1||mod n b>0&&b#div n b
f n=until(#n)(+1)2

Cobalah online!

Cukup mendasar tetapi tidak bisa memikirkan cara yang baik untuk mempersingkatnya

EDIT: Terima kasih kepada Laikoni karena telah menyelamatkan saya 4 byte! Tidak tahu mengapa saya tidak pernah memikirkannya !!0. Saya mungkin harus mencoba menghapus tanda kurung itu tetapi saya memiliki kenangan samar-samar dari beberapa kesalahan aneh ketika Anda mencoba untuk menggunakan ||dan &&bersama - sama. Mungkin saya bingung dengan operator kesetaraan.

EDIT 2: Terima kasih @Lynn karena telah mencukur 4 byte lagi! Tidak tahu bagaimana saya tidak pernah tahu untilsebelumnya.

pengguna1472751
sumber
1
Anda mengalahkan saya semenit dengan solusi yang hampir persis sama. :) !!0lebih pendek dari headdan saya pikir Anda bisa drop kurung di #.
Laikoni
2
Penjahat yang diremehkan until :: (a → Bool) → (a → a) → a → amenghemat empat byte:f n=until(#n)(+1)2
Lynn
6

Sekam , 7 byte

→V▼MBtN

Cobalah online!

Penjelasan

→V▼MBtN
     tN    list of natural numbers starting from 2
   MB      convert the (implicit) input to each of those bases
 V▼        find the (1-based) index of the first result where the minimum digit is truthy
→          add 1 to this index
Leo
sumber
5

Python 2 , 57 byte

n=x=input()
b=2
while x:z=x%b<1;b+=z;x=[x/b,n][z]
print b

Cobalah online!

Ini satu byte lebih pendek dari fungsi rekursif:

f=lambda n,b=1,x=1:b*(x<1)or f(n,b+(x%b<1),[x/b,n][x%b<1])
Lynn
sumber
1
BTW ini sangat mirip dengan solusi saya.
Erik the Outgolfer
3

05AB1E , 6 byte

-4 byte terima kasih kepada Adnan

1µNвPĀ

Cobalah online!

Okx
sumber
10 byte:[¹NÌDŠвPĀ#
Neil
2
1µNвPĀ bekerja selama 6 byte
Adnan
@ Adnan aku tahu itu terlalu lama
Okx
LB0.å0kadalah metode lain seluruhnya> _>.
Magic Gurita Guci
3

Sekam , 9 byte

←foΠ`B⁰tN

Cobalah online!

Penjelasan

            -- input N
        tN  -- tail of [1..] == [2..]
←f(    )    -- filter with the following:
    `B⁰     --   convert N to that base
   Π        --   product (0 if it contains 0)
←           -- only keep first element
ბიმო
sumber
3

Java 8, 61 56 54 byte

n->{int b=2,t=n;for(;t>0;)t=t%b++<1?n:t/--b;return b;}

Coba di sini.

Penjelasan:

n->{            // Method with integer as both parameter and return-type
  int b=2,      //  Base-integer, starting at 2
      t=n;      //  Temp-integer, copy of the input
  for(;t>0;)    //  Loop as long as `t` is not 0
    t=t%b++<1?  //   If `t` is divisible by the base `b`
                //   (and increase the base `b` by 1 afterwards with `b++`)
       n        //    Set `t` to the input `n`
      :         //   Else:
       t/--b;   //    Divide `t` by the `b-1`
                //    (by decreasing the base `b` by 1 first with `--b`)
                //  End of loop (implicit / single-line body)
  return b;     //  Return the resulting base
}               // End of method

Saya punya perasaan ini bisa golf dengan menggunakan pendekatan aritmatika. Memang bisa, dengan porta jawaban @Steadybox 'C , dan kemudian di-golf 2 byte berkat @Nevay .

Lama (Jawaban 61 byte ):

n->{int b=1;for(;n.toString(n,++b).contains("0"););return b;}

Coba di sini.

Penjelasan:

n->{         // Method with Integer as both parameter and return-type
  int b=1;   //  Base-integer, starting at 1
  for(;n.toString(n,++b).contains("0"););
             //  Loop as long as the input in base-`b` does contain a 0,
             //  after we've first increased `b` by 1 before every iteration with `++b`
  return b;  //  Return the resulting base
}            // End of method
Kevin Cruijssen
sumber
2
54 byte:n->{int b=2,t=n;for(;t>0;)t=t%b++<1?n:t/--b;return b;}
Nevay
2

Japt , 8 byte

@ìX e}a2

Cobalah online!

Penjelasan

@    }a2

Kembalikan angka pertama ( X) untuk melewati fungsi, mulai dari2

ìX

Ubah nomor input menjadi array Xangka dasar .

e

Periksa apakah semua digit benar.

Justin Mariner
sumber
Bukankah ini akan gagal jika array berisi beberapa 10?
Shaggy
@Shaggy Pemahaman saya adalah bahwa, menurut komentar OP, bahwa angka untuk pangkalan di atas 9 tidak dihitung sebagai nol.
Justin Mariner
Ah, saya melihatnya sekarang. Ada masalah dengan pengungkapan tantangan, jadi (atau saya terlalu lelah!).
Shaggy
2

JavaScript (ES6), 43 41 37 byte

n=>(g=x=>x?g(x%b++?x/--b|0:n):b)(b=1)

Uji kasus

Arnauld
sumber
2

Brachylog , 11 byte

;.≜ḃ₎¬∋0∧1¬

Cobalah online!

Penjelasan

;.≜ḃ₎           The Input represented in base Output…
     ¬∋0        …contains no 0
        ∧1¬     And Output ≠ 1
Fatalisasi
sumber
2

Python 2 , 57 byte

n=m=input()
b=2
while m:c=m%b<1;b+=c;m=(m/b,n)[c]
print b

Cobalah online!

-1 terima kasih kepada Felipe Nardi Batista .
-2 Terima kasih kepada Lynn (dan sekarang ini adalah tiruan dari solusinya: D)

Erik the Outgolfer
sumber
59 byte dengan mengubah a,b=a+c,dkea+=c;b=d
Felipe Nardi Batista
Saya pikir Anda dapat menggantinya while m>1dengan while m(dan kemudian kami terikat!)
Lynn
@ Lynn Itu sebabnya saya mengomentari solusi Anda, itu akan sama persis kalau begitu.
Erik the Outgolfer
1
@ Lynna saya sudah tahu: p kalau tidak saya akan meminta Anda untuk menghapus Anda.
Erik the Outgolfer
2

APL (Dyalog) , 20 19 byte

1+⍣{~0∊⍺⊥⍣¯1n}≢n←⎕

Cobalah online!

Seperti biasa, terima kasih kepada @ Adám karena telah membantu dalam obrolan dan membuat kode berfungsi di TIO. Juga, menghemat 1 byte.

Ini tradfn ( trad itional f unctio n ) tubuh. Untuk menggunakannya, Anda harus menetapkannya nama (yang ada di bidang header TIO), lampirkan dalam s (satu sebelum nama dan satu di bidang footer TIO), lalu panggil menggunakan namanya. Karena menggunakan quad ( ) untuk mengambil input pengguna, itu disebut sebagai f \n inputbukan yang biasaf input

Bagaimana?

1+⍣{~0∊⍺⊥⍣¯1n}≢n←⎕   Main function.
                  n←⎕  Assigns the input to the variable n
1+⍣{           }≢      Starting with 1, add 1 until the expression in braces is truthy
    ~0                returns falsy if 0 "is in"
                      convert
            n         the input
         ⍣¯1           to base
                      left argument (which starts at 1 and increments by 1)

Fungsi kemudian mengembalikan basis yang dihasilkan.

J. Sallé
sumber
1
Kiat golf: karena n←⎕akan menjadi angka sederhana dan Anda perlu 1sebagai argumen awal untuk sisa kode, Anda bisa menghitung jumlah elemen dalam n(yaitu 1), dengan mengganti 1⊣dengan . Cobalah online!
Adám
1

Proton , 40 byte

x=>filter(y=>all(digits(y,x)),2..x+3)[0]

Cobalah online!

HyperNeutrino
sumber
1
Ini tidak valid. 2..xmemeriksa pangkalan dalam interval [2, x), maka gagal untuk kasus uji 1dan 2.
Tn. Xcoder
1

R , 79 71 66 63 65 byte

function(n){while(!{T=T+1;all(n%/%T^(0:floor(log(n,T)))%%T)})T
T}

Cobalah online!

Jawaban ini didasarkan pada pengaturan ulang Giuseppe dalam satu loop tunggal.

Disimpan 8 byte berkat JDL, dan 6 byte berkat Giuseppe.

NofP
sumber
1
Anda dapat sub buntuk T, yang dimulai didefinisikan sebagai TRUE == 1, menghilangkan kebutuhan b=1. Demikian pula Anda dapat sub Funtuk k( Fadalah FALSE)
JDL
Saya melihat apa yang Anda lakukan di sana. Itu yang berguna untuk diketahui!
NofP
1
66 byte menggunakan m%/%T(divisi integer) bukan(m-m%%T)/T
Giuseppe
65 byte . itu agak berantakan tetapi saya menduga menyingkirkan loop bersarang akan menghemat sesuatu ; Saya hanya berpikir itu akan menjadi lebih dari 1 byte :(
Giuseppe
1

MATL , 13 12 byte

`G@Q_YAA~}@Q

Cobalah online!

-1 byte terima kasih kepada Luis Mendo. Program ini tidak menangani testcases lebih besar dari 2 ^ 53 ( flintmax, integer maksimum berturut-turut diwakili oleh tipe floating point), karena tipe data default doubledalam MATL. Namun, ia harus dapat menemukan pangkalan nir-sembarang sewenang-wenang di bawah angka itu.

`            % Do while
 G           %  Push input
  @ _        %  Outputs the iteration number, negate.
     YA      %  Convert input to base given by the iteration number, the negative number is to instruct MATL we want an arbitrary high base with a integer vector rather than the default character vector we know from hexadecimal
       A~    %  If they're not all ones, repeat
         }   % But if they are equal, we finally
          @  %  Push the last base
   Q       Q %  As base 1 makes no sense, to prevent MATL from errors we always increase the iteration number by one.
Sanchises
sumber
@LuisMendo Saya harus mulai membaca dokumen dengan lebih baik. Terima kasih.
Sanchises
Ini sepertinya tidak berfungsi untuk test case yang lebih besar, tapi saya tidak cukup tahu tentang MATL / Matlab untuk mengetahui apakah itu disebabkan oleh batas integer atau tidak.
Mego
@Mego Saya menguji versi 13 byte saya yang seharusnya setara dengan versi saat ini hingga 1e6, pada MATLAB R2017a. Pengaturan tes apa yang menyebabkan masalah bagi Anda?
Sanchises
2 kasus uji terakhir menyebabkan kesalahan.
Mego
@Mego Ah saya tidak melihat testcases sebelumnya. Hal ini disebabkan oleh implementasi MATLs YAmenggunakan ganda secara internal, sehingga hanya dapat menangani input hingga integer maksimum berturut-turut yang diwakili oleh ganda (lihat flintmax). Apakah ini membatalkan jawaban? Pada prinsipnya algoritma bekerja untuk basis sewenang-wenang, saya telah secara eksplisit bekerja di sekitar perintah lain yang hanya akan melakukan hingga basis 36.
Sanchises
0

PHP, 59 +1 byte

menggunakan builtin , basis maks 36:

for($b=1;strpos(_.base_convert($argn,10,++$b),48););echo$b;

tidak ada builtin, 63 60 +1 byte , basis apa pun:

for($n=$b=1;$n&&++$b;)for($n=$argn;$n%$b;$n=$n/$b|0);echo$b;

Jalankan sebagai pipa dengan -nRatau coba online .

Titus
sumber
0

J, 26 byte

]>:@]^:(0 e.]#.inv[)^:_ 2:

Ingin tahu jika ini bisa diperbaiki.

Kata kerja utama adalah frasa diad:

>:@]^:(0 e.]#.inv[)^:_

yang diberi input di sebelah kiri dan konstanta 2 di sebelah kanan. Frasa kata kerja utama itu kemudian menggunakan J's Do.. Sementara membangun, menambah argumen y kanan selama 0 adalah elemen darie. .

Cobalah online!

Jonah
sumber
0

Lua , 77 76 byte

b=2n=...N=n
while~~N>0 do
if N%b<1then
b=b+1N=n
else
N=N//b
end
end
print(b)

Cobalah online!

Felipe Nardi Batista
sumber
0

Bimasakti , 38 byte

^^'%{255£2+>:>R&{~^?{_>:<;m_+¡}}^^^}

pemakaian: ./mw base.mwg -i 3


Penjelasan

code                                 explanation                    stack layout

^^                                   clear the preinitialized stack []
  '                                  push the input                 [input]
   %{                              } for loop
     255£                             push next value from 0..254   [input, base-2]
         2+                           add 2 to the get the base     [input, base]
           >                          rotate stack right            [base, input]
            :                         duplicate ToS                 [base, input, input]
             >                        rotate stack right            [input, base, input]
              R                       push 1                        [input, base, input, 1]
               &{~             }      while ToS (=remainder) is true ...
                  ^                    pop ToS                      [input, base, number]
                   ?{         }        if ToS (=quotient) ...
                     _>:<;              modify stack                [input, base, number, base]
                           m            divmod                      [input, base, quotient, remainder]
                           _+¡         else: output ToS (0) + SoS and exit
                                ^^^   pop everything but the input.

Saya yakin ini bisa disingkat menggunakan while-loop bukan for loop, tapi saya tidak bisa membuatnya bekerja.

ovs
sumber
0

Ditumpuk , 23 byte

{!2[1+][n\tb all]until}

Cobalah online!

Peningkatan ini ( [1+]) J mulai dari dua ( 2) sedangkan representasi basis J dari input tidak memiliki nol ( alldan until).

Conor O'Brien
sumber