Todo sobre binario básico

29

Por favor, disculpe el título punny.

Esta es una pregunta inspirada en una propiedad curiosa de 82000 . En él, el autor señala que el número 82000 es binario en las bases 2, 3, 4 y 5. La publicación plantea la pregunta "¿hay un número que sea binario en las bases 2, 3, 4, 5 y 6? "? (Para aquellos curiosos, he verificado valores de hasta 10 ^ 1,000,000 y hasta ahora la respuesta es no).

Esto me hizo pensar: dado un número, ¿en qué bases es binario?

Nuestro curioso número, 82000, es en realidad binario en seis bases:

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

No todos los números tendrán bases binarias que sean secuenciales. Considere el número 83521. Es binario en las bases 2, 17, 289, 83520 y 83521.

Su desafío es determinar y mostrar en qué bases un número es binario.

Reglas

  • Un número se considera "binario" en una base dada si su representación en esa base consiste solo en ceros y unos. 110110es un valor binario, mientras 12345que no lo es,A380F es definitivamente no lo es.
  • Su número será proporcionado en la entrada estándar. Será un valor entero entre 2 y 2 ^ 32-1 inclusive y se proporcionará en formato base 10.
  • En orden ascendente, muestre cada base mayor que una en la que el número sea binario. Cada base debe estar en su propia línea. Si incluye el valor binario en esa base (vea la puntuación de bonificación a continuación), separe la base y el valor binario con un espacio. Solo se juzgará la salida a la salida estándar, se ignorarán los errores estándar y otras fuentes.

Tanteo

Su puntaje es el tamaño de su programa en bytes. Cuanto más bajo sea el puntaje, mejor.

Bonificación :
si su programa también genera los valores binarios en las bases encontradas, multiplique su puntaje por 0.75
El valor binario que se muestra no debe tener puntuación adicional, ni ceros extraños, ni punto decimal, solo ceros y unos.

Ejemplos

Entrada:

82000

Salida (recibe bonificación):

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

Entrada:

1234321

Salida (sin bonificación):

2
1111
1234320
1234321
Señor llama
fuente
¿La entrada puede terminar con una nueva línea?
LegionMammal978
@ LegionMammal978 - Uhhh ... ¿seguro? Mi intención era que pudieras obtener el número de entrada con un simple fgets, readline o algo similar.
Sr. Llama
1
En general, nsiempre es al menos binaria en bases 1(no contados), 2, n-1, y n.
mbomb007
1
Cuando dice: "su número se proporcionará en la entrada estándar", ¿se refiere a STDIN solamente, o podemos aceptar alternativamente el número como argumento de función como es estándar para el sitio?
Alex A.
¿Debería la representación binaria (en la parte de bonificación) tener cierto formato? Particularmente estaría [1, 0, 1, 1, 0]bien, o ¿los números tienen que unirse como 10110?
Jakube

Respuestas:

14

Pyth, 14 13

jbf!-jQTU2tSQ

Gracias a Jakube por señalar la nueva Sfunción.

Pruébalo aquí.

La versión en línea es muy lenta 1234321 . Esto simplemente convierte la entrada a cada base de 2 a sí misma y descarta los resultados que contienen valores distintos de 0 y 1.

Explicación:

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

Además, esta es una versión de bonificación ( no muy bien ahora muy bien, nuevamente gracias a Jakube) (20 * .75 = 15):

VQI!-JjQK+2NU2pdKjkJ

Pruébalo aquí

FryAmTheEggman
fuente
Pyth acaba de actualizarse. Para que pueda vincular a soluciones reales.
Jakube
Y aquí hay una solución de 20 * 0.75 = 15: a VQI!-JjQK+2NU2pdKjkJveces, la programación funcional no es el mejor enfoque.
Jakube
10

Julia, 72 70 bytes

En realidad es más largo con la bonificación, por lo que no hay bonificación aquí.

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

Esto lee una línea de STDIN, la convierte en un número entero e imprime el resultado. A pesar de ser un método de fuerza bruta, la entrada 1234321 me tomó menos de 1 segundo.

Ungolfed + explicación:

# 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

Ejemplos:

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

NOTA : Si la entrada se puede tomar como un argumento de función en lugar de STDIN (esperando la confirmación del OP), la solución es de 55 bytes.

Alex A.
fuente
7

CJam, 20 bytes (o 27 bytes * 0.75 = 20.25)

Aquí está la versión sin bonificación, 20 bytes:

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

Intenta esto aquí.

Solo por diversión, aquí está la versión de bonificación, 27 bytes:

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

Pruébalo en línea aquí

Optimizador
fuente
Seguro. Una vez que haya terminado un poco de golf.
Optimizador
1
ri_,f{2+S@2$bN}4/{2=2,-!},(19.5 bytes)
Dennis
7

Mathematica, 59 bytes

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

Ugh ... IntegerDigitsD:

No hay mucho que explicar sobre el código ... 12 bytes son desperdiciados por el requisito de usar STDIN y STDOUT.

No creo que pueda reclamar el bono. Lo mejor que tengo es 84 bytes (lo que arroja una puntuación superior a 60):

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

Pitón 2, 88 86 80

Bastante sencillo, sin bonificación. Python es agradable e indulgente con variables globales.

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

Lo mejor que he conseguido para obtener el bono es 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
fuente
Buena solución, me ganó con un código mucho más corto.
Kade
Sería más corto simplemente hacer en g(N)lugar de n=N.
feersum
@feersum Oh sí (solía ser g(N,b)así que la coma hacía que los dos fueran iguales), pero ¿qué quieres decir con que no necesitaría una variable para N?
KSab
@KSab eliminé esa segunda parte; no importa.
fiesta
Puedo estar equivocado, pero ¿no podría obtener la bonificación simplemente cambiando g(n/b)a (g(n/b)+'n%b')donde 'representa un retroceso?
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

Enfoque iterativo bastante sencillo.

Sin la bonificación, esto es 73 bytes:

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
fuente
4

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

Como se sabe que SQL es maravilloso en este tipo de desafíos, pensé que sería mejor armar uno :) El bono realmente valió la pena para este.
Debe cumplir con las especificaciones, pero no tengo una manera fácil de probar la COPIA I DE STDIN .
Editar orden fija. Se cambió la forma en que se maneja la columna R para usar una matriz.

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

Como prueba, solo utilicé inserciones rectas en la Imesa. Ejecución de prueba ampliada y comentada.

-- 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
fuente
¡Tan cerca! Las bases de salida deben estar en orden ascendente. +1 por usar un lenguaje poco convencional.
Sr. Llama
@ Mr.Llama lo arregló con un order by. Ahora para ver si puedo recuperar esos personajes
MickyT
3

Haskell 109 * 0.75 = 81.75 bytes

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

Ejemplo de uso (nota: los valores binarios son lsb primero):

p 82000

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

Sin restricciones de entrada / salida, es decir, entrada a través del argumento de función, salida en formato nativo a través de REPL):

Haskell, 67 * 0.75 = 50.25 bytes

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

Devuelve una lista de pares (base, valor). Los valores son lsb primero, por ejemplo (nuevas líneas / espacios añadidos para una mejor visualización):

 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
fuente
2

R, 111

Probablemente mucho espacio para mejorar esto en este momento

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

Corre con advertencias

> 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
fuente
@AlexA. Advertencias causadas por la coacción I%/%bde un lógico en la any()cláusula. `
MickyT
2

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

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

Ampliado con explicación:

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

Original (sin bonificación):

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 bytes gracias a Ypnypn :)

El numero uno
fuente
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")

Uso:

> 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

El núcleo de la función es !sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n}) que, para cada base x de 2 a n, mantenga el cociente n / x siempre que el resto sea 0 y 1. Luego genera el resultado (que es 0 si todos los restos fueron 1 o 0) y lo niega (0 niega a VERDADERO, todo lo demás niega a FALSO). Gracias al alcance de la función, no hay necesidad de hacer una variable ficticia para n. El vector resultante de booleanos se usa para indexar 2:ny, por lo tanto, solo genera las bases para las que funcionó.

plannapus
fuente
1

TI-Basic, 45 bytes

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

Explicación

  • Entrada N
  • Por cada B de 2 a N
    • Si N es solo 0 y 1 en la base B
      • Display B
  • Bucle final

La parte complicada

La segunda línea funciona de la siguiente manera:

  • Por cada X de 0 a log B N
  • B × fParte (iPart (N / B X ) / B) es el enésimo dígito en la base B, contando hacia atrás
  • Considera esto como una lista
  • Para cada elemento, si el dígito es menor que 2, se obtiene 1 (verdadero), de lo contrario 0 (falso)
  • Tome el producto: 1 si todos los elementos son 1

Nota

El programa se ejecuta significativamente más rápido si )se coloca un paréntesis de cierre al final de la segunda línea. Vea aquí para más información sobre esto.

Ypnypn
fuente
1

TI-BASIC, 31 29

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

Esto es probablemente óptimo para TI-BASIC.

Explicación:

randIntNoRep(1,32)devuelve una permutación aleatoria de los números del 1 al 32 (todo lo que necesitamos es esos números en algún orden; TI-BASIC no tiene nada como el comando iota de APL). 32 elementos son suficientes porque la base más pequeña posible es 2 y el número más grande es 2 ^ 32-1. B^randIntNoRep(1,31)eleva esa lista a la potencia Bth, lo que resulta en la lista que contiene todosB^1,B^2,...,B^32 (en algún orden).

Luego, la entrada (en la Ansvariable wer, que se ingresa en el formulario [number]:[program name]) se divide por ese número. Si su entrada es 42 y la base es 2, el resultado será la lista21,10.5,5.25,...,42/32,42/64,[lots of numbers less than 1/2] , nuevamente en algún orden.

Tomar la parte fraccionaria y multiplicar el número por su base da el dígito en esa posición en la representación de la base-b. Si todos los dígitos son menores que 2, entonces el dígito más grande será menor que 2.

Como dijo Ypnypn, un paréntesis de cierre en el For declaración acelera esto debido a un error del analizador.

31-> 31: se guardó un byte pero se corrigieron los errores de redondeo que agregaron el byte nuevamente.

31-> 29: se guardaron dos bytes usando en RandIntNoRep()lugar de cumSum(binomcdf()).

lirtosiast
fuente
TI-BASIC tiene una función de secuencia?
Sr. Llama
Sí, el comando es seq(expression, variable, start, end[, step]). Si no se da ningún paso, el valor predeterminado es 1. Sin embargo, cumSum(binomcdf(31,0es de 8 bytes mientras que seq(X,X,1,32es de 9 bytes.
lirtosiast
Ah, eso lo explica. No estoy familiarizado con los trabajos de puntuación en TI-Basic.
Sr. Llama
1

Jalea , 9 bytes

³bṀỊµÐfḊY

Pruébalo en línea!

Hecho junto a caird coinheringaahing en el chat .

Cómo funciona

³bṀỊµÐfḊY Programa completo.

     Filterf Filtre el rango generado implícitamente [1, entrada].
    µ Inicia una nueva cadena monádica.
³b Convierta la entrada a la base del número actual, como una lista.
  Ṁ Máximo.
   Ị Insignificante. Comprueba si abs (Z) ≤ 1.
       Ḋ Dequeue; Elimina el primer elemento de la lista (para soltar la base 1).
        Y Únete por nuevas líneas.
Sr. Xcoder
fuente
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ón previa:

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}

Comprobar:

f(82000)
Object { 2: "10100000001010000", 3: "11011111001", 4: "110001100", 5: "10111000", 81999: "11", 82000: "10" }
Qwertiy
fuente
Aquí no tienes entrada ni salida.
edc65
0

JavaScript ( ES6 ) 65

68 bytes para una función con un parámetro y salida de consola.

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

65 bytes con E / S a través de una ventana emergente

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

Reclamando la bonificación: 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
fuente
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}

Inicialmente se olvidó de los requisitos de entrada ... Afortunadamente, esos no agregaron demasiado extra.

Cuenta
fuente
0

Perl 5 , 63 bytes

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

Pruébalo en línea!

No hay bonificación en esto porque puntúa muy ligeramente mejor que mi versión con la bonificación:

Perl 5 , 85 bytes * 0.75 = 63.75

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

Pruébalo en línea!

Xcali
fuente