Можно ли записать это число в формате (3 ^ x) - 1?

41

Вызов:

Создайте программу, которая принимает положительное целое число и проверяет, можно ли ее записать в виде (3 ^ x) -1, где X - другое положительное целое число .

Если это возможно, выведите X

Если это невозможно, выведите -1 или ложное утверждение.

Пример входов / выходов

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

2

Его можно записать как (3 ^ 1) - 1, поэтому мы выводим x, равное 1

Выход:

1

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

26

26 можно записать как (3 ^ 3) - 1, поэтому мы выводим x (3)

Выход:

3

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

1024

1024 нельзя записать в виде (3 ^ x) - 1, поэтому мы выводим -1

Выход:

-1

Это поэтому выигрывает наименьшее количество байтов


Родственный OEIS: A024023

П. Ктинос
источник
4
Я прошу вывести X, потому что считаю, что так сложнее. На мой взгляд, просто найти формат 3 ^ x - 1 было бы слишком легко для решения проблемы.
П. Ктинос
2
Если только это не ложное утверждение на вашем языке программирования, то нет.
П. Ктинос
2
Могу ли я хотеть, чтобы число вводилось в троичной системе?
Джон Дворак
2
необходимость обрабатывать неотрицательные интергеры делает 0 3^0-1 действительным выводом и, следовательно, не может использоваться как ложное,
Jasen
2
Любой, кто думает об использовании log()в своем ответе, должен подтвердить, что он дает правильный ответ 5при 242 вводе.
Ясен

Ответы:

23

Mathematica, 21 16 байт

-1&@@Log[3,#+1]&

Использует символические вычисления Mathematica. Если#+1 это степень трех, то Log[3,#+1]вычисляется целочисленный результат, который является атомарной величиной. В противном случае мы получим Log[#+1]/Log[3]как есть. Поскольку это не атомарное значение, это выражение, которое всегда имеет форму head[val1,val2,...]. В этом случае это на самом деле что-то вроде Times[Power[Log[3], -1], Log[#+1]].

Мы различаем два случая, применяя другую функцию к результату. Что действительно применяет приложение, так это то, что оно заменяет headчасть выражения. Поскольку целочисленные результаты являются атомарными, применение любой функции к ним ничего не делает. В частности f @@ atom == atom.

Однако в другом случае голова заменяется. Функция, которую мы используем, -1&это простая функция, которая игнорирует свои аргументы и возвращает -1. Таким образом, мы получаем что-то -1&[Power[Log[3], -1], Log[#+1]]в нецелых случаях, что напрямую оценивается -1. Специальный корпус с помощью магии.

Мартин Эндер
источник
13

Python, 46 44 байта

lambda x:max(n*(3**n-1==x)for n in range(x))

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

В этом случае 0будет ложное значение. Спасибо @ mbomb007 за указание на мой неверный вывод, а также 2 байта без []экономии.

nmjcman101
источник
Вы можете переписать как [n for n in range(x)if 3**n-1==x]для -4 байта, пустой список как ложный
Род
Исправлено, спасибо! @ Род тогда это возвратило бы [n] вместо n, я думаю
nmjcman101
@ nmjcman101 это не должно быть проблемой
Род
@Rod Я бы предпочел строго придерживаться спецификации на данный момент
nmjcman101
@Rod Если требуется вывести целое число, вы не можете вывести его в списке, если это не разрешено OP.
mbomb007
13

Haskell, 35 байт

f x=last(-1:[i|i<-[1..x],3^i-1==x])

Пример использования: f 26-> 3.

Ними
источник
PS: попробуйте онлайн! поддерживает Haskell! (Хороший ответ кстати!)
flawr
11

05AB1E , 7 байтов

3IÝm<¹k

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

объяснение

3        # push 3 
 I       # push input
  Ý      # range [0 ... input]
   m     # 3^[0 ... input]
    <    # -1
     ¹k  # find index of input, return -1 if not found
Emigna
источник
05AB1E очевидно хорош в базовом преобразовании, это действительно лучший подход?
Ясен
1
@Jasen: все мои попытки конвертировать базы оказались длиннее. Если есть лучший способ, чем этот, я не вижу его. Не стесняйтесь доказать, что я не прав :)
Emigna
Честно говоря, я только прочитал описание языка и, таким образом, ожидал увидеть 5-байтовое решение ....
Jasen
1
@Jasen <3zm©.ïi®- самый близкий мне не использующий диапазоны, как он.
Волшебная Урна Осьминога
1
3DÝms<k... Неважно ... Не могу сбрить еще один байт, могу поклясться, что смогу.
Волшебная Урна Осьминога
9

Желе , 5 байт

R3*’i

Выходы х или 0 (ложь).

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

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

R3*’i  Main link. Argument: n

R      Range; yield [1, ..., n].
 3*    Map each k to 3**k.
   ’   Decrement the results.
    i  First index of n (0 if not found).
Деннис
источник
6

Python 2, 41 байт

f=lambda n,i=0:i*0**n or n%3/2*f(n/3,i+1)

Рекурсивная функция, которая возвращает 0несоответствующие входы. Неоднократно наполовину делит ввод на 3, считая количество шагов i, которое выводится в конце. Но если какой-либо шаг выдает значение n, которое не равно 2 по модулю 0, число не соответствует значению 3^i-1, поэтому результат умножается на 0.

XNOR
источник
6

Perl, 31 байт

say grep{3**$_-1==$i}0..($i=<>)

Требуется -Eфлаг для запуска:

perl -E 'say grep{3**$_-1==$i}0..($i=<>)' <<< 26

Пояснения:
grep{3**$_-1==$i}0..($i=<>)возвращает список элементов диапазона 0..$_(т. Е. От 0 до ввода), который удовлетворяет критерию 3**$_-1==$i. Только один элемент может удовлетворить этот тест, поэтому эта инструкция вернет массив из 0 или 1 элемента. Затем мы печатаем этот список: либо «то», Xлибо «ничего» (что неверно).

папа
источник
5

Pyth, 11 байт

?-JjQ3 2ZlJ

Преобразует в базу 3 и проверяет равенство [2, 2, ..., 2].

orlp
источник
Вы можете уменьшить это на один байт с ?-2JjQ3ZlJ, так как <col> <num>и<num> <col> взаимозаменяемы для -в Pyth.
notjagan
5

JavaScript (ES7), 38 36 34 байта

f=(n,k=33)=>3**k-n-1&&--k?f(n,k):k

Или просто 30 29 байт, если можно выйти с ошибкой при ошибке:

f=(n,k)=>~(n-3**k)?f(n,-~k):k

Тест

Arnauld
источник
5

Java 8, 37 58 67 байт

i->{String s=i.toString(i,3);return s.matches("2*")?s.length():-1;}

Эта лямбда вписывается в Function<Integer, Integer> ссылку и использует простой трюк с базой 3.

На этот раз все должно работать правильно.


источник
3
Разве это не напечатало бы только True или False, когда это можно записать в формате? Но я спросил у экспоненты, когда результат
верен
2
Это гений! +1 за очень умный подход
DJMcMayhem
Это умно ... я верю, что вы можете удалить паренсы и просто сделать это i->. Кроме того, если вы берете iкак Long, вы можете использовать a.toString(...)(идентификаторы будут выдавать некоторые предупреждения о неправильном использовании статических функций, но должны компилироваться). Однако, как сказал OP, вам нужно возвращать значение, а не только True или False.
FlipTack
Если лямбда хранится в другом типе функции, то статический трюк работает. Я также исправил возвращаемое значение. Должно быть, я пропустил эту часть.
5

Обработка, 60 56 байт

void q(float n){n=log(n+1)/log(3);print(n>(int)n?-1:n);}

Выходы -1 если ложные.

объяснение

void q(float n){              // n is input
  n=log(n+1)/log(3);          // finds X in 3^X+1=n as a float (here we'll storing that in n)
  print(n>(int)n?-1:n);       // checks if the float is greater than
                              // the number rounded down (by int casting)
                              // if it is greater, output -1
                              // otherwise output X
}

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

Альтернативное решение

void z(float n){int c=0;for(++n;n>1;c++)n/=3;print(n==1?c:-1);}

за 63 байта, но я думаю, что этот альт может быть короче, чем оригинальное решение. Я работаю над этим.

Kritixi Lithos
источник
@FlipTack Да, я знал, что это не будет на Java. Я просто спросил, так как не был уверен, что Processing не добавила что-то подобное. «Отличное значение», которое нужно было использовать, было -1, а не 0. С тех пор оно было изменено, поэтому я, вероятно, исправлю свои комментарии по этому поводу.
Geobits
Подождите, так я могу вернуться 0сейчас?
Критиси Литос
Я бы все еще сказал нет. Этот вопрос дает альтернативное целочисленное значение для использования в случае ложности, но 0это не ложь в Java / Processing, о которой я знаю.
Geobits
Думаю, обработка должна была быть менее разносторонней, чем Java
Павел
@Pavel Но я не использую лямбды: /
Kritixi Lithos
4

Брахилог , 8 байт

,3:.^-?,

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

Выводит значение, если оно истинно и false.если это невозможно.

объяснение

Это прямая транскрипция данного отношения:

,     ,      (Disable implicit unification)
 3:.^        3^Output…
     -?              … - 1 = Input
Fatalize
источник
Вы можете почти гольф это до 7 байт , как +~^r~:3, но , к сожалению , ~:не делать то , что вы могли бы ожидать (вероятно , потому , что :это синтаксис , а не встроено в него ), и , кажется, обрабатывают идентично :.
@ ais523 Это верно, :является управляющим символом и ~работает только с предикатами.
фатализировать
3

Perl 6 ,  25  24 байта

{first $_==3** *-1,0..$_}

Попытайся

{first $_==3***-1,0..$_}

Удаление места после ** работ, потому что он длиннее, чем другой инфиксный оператор, который может совпадать *.
Так …***…разбирается как … ** * …а не … * ** ….

Попытайся

Expanded:

{  # bare block lambda with implicit parameter 「$_」

  first
    $_ == 3 ** * - 1,   # WhateverCode lambda
    #          ^- current value

    0 .. $_             # a Range up-to (and including) the input

}
Брэд Гилберт b2gills
источник
3

R, 24 байта

Отличный подход от ответа Plannapus , и на один байт короче!

match(scan(),3^(1:99)-1)

Генерирует все целые числа от 3^1-1до 3^99-1и проверяет соответствие стандартного ввода. Если это так, он возвращает индекс, по которому он совпадает, то есть x. Если нет, возвращаетNA как ложное значение.

Между прочим, он примет несколько значений в качестве входных данных и протестирует все из них, что является отличной особенностью.

rturnbull
источник
3

Пролог, 20 байт

d(A,X):-A#=(3**X)-1.

Этот язык чертовски крут.

| ?- d(1024,X).

no
| ?- d(26,X).

X = 3

yes
| ?- d(2,X).

X = 1

yes
Имя Макчэндж
источник
2

05AB1E , 9 байтов

DÝ3sm<Q1k

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

Отпечатки -1 для ложных.

D         # Duplicate the input
 Ý3sm     # Push [0 .. input]^3 (e.g. [0^3, 1^3, 2^3, 4^3 ...])
     <    # subtract 1
      Q   # push a 1 everywhere that equals the input, and 0 everywhere else
       1k # push the index of the 1, or -1 if not found
          # implicit output
Райли
источник
2

MATL , 8 байт

3i:^qG=f

Это выводит число x если оно существует, или иначе ничего не выводит, что ложно.

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

объяснение

3    % Push 3
i    % Input n
:    % Range: gives `[1 2 ... n]
^    % Power, element-wise. Gives [3^1 3^2 ... 3^n]
q    % Subtract 1, element-wise. Gives [3^1-1 3^2-1 ... 3^n-1]
=    % Test for equality. Contains 'true' at the position x, if any,
     % where 3^x-1 equals n
f    % Find. Gives index of the 'true' position, which ix x; or gives
     % an empty array if no such position exists. Implicitly display
Луис Мендо
источник
2

Japt , 11 байт

o æ@U+1¥3pX

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

Большое спасибо ETHproductions за помощь!

Оливер
источник
2

Python 3, 74 66 64 байта

-10 байт благодаря @ mbomb007, @FlipTack и @ nmjcman101

from math import*
def f(n):x=ceil(log(n,3));print((3**x-1==n)*x)
dfernan
источник
Вы можете поместить весь свой код в одну строку и использовать from math import*. Также return n==3**x-1and x.
mbomb007
@ mbomb007 Функциям разрешено печатать результат STDOUT, поэтому вы можете изменить этот возврат на печать.
FlipTack
Если вы представляете это как решение SageMath, а не как решение Python, вы можете полностью удалить первую строку.
Федерико Полони
Наряду с другим сокращением до 65 байт можно использовать import mathи math.ceilдля одного байта. Также вы можете обратиться 3**x-1==n and xкx*(3**x-1==n)
nmjcman101
2

C, 56 байтов

 n;f(a){n=0;for(a++;!(a%3)&&(a/=3);++n);return --a?-1:n;}

добавьте один к входу и затем несколько раз делите на три, пока остаток не будет найден, если он достигнут, верните счетчик делений, иначе -1

Jasen
источник
Сохраните один байт a%3<1вместо !(a%3). Еще один с 0фальшивкой.
Тит
Предполагая, что вы используете GCC для компиляции, вы можете сохранить в общей сложности 10 (11) байтов: вам не нужно инициализировать n равным нулю, если вы знаете, что вызовете эту функцию только один раз, поскольку тогда n будет по умолчанию нулем ( потому что это глобально) - это на 4 байта меньше; Также вам не нужно возвращать оператор, написав, a=--a?-1:n;вы сэкономите 5 байтов. если не пустая функция не имеет возврата, она просто использует последнее присваивание. Также, что сказал @Titus.
Этаоин Шрдлу
1
Предлагаю a%3?0:(a/=3)вместо!(a%3)&&(a/=3)
потолок кошка
2

Утилиты Bash / Unix, 37 35 байт

bc<<<`dc<<<3o$1p|grep ^2*$|wc -c`-1

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

Использует dc для преобразования в базу 3, проверяет, что полученная строка равна всем 2, подсчитывает количество символов (включая символ новой строки), а затем использует bc для вычитания 1.

Если число в базе 3 - это не все 2, то grep ничего не выводит (даже перевод строки), поэтому количество символов равно 0, а вычитание 1 дает -1.

Митчелл Спектор
источник
2

C составлен с Clang 3.8.1, 53 , 52 , 54 , 51 байт

n;f(y){y++;for(n=0;y%3==0;y/=3)n++;return y^1?0:n;}

@SteadyBox уже опубликовал решение на C, но я использую другой подход.

@ Спасибо Jasen за помощь в сохранении байтов.

Уэйд Тайлер
источник
1
да, но это работает? Сравнение поплавков на равенство часто является рецептом неожиданного сбоя (попробуйте большие входные данные)
Jasen
@Jasen Хм, еще не пробовал, но в C logвозвращается, doubleтак что, возможно, это сработает.
Уэйд Тайлер
double - это тип значения с плавающей запятой, поэтому проблема сохраняется.
Ясен
кажется, работает нормально для 3 ^ 19, который, вероятно, достаточно велик.
Ясен
@Jasen Это не работает в течение 3 ^ 10
Уэйд Тайлер
2

C, 42 байта, оптимизированный от Wade Tyler's

n;f(y){for(n=0;y%3>1;y/=3)n++;return!y*n;}

Пытаться

C 37 байт, без return

n;f(y){for(n=0;y%3>1;y/=3)n++;n*=!y;}

Пытаться

nявляется глобальным, но (I)MULможет иметь только операнд dest в регистре, поэтому нужно поместить вEAX (обычный выбор) и переместить туда

JavaScript 6, 32 байта

f=(y,n)=>y%3>1?f(y/3|0,-~n):!y*n
;[1,2,3,8,12,43046720].forEach(x=>console.log(f(x)))

Если «ложь» должна быть такой же, 33 байта:

f=(y,n)=>y%3>1?f(y/3|0,-~n):!y&&n
l4m2
источник
2

Пыть , 10 9 байт

←⁺3ĽĐĐƖ=*

Объяснение:

←                Get input
 ⁺               Add one
  3Ľ             Log base 3
    ĐĐ           Triplicate top of stack
      Ɩ          Convert top of stack to integer
       =         Check for equality between top two on stack
        *        Multiply by log_3(input+1)


Сохраненный байт с помощью функции приращения вместо явного добавления 1

mudkip201
источник
в какой кодовой странице эти 9 байтов? (в UTF-8 это 17 байт)
Jasen
1

Python, 64 байта

Выводится, Falseесли число не может быть записано в этом формате.

def f(n):L=[3**x-1for x in range(n)];print n in L and L.index(n)

Это также работает в 64 байтах и ​​печатает пустую строку как ложный вывод:

def f(n):
 try:print[3**x-1for x in range(n)].index(n)
 except:0

Креативное решение для 65 байтов, вывод 0для фальсификации:

lambda n:-~",".join(`3**x-1`for x in range(n+1)).find(',%s,'%n)/2
mbomb007
источник
Не выводит xни -1.
17
Программа должна выводить xвместо nв случае совпадения.
17
Нет, он должен вывести положительное целое число, которое при замене на X, вы получите ввод. Вопрос относится к X как к переменной, а не как к строке
P. Ktinos
@ P.Ktinos Исправлено.
mbomb007
1

Юлия, 30 байт

n->findfirst(n.==3.^(0:n)-1)-1

Это простая функция - она ​​создает вектор, который имеет trueтолько в соответствующей позиции в 3^a-1, где aвектор, содержащий целые числа от 0 до n. Он находит «первую» позицию, которая равна true1, и вычитает 1 (если это все false, find оценивается как ноль, и возвращает -1).

Как 0:nи 0в первом месте, вычитание 1 корректирует индексирование и также допускает -1ложный ответ.

Глен О
источник
1

Pyth 8 байтов

xm^3dUQh

     UQ  # generate all values 1..Q (Q is the input)
 m^3d    # map 3^d over this ^ list
x      h # find the input+1 (hQ) in the result of the last command

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

прут
источник