Заменить двойки тройками

36

Учитывая положительное целое число п написать код , чтобы взять его разложение на простые множители и замены всех его факторов 2с 3.

Например

12 = 2 * 2 * 3 -> 3 * 3 * 3 = 27

Это код-гольф, поэтому цель состоит в том, чтобы минимизировать количество байтов в вашем ответе.

Контрольные примеры

1 -> 1
2 -> 3
3 -> 3
4 -> 9
5 -> 5
6 -> 9
7 -> 7
8 -> 27
9 -> 9
10 -> 15
11 -> 11
12 -> 27
13 -> 13
14 -> 21
15 -> 15
16 -> 81
17 -> 17
18 -> 27
19 -> 19
20 -> 45
21 -> 21
22 -> 33
23 -> 23
24 -> 81
25 -> 25
26 -> 39
27 -> 27
28 -> 63
29 -> 29
code-golf arithmetic number-theory Мастер пшеницы
источник

Ответы:

63

Фрактран , 3 байта

3/2

Fractran буквально имеет только один встроенный модуль, но он делает именно то, что требует эта задача. (Само по себе также полное по Тьюрингу.)

Язык не имеет стандартизированного синтаксиса или интерпретатора. Этот интерпретатор (в комментарии к сообщению в блоге - это очень простой язык) примет синтаксис, показанный здесь. (Существуют и другие интерпретаторы Fractran с другим синтаксисом, например, некоторые пишут эту программу как 3 2, или даже используют 3и 2как аргументы командной строки, что приведет к счету 0 + 3 байта. Я сомневаюсь, что это можно сделать лучше, чем 3 в уже существующий переводчик.)

объяснение

3/2
 /   Replace a factor of
  2  2
3    with 3
     {implicit: repeat until no more replacements are possible}

источник
10
Разговор о правильном инструменте для работы ..
Кевин Круйссен
23
«Не рекламируйте тривиальные решения, которые используют только простую встроенную функцию». Что ж, в данном случае: знание того, что есть язык «Fractran», имеющий единую встроенную функцию, которая решает эту конкретную задачу, само по себе впечатляет.
Стьюи Гриффин
3
Соответствующий код SO для гольфа (до PPCG): Написать интерпретатора Fractran .
Хоббс
1
@AnderBiguri: Скорее всего, ищем полный по Тьюрингу язык, который очень прост / легок в реализации. Фрактран действительно элегантен, как и брезенты Тьюринга; большинство из них имеют гораздо более грубые края, особые случаи или детали, которые могут быть изменены без особой разницы.
3
@AnderBiguri Похоже, это пришло из его исследований гипотезы Коллатца; он доказал, что обобщение Коллатца эквивалентно Фрактрану и что Фрактран полон по Тьюрингу, поэтому обобщенный Коллатц неразрешим.
Хоббс
21

Python 2 , 28 байт

f=lambda n:n%2*n or 3*f(n/2)

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

Рекурсивно разделите число на 2 и умножьте результат на 3, если число четное. Нечетные числа возвращаются.

32 байта alt:

lambda n:n*(n&-n)**0.58496250072

Попробуйте онлайн . Имеет некоторую ошибку с плавающей точкой. Константа есть log_2(3)-1.

Используется (n&-n)для нахождения наибольшего фактора силы-2 n, который преобразуется 3**kв 2**kвозведение его в степень log_2(3)-1.

XNOR
источник
Хорошо, это мое решение точно!
Пшеничный волшебник
@WheatWizard Я тоже, ага!
Гравитон
18

05AB1E , 4 байта

Ò1~P

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

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

Ò     Compute the prime factorization of the input.
 1~   Perform bitwise OR with 1, making the only even prime (2) odd (3).
   P  Take the product of the result.
Деннис
источник
Это превосходит Jelly на 1 байт просто потому, что
первичная
5
@HyperNeutrino: Я тоже это заметил: «почему Деннис использует 05AB1E? О, идентичный алгоритм, более короткие встроенные имена». Поэтому мне пришлось пойти и найти язык, на котором я мог бы сделать это за еще меньшее количество байтов, используя еще более подходящий набор встроенных функций.
14

Haskell, 24 23 байта

until odd$(*3).(`div`2)

Разделите на два и умножьте на 3 до странного трюка в Хаскеле.

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

Альтернатива с лямбдой вместо функции pointfree и с тем же количеством байтов:

odd`until`\x->div(x*3)2

Изменить: @ ais523 сохранил байт в исходной версии и @ Örjan Johansen в альтернативной версии, поэтому обе версии имеют одинаковую длину. Благодарность!

Ними
источник
3
Лямбда-версия может быть сокращена до odd`until`\x->div(x*3)2.
Орджан Йохансен
2
Оригинальная версия также может быть сокращена на один байт с помощью $замены пары скобок: попробуйте онлайн!
@ ØrjanJohansen: ах, приятно! Спасибо.
Ними
@ ais523: Как я мог пропустить это, спасибо!
Ними
2
Я думаю, что вы забыли удалить пару ()из лямбда-версии
CAD97
8

JavaScript (ES6), 19 байт

f=x=>x%2?x:f(x*1.5)

Хотя вход делится на два, он умножается на 1,5, что эквивалентно делению на 2 и умножению на 3.

ETHproductions
источник
2
x*3/2имеет тот же счетчик
Leaky Nun
1
f=Обычно не требуется для JS.
Кристоф
3
@Christoph Спасибо, но для того, чтобы называть себя, f(x*1.5)ему нужно имя f, следовательно, почему f=оно включено.
ETHproductions
@ETHproductions Хм ... конечно! Я пропустил это. Есть ли мета о том, как именно выглядит вызывающий код?
Кристоф
2
@Christoph Вот соответствующий мета-пост.
ETHproductions
8

Brain-Flak , 76 байт

{{({}[()]<([({})]()<({}{})>)>)}{}([{}]()){{}((({})){}{})<>}<>}<>({}({}){}())

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

объяснение

Эта программа работает, деля число на два и утраивая, пока не получит остаток от деления. Затем он останавливается, удваивается и добавляет единицу к последнему числу.

Более подробное объяснение в конце концов ...

0 '
источник
> Скоро
Мастер Пшеницы
7

Mathematica, 22 19 байтов

Спасибо lanlock4 за сохранение 3 байта!

#//.x_?EvenQ:>3x/2&

Чистая функция, которая выполняет замену несколько раз, один фактор 2 за один раз. Работает на всех натуральных числах менее 2 65537 .

Грег Мартин
источник
Будет x_?EvenQработать вместо x_/;EvenQ@x?
Не дерево
1
Вы совершенно правы, спасибо!
Грег Мартин
6

MATL , 7 , 6 байтов

Yf1Z|p

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

1 байт сохранен благодаря гениальному наблюдению Денниса

Лучший способ объяснить это - показать стек в разных точках.

Yf  % Prime factors

[2 2 2 3]

1Z| % Bitwise OR with 1

[3 3 3 3]

p   % Product

81

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

Yfto~+p
DJMcMayhem
источник
Ницца! У меня было Yf3H$X>pпо 8 байт
Луис Мендо
6

05AB1E , 6 5 байт

Сохранил байт благодаря Аднану .

ÒDÈ+P

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

объяснение

Ò       # push list of prime factors of input
 D      # duplicate
  È     # check each factor for evenness (1 if true, else 0)
   +    # add list of factors and list of comparison results
    P   # product
Emigna
источник
2
ÒDÈ+Pдолжен сохранить байт
Аднан
@Adnan: Спасибо!
Эминья,
6

Алиса , 9 байт

2/S 3
o@i

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

Алиса имеет встроенную функцию для замены делителя числа другим. Я не думал, что смогу использовать это так скоро ...

Используя кодовые точки символов для ввода / вывода, получается 6 байтов: I23SO@ .

объяснение

2   Push 2 (irrelevant).
/   Reflect to SE. Switch to Ordinal.
i   Read all input as a string.
    The IP bounces up and down, hits the bottom right corner and turns around,
    bounces down again.
i   Try to read more input, but we're at EOF so this pushes an empty string.
/   Reflect to W. Switch to Cardinal.
2   Push 2.
    The IP wraps around to the last column.
3   Push 3.
S   Implicitly discard the empty string and convert the input string to the integer
    value it contains. Then replace the divisor 2 with the divisor 3 in the input.
    This works by multiplying the value by 3/2 as long as it's divisible by 2.
/   Reflect to NW. Switch to Ordinal.
    Immediately bounce off the top boundary. Move SW.   
o   Implicitly convert the result to a string and print it.
    Bounce off the bottom left corner. Move NE.
/   Reflect to S. Switch to Cardinal.
@   Terminate the program.
Мартин Эндер
источник
1
Ваша одержимость официально подтверждена.
Утренняя монахиня
4

Желе , 8 5 байт

Æf3»P

Æf3»P  Main Link, argument is z
Æf     Prime factors
  3»   Takes maximum of 3 and the value for each value in the array
    P  Takes the product of the whole thing

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

-3 байта благодаря подсказке от @Dennis!

HyperNeutrino
источник
2
Подсказка: 2 - это единственное четное и наименьшее простое число.
Деннис
@ Денис, я вижу. Да, получил это сейчас. Благодарность! :)
HyperNeutrino
Поздравляю с изучением желе.
Утренняя монахиня
@ LeakyNun Спасибо! И спасибо, что научил меня. :)
HyperNeutrino
Поздравляю с этим ответом!
Эрик Outgolfer
4

Pyth - 14 10 9 байт

*^1.5/PQ2

Считает число 2s в простой факторизации (/ PQ2). Умножает ввод на 1,5 ^ (число из 2 с)

Попытайся

Мария
источник
Интересный подход - очень жаль, что он не такой короткий, как существующее решение Pyth.
Esolanging Fruit
@ Challenger5 Я не вижу здесь никакого другого решения Pyth.
Мария
1
Ох, тогда хорошо. Это более интересный подход, чем типичный для этой задачи.
Esolanging Fruit
4

Гексагония , 112 91 байт

Размер сетки 6 (91 байт)

      ? { 2 . . <
     / = { * = \ "
    . & . . . { _ '
   . . { . . } ' * 2
  _ } { / . } & . ! "
 . > % . . < | . . @ |
  \ . . \ . | ~ . . 3
   . . " . } . " . "
    . & . \ = & / 1
     \ = { : = } .
      [ = { { { <

Компактная версия

?{2..</={*=\".&...{_'..{..}'*2_}{/.}&.!".>%..<|..@|\..\.|~..3..".}.".".&.\=&/1\={:=}.[={{{<

Размер сетки 7 (112 байт)

       ? { 2 " ' 2 <
      / { * \ / : \ "
     . = . = . = | . 3
    / & / { . . } { . "
   . > $ } { { } / = . 1
  _ . . } . . _ . . & . {
 . > % < . . ~ & . . " . |
  | . . } - " . ' . @ | {
   . . . = & . . * ! . {
    . . . _ . . . _ . =
     > 1 . . . . . < [
      . . . . . . . .
       . . . . . . .

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

Компактная версия:

?{2"'2</{*\/:\".=.=.=|.3/&/{..}{.".>$}{{}/=.1_..}.._..&.{.>%<..~&..".||..}-".'.@|{...=&..*!.{..._..._.=>1.....<[

Версия Ungolfed для лучшей читаемости:

Ungolfed

Примерный план памяти

введите описание изображения здесь

Серый путь (инициализация памяти)

?     Read input as integer (Input)
{     Move to memory edge "Divisor left"
2     Set current memory edge to 2 
" '   Move to memory edge "Divisor right" 
2     Set current memory edge to 2
"     Move to memory edge "Multiplier" 
3     Set current memory edge to 3
"     Move to memory edge "Temp 2" 
1     Set current memory edge to 1 
{ { { Move to memory edge "Modulo"
=     Turn memory pointer around 
[     Continue with next instruction pointer

Цикл входа

%     Set "Modulo" to Input mod Divisor
<     Branch depending on result

Зеленый путь (значение все еще делится на 2)

} } {     Move to memory edge "Result"
=         Turn memory pointer around 
*         Set "Result" to "Temp 2" times "Multiplier" (3) 
{ = &     Copy "Result" into "Temp2" 
{ { } } = Move to "Temp"
:         Set "Temp" to Input / Divisor (2)
{ = &     Copy "Temp" back to "Input"
"         Move back to "Modulo"

Красный путь (значение больше не делится на 2)

} = & " ~ & ' Drag what's left of "Input" along to "Multiplier"
*             Multiply "Multiplier" with "Temp 2"
! @           Output result, exit program
Манфред Радлвиммер
источник
1
Добро пожаловать в PPCG! :)
Мартин Эндер
@MartinEnder Спасибо, классный язык, кстати. :)
Манфред Радлвиммер
1
Спасибо за использование! :) Разве вы не можете упростить макет памяти (и, следовательно, количество движения, которое вам нужно сделать), если вы вычисляете %2и то и :2другое по краю "по модулю"? (Таким образом, вы можете просто избавиться от двух верхних ребер.) И затем, вы могли бы прикрепить ветвь «множителя» к ребру «по модулю» вместо ребра «делителя», чтобы вам было нужно меньше движения после каждой ветки? (Вы могли бы даже повернуть этот раздел, чтобы «result» или «temp 2» касались «modulo», что означало бы, что вам нужно скопировать окончательный результат только один раз, прежде чем вы сможете вычислить продукт.)
Martin Ender
@MartinEnder Ммм, наверное. Я все еще изучаю часть языка «Агония», поэтому сейчас, вероятно, я буду придерживаться уменьшения сетки, не затрагивая логику ^^
Манфред Радлвиммер
3

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

~×₂×₃↰|

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

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

~×₂×₃↰|      original program
?~×₂×₃↰.|?.  with implicit input (?) and output (.) added

?~×₂         input "un-multiplied" by 2
    ×₃       multiplied by 3
      ↰      recursion
       .     is the output
        |    or (in case the above fails, meaning that the input
                 cannot be "un-multiplied" by 2)
         ?.  the input is the output
Дрянная Монахиня
источник
Относящиеся .
2

J 11 байт

[:*/q:+2=q:

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

[: cap (заполнитель для вызова следующего глагола monadically)

*/ продукт

q: основные факторы

+ плюс (т.е. с одним добавленным где)

2 два

= равно (каждому из)

q: основные факторы

Адам
источник
Я думал, что вы находите [:отвратительным.
Утренняя монахиня
@LeakyNun, но я не был таким умным, как Конор О'Брайен .
Адам
2

J , 15 12 10 байт

(+2&=)&.q:

Попробуйте онлайн! Работает аналогично ниже, только имеет другую логику в отношении замены 2с 3.

15 байт

(2&={,&3)"+&.q:

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

объяснение

(2&={,&3)"+&.q:
           &.    "under"; applies the verb on the right, then the left,
                 then the inverse of the right
             q:  prime factors
(       )"+      apply inside on each factor
     ,&3         pair with three: [factor, 3]
 2&=             equality with two: factor == 2
    {            list selection: [factor, 3][factor == 2]
                 gives us 3 for 2 and factor for anything else
           &.q:  under prime factor
Конор О'Брайен
источник
Да, вы переключили алгоритм, пока я писал свой. Теперь мы используем то же самое.
Адам
@ Адам О, ха-ха. Хороший ответ! Я не мог удержаться от возможности использовать rollздесь. :)
Конор О'Брайен
На самом деле я мог бы сохранить еще несколько байтов ... Редактировать сохранил некоторые: D
Конор О'Брайен
Забавно, ты называешь это Ролл, я называю это Под. Надеюсь получить его в APL в ближайшее время.
Адам
@ Adám Хаха, на самом деле это называется. Я запутался в условиях
Конор О'Брайен,
2

Pyth , 9 байт

Целочисленный вывод \ o /

*F+1.|R1P

Тестирование .

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

*F+1.|R1P
        P   prime factorization
    .|R1    bitwise OR each element with 1
*F+1        product
Дрянная Монахиня
источник
2

Japt , 19 16 10 9 7 байт

k ®w3Ã×

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

объяснение

 k ®   w3Ã ×
Uk mZ{Zw3} r*1
U              # (input)
 k m           # for every prime factor
    Z{Zw3}     # replace it by the maximum of itself and 3
           r*1 # output the product
Люк
источник
Ха, JS связан с Japt.
Верный
Подсказки: ×это ярлык для r@X*Y}1(или просто r*1), который может пригодиться. Там также XwYесть что Math.max(X,Y).
ETHproductions
Спасибо, хотя рекурсивное решение действительно самое короткое.
Лука
Хороший! Я думаю, что вы можете сделать, k m_w3Ã×чтобы сохранить байт. Также m_можно сократить до ®.
Оливер
2

PHP, 36 байт

for($a=$argn;$a%2<1;)$a*=3/2;echo$a;

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

Йорг Хюльсерманн
источник
1
for($a=$argn;!1&$a;)$a*=3/2;echo$a;переименование $argnсохраняет один байт.
Кристоф
2

CJam, 10 9 байтов

rimf1f|:*

Действительно просто.

Объяснение:

ri  e# Read integer:         | 28
mf  e# Prime factors:        | [2 2 7]
1   e# Push 1:               | [2 2 7] 1
f|  e# Bitwise OR with each: | [3 3 7]
:*  e# Product:              | 63
Esolanging Fruit
источник
2

Гексагония , 28 27 26 байт

?'2{{(\}}>='!:@=$\%<..>)"*

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

Выложил:

    ? ' 2 {
   { ( \ } }
  > = ' ! : @
 = $ \ % < . .
  > ) " * . .
   . . . . .
    . . . .

Это в основном работает:

num = input()
while num%2 == 0:
    num = (num/2)*3
print num

На данный момент это упражнение о том, как мучительно я могу получить путь цикла, чтобы минимизировать байты.

Джо Кинг
источник
Ну, черт возьми, я не думал об этом
Манфред Радлвиммер
1
@ManfredRadlwimmer Не волнуйтесь, кодирование чего-либо в Hexagony само по себе является достижением
Джо Кинг,
1

Japt , 7 байт

k mw3 ×

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

объяснение

k mw3 ×

k        // Factorize the input.
  mw3    // Map each item X by taking max(X, 3).
      ×  // Take the product of the resulting array.
         // Implicit: output result of last expression
ETHproductions
источник
1

R, 42 байта

Единственное правильное количество байтов в ответе.

x=gmp::factorize(scan());x[x==2]=3;prod(x)

Довольно просто, использует gmpпакет для разложения x, заменяет 2 на 3 и возвращает продукт.

JAD
источник
1

Befunge-93 , 20 байтов

&>:2%!#v_.@
 ^*3/2 <

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

& - take in input and add it to the stack
> - move right
: - duplicate the top of the stack
2 - add two to the stack
% - pop 2 and the input off the stack and put input%2 on the stack
! - logical not the top of the stack
# - jump over the next command
_ - horizontal if, if the top of the stack is 0 (i.e. input%2 was non zero) go 
    right, else go left

If Zero:
. - output the top of the stack
@ - end code

If Not Zero:
v - move down
< - move left
2 - add 2 the top of the stack
/ - pop top two, add var/2 to the stack
3 - add 3 to stack
* - pop top two, add var*3 to the stack
^ - move up
> - move right (and start to loop)
bwillsh
источник
17 байт
Джо Кинг,
1

Perl 6 , 14 байт

{1.5**.lsb*$_}

lsb возвращает позицию младшего бита, отсчитанную справа. То есть, сколько концевых нулей в двоичном представлении, что совпадает с числом факторов, равных 2. Так что поднимите 3/2 до этой степени, и мы закончили.

say {$_*1.5**.lsb}(24);
> 81
Фил Х
источник