Пожалуйста, извините за заголовок.

Этот вопрос вдохновлен «Любопытной собственностью» 82000 . В нем автор указывает, что число 82000 является двоичным в основаниях 2, 3, 4 и 5. В этом посте возникает вопрос «есть ли число двоичное в основаниях 2, 3, 4, 5 и 6?» «? (Для любопытных я проверил значения до 10 ^ 1 000 000, и пока ответ - нет.)

Это заставило меня задуматься: учитывая число, на каких основаниях оно является двоичным?

Наше любопытное число 82000 на самом деле является двоичным по шести базам:

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

Не все числа будут иметь двоичные базы, которые являются последовательными. Рассмотрим число 83521. Это двоичное в базах 2, 17, 289, 83520 и 83521.

Ваша задача состоит в том, чтобы определить и отобразить, в каких основаниях число является двоичным.

правила

• Число считается «двоичным» в данной базе, если его представление в этой базе состоит только из нулей и единиц. 110110это двоичное значение, а 12345нет,A380F это определенно нет.
• Ваш номер будет указан на стандартном вводе. Это будет целочисленное значение от 2 до 2 ^ 32-1 включительно и будет предоставлено в формате base-10.
• В порядке возрастания отобразите каждую базу больше единицы, в которой число является двоичным. Каждая база должна находиться в отдельной строке. Если вы включили двоичное значение в эту базу (см. Оценку бонусов ниже), разделите базу и двоичное значение пробелом. Будет оцениваться только вывод на стандартный выход, стандартная ошибка и другие источники будут игнорироваться.

счет

Ваша оценка - это размер вашей программы в байтах. Чем ниже оценка, тем лучше.

Бонус :
если ваша программа также выводит двоичные значения в найденных базах, умножьте ваш счет на 0,75
вашего отображаемого двоичного значения не должно быть лишних знаков препинания, никаких посторонних нулей, никаких десятичных точек, только нули и единицы.

Примеры

Входные данные:

82000

Вывод (получает бонус):

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

Входные данные:

1234321

Выход (без бонуса):

2
1111
1234320
1234321

Pyth, 14 13

jbf!-jQTU2tSQ

Спасибо Jakube за указание на новую Sфункцию.

Попробуй это здесь.

Интернет-версия слишком медленная, чтобы сделать 1234321 . Это просто преобразует входные данные для каждой базы из 2 в себя и отбрасывает результаты, которые содержат значения, отличные от 0 и 1.

Объяснение:

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

Кроме того, это бонусная версия ( не очень хорошо играемая в гольф, опять же благодаря Jakube) (20 * .75 = 15):

VQI!-JjQK+2NU2pdKjkJ

Попробуй здесь

Юлия, 72 70 байт

Это на самом деле больше с бонусом, поэтому здесь нет бонуса.

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

Это читает строку из STDIN, преобразует ее в целое число и печатает результат. Несмотря на то, что метод «грубой силы», ввод 1234321 занял у меня менее 1 секунды.

Ungolfed + объяснение:

# 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

Примеры:

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

ПРИМЕЧАНИЕ . Если входные данные могут быть приняты в качестве аргумента функции, а не из STDIN (в ожидании подтверждения от OP), решение имеет 55 байтов.

CJam, 20 байтов (или 27 байтов * 0,75 = 20,25)

Вот версия без бонуса, 20 байт:

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

Попробуйте это здесь.

Просто для удовольствия, вот бонусная версия, 27 байт:

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

Попробуйте онлайн здесь

Mathematica, 59 байт

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

Тьфу ... IntegerDigits D:

На самом деле не так много объяснений по поводу кода ... 12 байтов тратятся впустую из-за необходимости использовать STDIN и STDOUT.

Я не думаю, что могу претендовать на бонус. Лучшее, что у меня есть, это 84 байта (что дает оценку более 60):

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

Питон 2, 88 86 80

Довольно просто, без бонусов. Python хорош и мягок с глобальными переменными.

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

Лучшее, что мне удалось получить за этот бонус - 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)

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

Довольно простой итеративный подход.

Без бонуса это 73 байта:

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

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

Поскольку известно, что SQL прекрасно справляется с подобными задачами, я подумал, что лучше собрать его вместе :) Бонус действительно стоил этого.
Это должно соответствовать спецификации, но у меня нет простого способа проверить COPY I FROM STDIN .
Редактировать Фиксированный заказ. Изменен способ обработки столбца R для использования массива.

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

В качестве теста я просто использовал прямые вставки в Iтаблицу. Тестовый прогон расширен и прокомментирован.

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

Haskell 109 * 0,75 = 81,75 байт

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

Пример использования (примечание: двоичные значения сначала lsb):

p 82000

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

Без ограничений ввода / вывода, т.е. ввод через аргумент функции, вывод в собственном формате через REPL):

Haskell, 67 * 0,75 = 50,25 байт

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

Возвращает список пар (база, значение). Сначала значения lsb, например (добавлены новые строки / пробелы для лучшего отображения):

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

R 111

Вероятно, есть много возможностей для улучшения этого на данный момент

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

Работает с предупреждениями

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

Java, 181 155,25 (207 * 0,75) 151,5 (202 * .75) байтов

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

Дополнено объяснением:

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

Оригинал (без бонуса):

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 байта благодаря Ypnypn :)

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

Использование:

> 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

Суть функции заключается в том, !sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n})что для каждого основания x от 2 до n сохраняется частное n / x до тех пор, пока остаток равен 0 и 1. Затем выводится результат (который равен 0, если все остатки равны 1 или 0) и отрицает его (0 отрицает ИСТИНА, все остальное отрицает ЛОЖЬ). Благодаря области действия функции нет необходимости создавать фиктивную переменную для n. Полученный вектор логических значений затем используется для индексации 2:nи, следовательно, выводит только те базы, для которых он работал.

TI-Basic, 45 байт

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

объяснение

• Вход N
• Для каждого B от 2 до N
  • Если N только 0 и 1 в базе B
    • Дисплей Б
• Конец цикла

Сложная часть

Вторая строка работает следующим образом:

• Для каждого X от 0 до log _B N
• B × fPart (iPart (N / B ^X ) / B) - это N-ая цифра в базе B, считая в обратном направлении
• Считайте это списком
• Для каждого элемента, если цифра меньше 2, выведите 1 (true), иначе 0 (false)
• Возьмите продукт: 1, если все элементы 1

Заметка

Программа работает значительно быстрее, если закрывающая скобка )ставится в конце второй строки. Смотрите здесь для получения дополнительной информации об этом.

TI-BASIC, 31 29

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

Это, вероятно, оптимально для TI-BASIC.

Объяснение:

randIntNoRep(1,32)возвращает случайную перестановку чисел от 1 до 32 (все, что нам нужно, это числа в некотором порядке; в TI-BASIC нет ничего похожего на команду iota APL). 32 элемента достаточно, потому что наименьшее возможное основание - 2, а наибольшее - 2 ^ 32-1. B^randIntNoRep(1,31)возводит этот список в степень Bth, что приводит к списку, содержащему все B^1,B^2,...,B^32(в некотором порядке).

Затем вход (в Ansпеременной wer, которая вводится в форму [number]:[program name]) делится на это число. Если вы введете 42, а база равна 2, результатом будет список21,10.5,5.25,...,42/32,42/64,[lots of numbers less than 1/2] , опять же в некотором порядке.

Взяв дробную часть и умножив число на вашу базу, вы получите цифру в этой позиции в представлении base-b. Если все цифры меньше 2, то наибольшая цифра будет меньше 2.

Как заявил Ypnypn, закрывающая скобка на For операторе ускоряет это из-за ошибки синтаксического анализатора.

31-> 31: Сохранен байт, но исправлены ошибки округления, которые снова добавили байт.

31-> 29: сохранил два байта, используя RandIntNoRep()вместо cumSum(binomcdf()).

Желе , 9 байт

³bṀỊµÐfḊY

Попробуйте онлайн!

Совершено рядом с Кайрдом в чате .

Как это работает

³bṀỊµÐfḊY Полная программа.

     Ìf Отфильтровать неявно сгенерированный диапазон [1, вход].
    Запускает новую монадическую цепочку.
³b Преобразовать ввод в базу текущего номера в виде списка.
  Ṁ максимум.
   Ị незначительный. Проверяет, если abs (Z) ≤ 1.
       Ḋ Dequeue; Удаляет первый элемент списка (чтобы удалить базу 1).
        Y Присоединяйтесь к новым строкам.

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}

Предыдущая версия:

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}

Проверьте:

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

JavaScript ( ES6 ) 65

68 байт для функции с параметром и вывода на консоль.

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

65 байтов с вводом / выводом через всплывающее окно

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

Требование бонуса: 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))

Mathematica, 76 * 0,75 = 57

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

Изначально забыл про входные требования ... К счастью, они не добавили слишком много лишних.

Рубин , 44 байта

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

Попробуйте онлайн!

Perl 5 , 63 байта

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

Попробуйте онлайн!

Никакого бонуса по этому поводу, потому что он выиграл немного лучше, чем моя версия с бонусом:

Perl 5 , 85 байт * 0,75 = 63,75

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

Попробуйте онлайн!