Semua tentang biner dasar

29

Maafkan judul titny.

Ini adalah pertanyaan yang diinspirasi oleh A Curious Property of 82000 . Di dalamnya, penulis menunjukkan bahwa angka 82000 adalah biner di basis 2, 3, 4, dan 5. Posting kemudian mengajukan pertanyaan "apakah ada angka yang biner di basis 2, 3, 4, 5, dan 6 "? (Bagi mereka yang penasaran, saya telah memeriksa nilai hingga 10 ^ 1.000.000 dan sejauh ini jawabannya adalah tidak.)

Hal ini membuat saya berpikir: diberi nomor, apa basis adalah hal biner dalam?

Nomor penasaran kami, 82000, sebenarnya biner dalam enam basis:

Base 2 = 10100000001010000
Base 3 = 11011111001
Base 4 = 110001100
Base 5 = 10111000
Base 81999 = 11
Base 82000 = 10

Tidak semua angka akan memiliki basis biner yang berurutan. Pertimbangkan nomor 83521. Biner di pangkalan 2, 17, 289, 83520, dan 83521.

Tantangan Anda adalah menentukan dan menampilkan basis nomor mana yang biner.

Aturan

  • Suatu angka dianggap "biner" dalam basis tertentu jika perwakilannya dalam basis itu hanya terdiri dari nol dan satu. 110110adalah nilai biner, sementara 12345tidak, A380Fpasti tidak.
  • Nomor Anda akan diberikan pada input standar. Ini akan menjadi nilai integer antara 2 dan 2 ^ 32-1 inklusif dan akan disediakan dalam format basis-10.
  • Dalam urutan menaik, perlihatkan setiap basis lebih besar dari satu yang jumlahnya biner. Setiap basis harus pada barisnya sendiri. Jika Anda memasukkan nilai biner di basis itu (lihat skor bonus di bawah), pisahkan basis dan nilai biner dengan spasi. Hanya keluaran ke standar yang akan dinilai, kesalahan standar dan sumber lainnya akan diabaikan.

Mencetak gol

Skor Anda adalah ukuran program Anda dalam byte. Semakin rendah skor, semakin baik.

Bonus :
Jika program Anda juga menampilkan nilai-nilai biner di basis yang ditemukan, kalikan skor Anda dengan 0,75
Nilai biner Anda yang ditampilkan tidak boleh memiliki tanda baca tambahan, tidak ada nol di luar, tidak ada angka desimal, hanya nol dan yang.

Contohnya

Memasukkan:

82000

Output (menerima bonus):

2 10100000001010000
3 11011111001
4 110001100
5 10111000
81999 11
82000 10

Memasukkan:

1234321

Output (tidak ada bonus):

2
1111
1234320
1234321
Tuan Llama
sumber
Bisakah input diakhiri dengan baris baru?
LegionMammal978
@ LegionMammal978 - Uhhh ... tentu? Maksud saya adalah bahwa Anda harus bisa mendapatkan nomor input dengan alat sederhana, garis baca, atau yang serupa.
Tn. Llama
1
Secara umum, nselalu setidaknya biner dalam basis 1(tidak dihitung), 2, n-1, dan n.
mbomb007
1
Ketika Anda berkata, "nomor Anda akan diberikan pada input standar," apakah yang Anda maksud hanya STDIN, atau bisakah kita menerima nomor tersebut sebagai argumen fungsi sebagaimana standar untuk situs?
Alex A.
Haruskah representasi biner (di bagian bonus) memiliki format tertentu? Khususnya akan [1, 0, 1, 1, 0]baik-baik saja, atau apakah angka harus digabung seperti 10110?
Jakube

Jawaban:

14

Pyth, 14 13

jbf!-jQTU2tSQ

Terima kasih kepada Jakube karena menunjukkan Sfungsi baru .

Coba di sini.

Versi online terlalu lambat untuk dilakukan 1234321. Ini hanya mengkonversi input ke setiap basis dari 2 ke basis itu sendiri dan membuang hasil yang mengandung nilai selain 0 dan 1.

Penjelasan:

                           : Q=eval(input) (implicit)
jb                         : join on newlines the list...
  f!                       : filter away nonempty values (impliticly named T)
    -jQTU2                 : sewtise difference of number converted to base and range(2)
     jQT                   : convert Q to base T
        U2                 : range(2)
          tSQ              : over the range [2 Q+1)

Selain itu, ini adalah ( tidak baik golfed sekarang juga golfed, lagi berkat Jakube) versi bonus (20 * 0,75 = 15):

VQI!-JjQK+2NU2pdKjkJ

Coba di sini

FryAmTheEggman
sumber
Pyth baru saja diperbarui. Jadi, Anda dapat menautkan ke solusi aktual.
Jakube
Dan inilah solusi 20 * 0,75 = 15: VQI!-JjQK+2NU2pdKjkJTerkadang pemrograman fungsional bukanlah pendekatan terbaik.
Jakube
10

Julia, 72 70 byte

Ini sebenarnya lebih lama dengan bonus, jadi tidak ada bonus di sini.

n=int(readline());for j=2:n all(i->i0:1,digits(n,j))&&println(j)end

Ini membaca baris dari STDIN, mengubahnya menjadi integer, dan mencetak hasilnya. Meskipun merupakan metode brute force, input 1234321 membutuhkan waktu kurang dari 1 detik untuk saya.

Penjelasan + tidak dikumpulkan:

# Read n from STDIN and convert to integer
n = int(readline())

# For every potential base from 2 to n
for j = 2:n
    # If all digits of n in base j are 0 or 1
    if all(i -> i0:1, digits(n, j))
        # Print the base on its own line
        println(j)
    end
end

Contoh:

julia> n=int(readline());for j=2:n all(i->i0:1,digits(n,j))&&println(j)end
1234321
2
1111
1234320
1234321

julia> n=int(readline());for j=2:n all(i->i0:1,digits(n,j))&&println(j)end
82000
2
3
4
5
81999
82000

CATATAN : Jika input dapat diambil sebagai argumen fungsi alih-alih dari STDIN (menunggu konfirmasi dari OP), solusinya adalah 55 byte.

Alex A.
sumber
7

CJam, 20 byte (atau 27 byte * 0,75 = 20.25)

Ini adalah versi no bonus, 20 byte:

ri:X,2f+{X\b2,-!},N*

Coba ini di sini.

Hanya untuk bersenang-senang, ini adalah versi bonusnya, 27 byte:

ri:X{X\)b2,-!},1>{)SX2$bN}/

Cobalah online di sini

Pengoptimal
sumber
Yakin. Setelah saya selesai bermain golf.
Pengoptimal
1
ri_,f{2+S@2$bN}4/{2=2,-!},(19,5 byte)
Dennis
7

Mathematica, 59 byte

Print/@Select[1+Range[n=Input[]],Max@IntegerDigits[n,#]<2&]

Ugh ... IntegerDigitsD:

Tidak banyak yang bisa dijelaskan tentang kode ... 12 byte terbuang oleh persyaratan untuk menggunakan STDIN dan STDOUT.

Saya tidak berpikir saya bisa mengklaim bonus. Yang terbaik yang saya dapatkan adalah 84 byte (yang menghasilkan skor lebih dari 60):

Print@@@Select[{b=#+1," ",##&@@n~IntegerDigits~b}&/@Range[n=Input[]],Max@##3<2&@@#&]
Martin Ender
sumber
7

Python 2, 88 86 80

Cukup mudah, tidak ada bonus. Python bagus dan ringan dengan variabel global.

N=input();g=lambda n:n<1or(n%b<2)*g(n/b)
for b in range(2,N+1):
 if g(N):print b

Terbaik yang berhasil saya dapatkan untuk bonus adalah 118 * .75 = 87.75 :

N=input();g=lambda n:0**n*" "or" "*(n%b<2)and(g(n/b)+`n%b`)*(g(n/b)>'')
for b in range(2,N+1):
 if g(N):print`b`+g(N)
KSab
sumber
Solusi yang bagus, kalahkan saya dengan kode yang jauh lebih pendek.
Kade
Ini akan menjadi lebih pendek untuk hanya melakukan g(N)bukan n=N.
feersum
@feersum Oh yeah (dulu g(N,b)begitu koma membuat keduanya sama), tapi apa maksudmu aku tidak perlu variabel untuk N?
KSab
@KSab, saya menghapus bagian kedua itu; lupakan saja.
feersum
Saya mungkin salah, tapi tidak bisa Anda mendapatkan bonus dengan hanya mengubah g(n/b)ke (g(n/b)+'n%b')mana 'merupakan backtick a?
feersum
4

Python 2, 90 * 0.75 = 67.5

n=input();b=1
while b<n:
 b+=1;s="";c=k=n
 while k:s=`k%b`+s;c*=k%b<2;k/=b
 if c:print b,s

Pendekatan iteratif yang cukup mudah.

Tanpa bonus, ini adalah 73 byte:

n=input();b=1
while b<n:
 b+=1;c=k=n
 while k:c*=k%b<2;k/=b
 if c:print b
Sp3000
sumber
4

SQL (PostgreSQL), 247.5 255 230.25 (307 * .75)

Karena SQL dikenal luar biasa dalam tantangan semacam ini, saya pikir saya lebih baik menyatukannya :) Bonusnya sangat berharga untuk yang satu ini.
Seharusnya sesuai dengan spec, tetapi saya tidak memiliki cara mudah untuk menguji COPY I FROM STDIN .
Edit pesanan tetap. Mengubah cara kolom R ditangani untuk menggunakan array.

CREATE TABLE IF NOT EXISTS I(I INT);TRUNCATE TABLE I;COPY I FROM STDIN;WITH RECURSIVE R AS(SELECT n,I/n I,ARRAY[I%n] R FROM generate_series(2,(SELECT I FROM I))g(n),(SELECT I FROM I)I(I)UNION ALL SELECT n,I/n,I%n||R FROM R WHERE I>0)SELECT n||' '||array_to_string(R,'')FROM R WHERE 2>ALL(R)and i=0ORDER BY n

Sebagai ujian saya hanya menggunakan sisipan lurus ke dalam Itabel. Uji coba diperluas dan dikomentari.

-- Create the table to accept the input from the copy command
CREATE TABLE IF NOT EXISTS I(I INT);
-- Make sure that it is empty
TRUNCATE TABLE I;
-- Popoulate it with a value from STDIN
--COPY I FROM STDIN;
INSERT INTO I VALUES(82000); -- Testing
--Using a recursive CTE query
WITH RECURSIVE R AS (
    -- Recursive anchor
    SELECT n,                -- base for the row
       I/n I,                -- integer division
       ARRAY[I%n] R   -- put mod value in an array
    FROM generate_series(2,(SELECT I FROM I))g(n), -- series for the bases
         (SELECT I FROM I)I(I) -- Cross joined with I,  saves a few characters
    UNION ALL 
    -- for each row from r recursively repeat the division and mod until i is 0
    SELECT n,
        I/n,
        I%n||R -- Append mod to beginning of the array
    FROM R WHERE I>0
    )
-- return from r where i=0 and r has 1's and 0's only
SELECT n||' '||array_to_string(R,'')
FROM R 
WHERE 2 > ALL(R)and i=0
ORDER BY n -- Ensure correct order

2 10100000001010000
3 11011111001
4 110001100
5 10111000
81999 11
82000 10

MickyT
sumber
Sangat dekat! Basis output harus dalam urutan menaik. +1 untuk menggunakan bahasa yang tidak konvensional.
Tn. Llama
@ Mr.Llama memperbaikinya dengan order by. Sekarang untuk melihat apakah saya bisa mendapatkan kembali karakter-karakter itu
MickyT
3

Haskell 109 * 0,75 = 81,75 byte

0#x=[]
n#x=n`mod`x:div n x#x 
f n=[show x++' ':(n#x>>=show)|x<-[2..n+1],all(<2)$n#x]
p=interact$unlines.f.read

Contoh penggunaan (catatan: nilai biner adalah lsb pertama):

p 82000

2 00001010000000101
3 10011111011
4 001100011
5 00011101
81999 11
82000 01

Tanpa batasan input / output, yaitu input melalui argumen fungsi, output dalam format asli melalui REPL):

Haskell, 67 * 0,75 = 50,25 byte

0#x=[]
n#x=n`mod`x:div n x#x
f n=[(x,n#x)|x<-[2..n+1],all(<2)$n#x]

Mengembalikan daftar pasangan (basis, nilai). Nilai-nilai adalah lsb pertama, misalnya (baris baru / spasi ditambahkan untuk tampilan yang lebih baik):

 f 82000
 [ (2,[0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1]),
   (3,[1,0,0,1,1,1,1,1,0,1,1]),
   (4,[0,0,1,1,0,0,0,1,1]),
   (5,[0,0,0,1,1,1,0,1]),
   (81999,[1,1]),
   (82000,[0,1]) ] 
nimi
sumber
2

R, 111

Mungkin banyak ruang untuk memperbaikinya saat ini

i=scan();b=2:i;R=i%%b;I=rep(i,i-1);while(any(I<-I%/%b))R=cbind(I%%b,R);for(x in b)if(all(R[x-1,]<2))cat(x,'\n')

Dijalankan dengan peringatan

> i=scan();b=2:i;R=i%%b;I=rep(i,i-1);while(any(I<-I%/%b))R=cbind(I%%b,R);for(x in b)if(all(R[x-1,]<2))cat(x,'\n')
1: 82000
2: 
Read 1 item
There were 17 warnings (use warnings() to see them)
2 
3 
4 
5 
81999 
82000
>
MickyT
sumber
@AlexA. Peringatan yang disebabkan oleh paksaan pada I%/%blogika dalam any()klausa. `
MickyT
2

Java, 181 155.25 (207 * .75) 151.5 (202 * .75) byte

class I{public static void main(String[]a){a:for(long b=new java.util.Scanner(System.in).nextLong(),c,d=1;d++<b;){String e="";for(c=b;c>0;e=c%d+e,c/=d)if(c%d>1)continue a;System.out.println(d+" "+e);}}}

Diperluas dengan penjelasan:

class I {
    public static void main(String[]a){
        a:for(long b=new java.util.Scanner(System.in).nextLong(),c,d=1; //b = input(), d = base
              d++<b;) {                                           //For all bases in range(2,b+1)
            String e="";
            for(c = b;c > 0; e = c % d + e,c /= d)                //Test all digits of base-d of b
                           //e = c % d + e                        //Append digits to string
                if (c % d > 1)                                    //Reject base if the digit is greater than 1
                    continue a;
            System.out.println(d+" "+e);                          //Print base and digits.
        }
    }
}

Asli (tanpa bonus):

class I{public static void main(String[]a){long b=new java.util.Scanner(System.in).nextLong(),c,d=1;a:for(;d++<b;){c=b;while(c>0){if(c%d>1)continue a;c/=d;}System.out.println(d);}}}

3,75 byte terima kasih kepada Ypnypn :)

TheNumberOne
sumber
2

R, 94 83 79

n=scan();cat((2:n)[!sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n})],sep="\n")

Pemakaian:

> n=scan();cat((2:n)[!sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n})],sep="\n")
1: 82000
2: 
Read 1 item
2
3
4
5
81999
82000
> n=scan();cat((2:n)[!sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n})],sep="\n")
1: 1234321
2: 
Read 1 item
2
1111
1234320
1234321

Inti dari fungsi ini adalah !sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n}), untuk setiap basis x dari 2 ke n, menjaga hasil bagi n / x selama sisanya adalah 0 dan 1. Kemudian output hasilnya (yaitu 0 jika semua sisa adalah 1 atau 0) dan meniadakannya (0 meniadakan ke TRUE, yang lainnya meniadakan ke SALAH). Berkat lingkup fungsi, tidak perlu membuat variabel dummy untuk n. Vektor yang dihasilkan dari boolean kemudian digunakan untuk mengindeks 2:ndan karenanya hanya menghasilkan basis yang berfungsi.

plannapus
sumber
1

TI-Basic, 45 byte

Input N
For(B,2,N
If prod(seq(BfPart(iPart(N/B^X)/B),X,0,log(N)/log(B))<2
Disp B
End

Penjelasan

  • Masukan N
  • Untuk setiap B dari 2 hingga N
    • Jika N hanya 0 dan 1 pada basis B
      • Tampilan B
  • Akhiri lingkaran

Bagian yang rumit

Baris kedua berfungsi sebagai berikut:

  • Untuk setiap X dari 0 hingga log B N
  • B × fPart (iPart (N / B X ) / B) adalah digit ke-N di basis B, menghitung mundur
  • Anggap ini sebagai daftar
  • Untuk setiap elemen, jika digit kurang dari 2, hasilkan 1 (benar), jika tidak 0 (salah)
  • Ambil produk: 1 jika semua elemen 1

Catatan

Program berjalan secara signifikan lebih cepat jika tanda kurung tutup )ditempatkan pada akhir baris kedua. Lihat di sini untuk informasi lebih lanjut tentang ini.

Ypnypn
sumber
1

TI-BASIC, 31 29

For(B,2,Ans
If 2>round(Bmax(fPart(Ans/B^randIntNoRep(1,32
Disp B
End

Ini mungkin optimal untuk TI-BASIC.

Penjelasan:

randIntNoRep(1,32)mengembalikan permutasi acak dari angka dari 1 hingga 32 (Yang kita butuhkan adalah angka-angka itu dalam beberapa urutan; TI-BASIC tidak memiliki apa pun seperti perintah iota APL). 32 elemen sudah cukup karena basis terkecil yang mungkin adalah 2 dan jumlah terbesar adalah 2 ^ 32-1. B^randIntNoRep(1,31)meningkatkan daftar itu ke kekuatan Bth, yang menghasilkan daftar yang berisi semua B^1,B^2,...,B^32(dalam urutan tertentu).

Kemudian input (dalam Ansvariabel wer, yang merupakan input ke dalam formulir [number]:[program name]) dibagi dengan angka itu. Jika input Anda adalah 42 dan basisnya adalah 2, hasilnya akan menjadi daftar 21,10.5,5.25,...,42/32,42/64,[lots of numbers less than 1/2], sekali lagi dalam urutan tertentu.

Mengambil bagian pecahan dan mengalikan angka dengan basis Anda memberikan angka pada posisi itu dalam representasi basis-b. Jika semua digit kurang dari 2, maka digit terbesar akan kurang dari 2.

Seperti Ypnypn menyatakan, tanda kurung tutup pada Forpernyataan mempercepat ini karena bug parser.

31-> 31: Menyimpan byte tetapi memperbaiki kesalahan pembulatan yang menambahkan byte lagi.

31-> 29: Menyimpan dua byte dengan menggunakan RandIntNoRep()alih-alih cumSum(binomcdf()).

lirtosiast
sumber
Apakah TI-BASIC memiliki fungsi urutan?
Tn. Llama
Ya, perintahnya adalah seq(expression, variable, start, end[, step]). Jika tidak ada langkah yang diberikan, defaultnya adalah 1. Namun, cumSum(binomcdf(31,0adalah 8 byte sedangkan seq(X,X,1,329 byte.
lirtosiast
Ah, itu menjelaskannya. Saya tidak terbiasa dengan mencetak karya di TI-Basic.
Tn. Llama 15
1

Jelly , 9 byte

³bṀỊµÐfḊY

Cobalah online!

Dilakukan bersama caird coinheringaahing dalam obrolan .

Bagaimana itu bekerja

FullbṀỊμÐfḊY Program lengkap.

     Jika menyaring rentang yang dihasilkan secara implisit [1, input].
    μ Mulai rantai monadik baru.
³b Konversi input ke basis nomor saat ini, sebagai daftar.
  Ṁ Maksimum.
   Ị Tidak signifikan. Cek apakah abs (Z) ≤ 1.
       Ḋ Dequeue; Menghapus elemen pertama dari daftar (untuk menjatuhkan basis 1).
        Y Gabung dengan baris baru.
Tuan Xcoder
sumber
0

Javascript, ES6, 118 * .75 = 88.5 110 * .75 = 82.5

f=x=>{res={};for(b=2;b<=x;++b)if(!+(res[b]=(c=x=>x%b<2?x?c(x/b|0)+""+x%b:"":"*")(x)))delete res[b];return res}

Versi sebelumnya:

f=x=>{res={};for(q=2;q<=x;++q)if(!+(res[q]=(c=(x,b)=>x%b<2?x?c(x/b|0,b)+""+x%b:"":"*")(x,q)))delete res[q];return res}

Memeriksa:

f(82000)
Object { 2: "10100000001010000", 3: "11011111001", 4: "110001100", 5: "10111000", 81999: "11", 82000: "10" }
Qwertiy
sumber
Di sini Anda tidak memiliki input dan output.
edc65
0

JavaScript ( ES6 ) 65

68 byte untuk fungsi dengan parameter dan output konsol.

f=n=>{s=n=>n%b>1||b<n&&s(n/b|0);for(b=1;b++<n;)s(n)||console.log(b)}

65 byte dengan I / O via popup

n=prompt(s=n=>n%b>1||b<n&&s(n/b|0));for(b=1;b++<n;)s(n)||alert(b)

Mengklaim bonus: 88 * 0.75 => 66

n=prompt(s=n=>n%b>1?9:(b<=n?s(n/b|0):'')+n%b);for(b=1;b++<n;)s(n)<'9'&&alert(b+' '+s(n))
edc65
sumber
0

Mathematica, 76 * 0,75 = 57

n=Input[];G=#~IntegerDigits~b&;If[Max@G@n<2,Print[b," ",Row@G@n]]~Do~{b,2,n}

Awalnya lupa tentang persyaratan input ... Untungnya, itu tidak menambah terlalu banyak.

Menghitung
sumber
0

Ruby , 44 byte

->n{(2..n).select{|i|n.digits(i)-[0,1]==[]}}

Cobalah online!

daniero
sumber
0

Perl 5 , 63 byte

map{$t=$n;1while($f=$t%$_<2)&&($t=int$t/$_);say if$f}2..($n=<>)

Cobalah online!

Tidak ada bonus untuk ini karena skornya sedikit lebih baik daripada versi saya dengan bonus:

Perl 5 , 85 byte * 0,75 = 63,75

map{my$r;$t=$n;$r=$/.$r while($/=$t%$_)<2&&($t=int$t/$_);say"$_ 1$r"if$/<2}2..($n=<>)

Cobalah online!

Xcali
sumber