Wszystko o podstawowym pliku binarnym

29

Przepraszam za tytuł.

To pytanie jest inspirowane przez Ciekawą własność 82000 . Autor zaznacza w nim, że liczba 82000 jest binarna w bazie 2, 3, 4 i 5. W odpowiedzi pojawia się pytanie „czy liczba jest binarna w bazach 2, 3, 4, 5 i 6 „? (Dla ciekawskich sprawdziłem wartości do 10 ^ 1 000 000 i jak dotąd odpowiedź brzmi nie.)

To sprawiło, że pomyślałem: biorąc pod uwagę liczbę, w jakich podstawach jest binarny?

Nasza ciekawa liczba, 82000, jest w rzeczywistości dwójkowa w sześciu bazach:

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

Nie wszystkie liczby będą miały sekwencje binarne. Rozważ liczbę 83521. Jest binarna w bazach 2, 17, 289, 83520 i 83521.

Wyzwanie polega na ustaleniu i wyświetleniu, w jakich podstawach liczba jest binarna.

Zasady

  • Liczba jest uważana za „binarną” w danej bazie, jeśli jej reprezentacja w tej bazie składa się tylko z zer i jedynek. 110110jest wartością binarną, chociaż 12345nie A380Fjest, zdecydowanie nie jest.
  • Twój numer zostanie podany na standardowym wejściu. Będzie to liczba całkowita od 2 do 2 ^ 32-1 włącznie i zostanie podana w formacie base-10.
  • W porządku rosnącym wyświetl każdą bazę większą niż jedna, w której liczba jest liczbą binarną. Każda baza powinna znajdować się w osobnej linii. Jeśli włączysz wartość binarną do tej podstawy (patrz punktacja premii poniżej), oddziel podstawę i wartość binarną spacją. Tylko wyjście do standardowego wyjścia zostanie ocenione, błąd standardowy i inne źródła zostaną zignorowane.

Punktacja

Twój wynik to rozmiar programu w bajtach. Im niższy wynik, tym lepiej.

Premia :
Jeśli Twój program wyświetla również wartości binarne w znalezionych bazach, pomnóż swój wynik przez 0,75.
Wyświetlana wartość binarna nie powinna zawierać dodatkowej interpunkcji, żadnych zer zerowych, żadnych kropek dziesiętnych, tylko zer i jedynek.

Przykłady

Wkład:

82000

Wyjście (otrzymuje bonus):

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

Wkład:

1234321

Wyjście (bez premii):

2
1111
1234320
1234321
Pan Llama
źródło
Czy dane wejściowe mogą kończyć się nową linią?
LegionMammal978
@ LegionMammal978 - Uhhh ... pewnie? Moim zamiarem było, że powinieneś być w stanie uzyskać numer wejściowy za pomocą prostych fgets, readline lub czegoś podobnego.
Pan Llama,
1
Ogólnie rzecz biorąc, nzawsze co najmniej binarny zasad 1(nie liczy) 2, n-1i n.
mbomb007
1
Kiedy mówisz: „Twój numer zostanie podany na standardowym wejściu”, masz na myśli tylko STDIN, czy też możemy alternatywnie zaakceptować liczbę jako argument funkcji, tak jak jest to standard w przypadku witryny?
Alex A.
Czy reprezentacja binarna (w części bonusowej) powinna mieć określony format? Szczególnie byłoby [1, 0, 1, 1, 0]dobrze, czy też liczby muszą być połączone, tak jak 10110?
Jakube,

Odpowiedzi:

14

Pyth, 14 13

jbf!-jQTU2tSQ

Dzięki Jakube za wskazanie nowej Sfunkcji.

Wypróbuj tutaj.

Wersja online jest zbyt wolna 1234321. To po prostu konwertuje dane wejściowe do każdej bazy z 2 na siebie i odrzuca wyniki zawierające wartości inne niż 0 i 1.

Wyjaśnienie:

                           : 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)

Ponadto, jest to ( nie dobrze grałem teraz dobrze grałem ponownie dzięki Jakube) wersji premiowej (20 * 0,75 = 15):

VQI!-JjQK+2NU2pdKjkJ

Wypróbuj tutaj

FryAmTheEggman
źródło
Pyth właśnie został zaktualizowany. Możesz więc połączyć się z rzeczywistymi rozwiązaniami.
Jakube,
Oto rozwiązanie 20 * 0,75 = 15: VQI!-JjQK+2NU2pdKjkJCzasami programowanie funkcjonalne nie jest najlepszym podejściem.
Jakube,
10

Julia, 72 70 bajtów

W rzeczywistości jest on dłuższy z bonusem, więc nie ma tu bonusu.

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

Odczytuje linię ze STDIN, konwertuje ją na liczbę całkowitą i wypisuje wynik. Pomimo tego, że była to metoda brutalnej siły, wejście 1234321 zajęło mi mniej niż 1 sekundę.

Niegolfowane + wyjaśnienie:

# 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

Przykłady:

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

UWAGA : Jeśli dane wejściowe można traktować jako argument funkcji, a nie ze STDIN (oczekuje na potwierdzenie z OP), rozwiązanie ma 55 bajtów.

Alex A.
źródło
7

CJam, 20 bajtów (lub 27 bajtów * 0,75 = 20,25)

Oto wersja bez premii, 20 bajtów:

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

Wypróbuj to tutaj.

Dla zabawy, oto wersja bonusowa, 27 bajtów:

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

Wypróbuj online tutaj

Optymalizator
źródło
Pewnie. Kiedyś skończę trochę grać w golfa.
Optymalizator
1
ri_,f{2+S@2$bN}4/{2=2,-!},(19,5 bajtów)
Dennis
7

Mathematica, 59 bajtów

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

Ugh ... IntegerDigitsD:

Tak naprawdę nie ma wiele do wyjaśnienia na temat kodu ... 12 bajtów jest marnowanych przez wymóg używania STDIN i STDOUT.

Nie sądzę, żebym mógł odebrać bonus. Najlepsze, jakie mam, to 84 bajty (co daje wynik powyżej 60):

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

Python 2, 88 86 80

Dość proste, bez premii. Python jest przyjemny i łagodny dla zmiennych globalnych.

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

Najlepsze, co udało mi się uzyskać za bonus, to 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
źródło
Fajne rozwiązanie, pobij mnie znacznie krótszym kodem.
Kade
g(N)Zamiast tego byłoby to krótsze n=N.
feersum
@feersum O tak (kiedyś g(N,b)przecinek sprawiał, że oba były równe), ale co masz na myśli, że nie potrzebowałbym zmiennej dla N?
KSab
@KSab Usunąłem tę drugą część; nie ważne.
feersum
Mogę się mylić, ale czy nie mógłbyś uzyskać premii, po prostu zmieniając g(n/b)na (g(n/b)+'n%b')gdzie „reprezentuje backstick?
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

Całkiem proste podejście iteracyjne.

Bez premii jest to 73 bajty:

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
źródło
4

SQL (PostgreSQL), 247,5 255 230,25 (307 * .75)

Ponieważ SQL jest znany z tego, że jest wspaniały w tego rodzaju wyzwaniach, pomyślałem, że lepiej go połączyć :) Bonus był naprawdę warty tego.
Powinien być zgodny ze specyfikacją, ale nie mam łatwego sposobu na przetestowanie COPY I FROM STDIN .
Edytuj ustaloną kolejność. Zmieniono sposób obsługi kolumny R w celu użycia tablicy.

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

Jako test użyłem właśnie prostych wkładek do Istołu. Uruchomiono test i skomentowano.

-- 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
źródło
Tak blisko! Podstawy wyjściowe muszą być w porządku rosnącym. +1 za użycie niekonwencjonalnego języka.
Pan Llama,
@ Mr.Llama naprawił to za pomocą order by. Teraz zobaczę, czy uda mi się odzyskać te postacie
MickyT
3

Haskell 109 * 0,75 = 81,75 bajtów

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

Przykład użycia (uwaga: wartości binarne są najpierw lsb):

p 82000

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

Bez ograniczeń wejścia / wyjścia, tj. Wejście przez argument funkcji, wyjście w formacie macierzystym przez REPL):

Haskell, 67 * 0,75 = 50,25 bajtów

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

Zwraca listę par (podstawowa, wartość). Wartości są najpierw lsb, np. (Dodano nowe wiersze / spacje dla lepszego wyświetlania):

 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
źródło
2

R, 111

Prawdopodobnie w tej chwili jest dużo miejsca, aby to poprawić

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')

Działa z ostrzeżeniami

> 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
źródło
@AlexA. Ostrzeżenia spowodowane przez wymuszenie I%/%blogicznej any()klauzuli. `
MickyT
2

Java, 181 155,25 (207 * .75) 151,5 (202 * .75) bajtów

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);}}}

Rozszerzony z wyjaśnieniem:

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.
        }
    }
}

Oryginał (bez premii):

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 bajtów dzięki Ypnypn :)

Numer jeden
źródło
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")

Stosowanie:

> 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

Rdzeniem funkcji jest to !sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n}), że dla każdej podstawy x od 2 do n zachowuje iloraz n / x, o ile reszta wynosi 0 i 1. Następnie wyprowadza wynik (który wynosi 0, jeśli wszystkie pozostałe były równe 1 lub 0) i neguje (0 neguje na PRAWDA, wszystko inne neguje na FAŁSZ). Dzięki zakresowi funkcji nie ma potrzeby tworzenia zmiennej zastępczej dla n. Powstały wektor booleanów jest następnie wykorzystywany do indeksowania, 2:na zatem generuje tylko zasady, dla których działał.

plannapus
źródło
1

TI-Basic, 45 bajtów

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

Wyjaśnienie

  • Wpisz N
  • Dla każdego B od 2 do N
    • Jeśli N wynosi tylko 0 i 1 w bazie B
      • Wyświetlacz B
  • Koniec pętli

Skomplikowana część

Druga linia działa w następujący sposób:

  • Dla każdego X od 0 do log B N
  • B × fPart (iPart (N / B X ) / B) to n-ta cyfra w bazie B, odliczająca do tyłu
  • Potraktuj to jako listę
  • Dla każdego elementu, jeśli cyfra jest mniejsza niż 2, zwróć 1 (prawda), w przeciwnym razie 0 (fałsz)
  • Weź produkt: 1 iff wszystkie elementy to 1

Uwaga

Program działa znacznie szybciej, jeśli nawias zamykający )zostanie umieszczony na końcu drugiej linii. Zobacz tutaj, aby uzyskać więcej informacji na ten temat.

Ypnypn
źródło
1

TI-BASIC, 31 29

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

Jest to prawdopodobnie optymalne dla TI-BASIC.

Wyjaśnienie:

randIntNoRep(1,32)zwraca losową permutację liczb od 1 do 32 (Potrzebujemy tylko tych liczb w pewnej kolejności; TI-BASIC nie ma nic takiego jak polecenie iota APL-a). Wystarczą 32 elementy, ponieważ najmniejsza możliwa baza to 2, a największa liczba to 2 ^ 32-1. B^randIntNoRep(1,31)podnosi tę listę do potęgi Bth, co powoduje, że lista zawiera wszystkie B^1,B^2,...,B^32(w pewnej kolejności).

Następnie dane wejściowe (w Anszmiennej wer, która jest wprowadzana w formularzu [number]:[program name]) są dzielone przez tę liczbę. Jeśli twój wkład to 42, a podstawa to 2, wynikiem będzie lista 21,10.5,5.25,...,42/32,42/64,[lots of numbers less than 1/2], znowu w pewnej kolejności.

Biorąc część ułamkową i mnożąc liczbę przez bazę, otrzymujemy cyfrę w tej pozycji w reprezentacji base-b. Jeśli wszystkie cyfry są mniejsze niż 2, wówczas największa cyfra będzie mniejsza niż 2.

Jak stwierdził Ypnypn, nawias zamykający Foroświadczenie przyspiesza to z powodu błędu parsera.

31-> 31: Zapisano bajt, ale naprawiono błędy zaokrąglania, które dodawały bajt ponownie.

31-> 29: Zapisano dwa bajty, używając RandIntNoRep()zamiast cumSum(binomcdf()).

lirtosiast
źródło
Czy TI-BASIC ma funkcję sekwencji?
Pan Llama,
Tak, polecenie brzmi seq(expression, variable, start, end[, step]). Jeśli nie podano żadnego kroku, domyślnie jest to 1. Jednak cumSum(binomcdf(31,0ma 8 bajtów, a seq(X,X,1,329 bajtów.
lirtosiast
Ach, to wyjaśnia. Nie znam punktacji w TI-Basic.
Pan Llama,
1

Galaretka , 9 bajtów

³bṀỊµÐfḊY

Wypróbuj online!

Sporządzono wraz z Cairnem coinheringaahing na czacie .

Jak to działa

FullbṀỊµÐfḊY Pełny program.

     Filterf Przefiltruj domyślnie wygenerowany zakres [1, wejście].
    µ Rozpoczyna nowy łańcuch monadyczny.
³b Konwertuj dane wejściowe na bazę bieżącego numeru jako listę.
  Ṁ Maksymalnie.
   Ị Nieistotne. Sprawdza, czy abs (Z) ≤ 1.
       Ḋ Dequeue; Usuwa pierwszy element listy (upuszczając bazę 1).
        Y Dołącz przez nowe linie.
Pan Xcoder
źródło
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}

Poprzednia wersja:

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}

Czek:

f(82000)
Object { 2: "10100000001010000", 3: "11011111001", 4: "110001100", 5: "10111000", 81999: "11", 82000: "10" }
Qwertiy
źródło
Tutaj nie masz wejścia ani wyjścia.
edc65
0

JavaScript ( ES6 ) 65

68 bajtów dla funkcji z parametrem i wyjściem konsoli.

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

65 bajtów z I / O poprzez wyskakujące okienko

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

Wniosek o premię: 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
źródło
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}

Początkowo zapomniałem o wymaganiach wejściowych ... Na szczęście nie dodały one zbyt wiele.

Zestawienie
źródło
0

Perl 5 , 63 bajtów

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

Wypróbuj online!

Brak premii z tego powodu, ponieważ osiąga bardzo niewiele lepsze wyniki niż moja wersja z premią:

Perl 5 , 85 bajtów * 0,75 = 63,75

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

Wypróbuj online!

Xcali
źródło