All about basic binary

Question

Please excuse the punny title.

This is a question is inspired by A Curious Property of 82000. In it, the author points out that the number 82000 is binary in base 2, 3, 4, and 5. The post then poses the question "is there a number that is binary in bases 2, 3, 4, 5, and 6"? (For those curious, I've checked values up to 10^1,000,000 and so far the answer is no.)

This got me thinking: given a number, what bases is it binary in?

Our curious number, 82000, is actually binary in six bases:

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

Not all numbers will have binary bases that are sequential. Consider the number 83521. It's binary in bases 2, 17, 289, 83520, and 83521.

Your challenge is to determine and display which bases a number is binary in.

Rules

• A number is considered "binary" in a given base if its representation in that base consists of only zeroes and ones. 110110 is a binary value, while 12345 is not, A380F is definitely not.
• Your number will be provided on standard input. It will be an integer value between 2 and 2^32-1 inclusive and will be provided in base-10 format.
• In ascending order, display each base greater than one that the number is binary in. Each base should be on its own line. If you include the binary value in that base (see the bonus scoring below), separate the base and the binary value with a space. Only output to standard out will be judged, standard error and other sources will be ignored.

Scoring

Your score is your program's size in bytes. The lower the score, the better.

Bonus:
If your program also outputs the binary values in the found bases, multiply your score by 0.75
Your displayed binary value should have no extra punctuation, no extraneous zeroes, no decimal point, just zeroes and ones.

Examples

Input:

82000

Output (receives bonus):

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

Input:

1234321

Output (no bonus):

2
1111
1234320
1234321

Answer 1

Pyth, 14 13

jbf!-jQTU2tSQ

Thanks to Jakube for pointing out the new S function.

Try it here.

The online version is too slow to do 1234321. This simply converts the input to each base from 2 to itself and discards the results that contain values other than 0 and 1.

Explanation:

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

---

In addition, this is a (not well golfed now well golfed, again thanks to Jakube) bonus version (20 * .75 = 15):

VQI!-JjQK+2NU2pdKjkJ

Try it here

Answer 2

Julia, 72 70 bytes

It's actually longer with the bonus, so no bonus here.

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

This reads a line from STDIN, converts it to an integer, and prints the result. Despite being a brute force method, the input 1234321 took less than 1 second for me.

Ungolfed + explanation:

# 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 -> i ∈ 0:1, digits(n, j))
        # Print the base on its own line
        println(j)
    end
end

Examples:

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

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

NOTE: If input can be taken as a function argument rather than from STDIN (awaiting confirmation from the OP), the solution is 55 bytes.

Answer 3

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

Here is the no bonus version, 20 bytes:

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

Try this here.

Just for fun, here is the bonus version, 27 bytes:

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

Try it online here

Answer 4

Mathematica, 59 bytes

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

Ugh... IntegerDigits D:

There isn't really much to explain about the code... 12 bytes are wasted by the requirement for using STDIN and STDOUT.

I don't think I can claim the bonus. The best I've got is 84 bytes (which yields a score over 60):

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

Answer 5

Python 2, 88 86 80

Fairly straightforward, no bonus. Python is nice and lenient with global variables.

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

Best I've managed to get for the bonus is 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)

Answer 6

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

Pretty straightforward iterative approach.

Without the bonus, this is 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

Answer 7

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

Since SQL is known to be wonderful at these sorts of challenges, I thought I better put one together :) The bonus was really worthwhile for this one.
It should comply with spec, but I have no easy way to test the COPY I FROM STDIN.
Edit Fixed order. Changed the way column R is handled to use an 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

As a test I just used straight inserts into the I table. Test run expanded and commented.

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

Answer 8

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

Usage example (note: binary values are lsb first):

p 82000

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

Without input/output restrictions, i.e input via function argument, output in native format via 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]

Returns a list of (base,value) pairs. The values are lsb first, e.g. (newlines/spaces added for better display):

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

Answer 9

R, 111

Probably a lot of room to improve this at the moment

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

Runs with warnings

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

Answer 10

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

Expanded with explanation:

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 (without 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 bytes thanks to Ypnypn :)

Answer 11

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

Usage:

> 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

The core of the function is !sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n}) which, for each base x from 2 to n, keep the quotient n/x as long as the remainder is either 0 and 1. It then outputs the result (which is 0 if all remainders were either 1 or 0) and negates it (0 negates to TRUE, everything else negates to FALSE). Thanks to function scope, there is no need to make a dummy variable for n. The resulting vector of booleans is then used to index 2:n and therefore outputs only the bases for which it worked.

Answer 12

Jelly, 9 bytes

³bṀỊµÐfḊY

Try it online!

Done alongside caird coinheringaahing in chat.

How it works

³bṀỊµÐfḊY    Full program.

     Ðf      Filter the implicitly generated range [1, input].
    µ        Starts a new monadic chain.
³b           Convert the input to the base of the current number, as a list.
  Ṁ          Maximum.
   Ị         Insignificant. Checks if abs(Z) ≤ 1.
       Ḋ     Dequeue; Removes the first element of the list (to drop base 1).
        Y    Join by newlines.

Answer 13

APL (Dyalog Extended), 28 bytes, 28 * 0.75 = 21

{{⍵⌿⍨∧/2>↑2⌷⍉⍵}(⍪,⊤∘⍵¨)1↓⍳⍵}

1↓⍳⍵ all numbers from 2 to ⍵

(⍪,⊤∘⍵¨) each number with the representation of ⍵ in that base

{⍵⌿⍨∧/2>↑2⌷⍉⍵} dfn to filter

↑2⌷⍉⍵ 2nd column as a matrix

2> is 2 greater than?

∧/ boolean and

⍵⌿⍨ replicate Try it online!

Answer 14

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

Explanation

• Input N
• For every B from 2 to N
  • If N is just 0 and 1 in base B
    • Display B
• End loop

The complicated part

The second line works as follows:

• For every X from 0 to log_B N
• B × fPart(iPart(N / B^X) / B) is the Nth digit in base B, counting backwards
• Consider this as a list
• For each element, if the digit is less than 2, yield 1 (true), else 0 (false)
• Take the product: 1 iff all elements are 1

Note

The program runs significantly faster if a closing parenthesis ) is placed at the end of the second line. See here for more about this.

Answer 15

TI-BASIC, 31 29

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

This is probably optimal for TI-BASIC.

Explanation:

randIntNoRep(1,32) returns a random permutation of the numbers from 1 to 32 (All we need is those numbers in some order; TI-BASIC doesn't have anything like APL's iota command). 32 elements is enough because the smallest possible base is 2 and the largest number is 2^32-1. B^randIntNoRep(1,31) raises that list to the Bth power, which results in the list containing all of B^1,B^2,...,B^32 (in some order).

Then the input (in the Answer variable, which is input to in the form [number]:[program name]) is divided by that number. If your input is 42 and the base is 2, the result will be the list 21,10.5,5.25,...,42/32,42/64,[lots of numbers less than 1/2], again in some order.

Taking the fractional part and multiplying the number by your base gives the digit at that position in the base-b representation. If all digits are less than 2, then the greatest digit will be less than 2.

As Ypnypn stated, a closing parenthesis on the For statement speeds this up due to a parser bug.

31->31: Saved a byte but fixed rounding errors which added the byte again.

31->29: Saved two bytes by using RandIntNoRep() instead of cumSum(binomcdf()).

Answer 16

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}

Previous version:

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}

Check:

f(82000)
Object { 2: "10100000001010000", 3: "11011111001", 4: "110001100", 5: "10111000", 81999: "11", 82000: "10" }

Answer 17

JavaScript (ES6) 65

68 bytes for a function with a parameter and console output.

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

Claiming the 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))

Answer 18

Mathematica, 76 * 0.75 = 57

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

Initially forgot about the input requirements... Fortunately, those didn't add too much extra.

Answer 19

Ruby, 44 bytes

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

Try it online!

Answer 20

Perl 5, 63 bytes

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

Try it online!

No bonus on this because it scores very slightly better than my version with the bonus:

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

Try it online!

Answer 21

Husk, ¹¹ 10 bytes

¶tfoΛε`B¹ḣ

Try it online!

-1 byte from Zgarb.

Explanation

¶tfoΛ<2`B¹ḣ
          ḣ list from 1..n
  f         filter based on the result of the following
   o        composition of 2 functions
       `B¹  the input in base n as digits
    Λ<2     are all digits < 2?
 t          remove first element
¶           join with newlines

Answer 22

Japt -R, 11 bytes

õ2 f@ìX e§1

Try it

õ2 f@ìX e§1     :Implicit input of integer U
õ2              :Range [2,U]
   f            :Filter by
    @           :Passing each X through the following fuction
     ìX         :  Convert U to base X digit array
        e       :  All
         §1     :    <=1
                :Implicit output, joined with newlines