Ganti berdua dengan bertiga

36

Diberikan bilangan bulat positif dan tulis beberapa kode untuk mengambil faktorisasi utamanya dan mengganti semua faktornya 2dengan 3.

Sebagai contoh

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

Ini adalah kode-golf sehingga tujuannya adalah untuk meminimalkan jumlah byte jawaban Anda.

Uji kasus

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 Wisaya Gandum
sumber

Jawaban:

63

Fraktran , 3 byte

3/2

Fractran secara harfiah hanya memiliki satu builtin, tetapi kebetulan melakukan persis apa yang diminta tugas ini. (Ini juga Turing-lengkap, dengan sendirinya.)

Bahasa tidak benar-benar memiliki sintaks atau penerjemah terstandarisasi. Penerjemah ini (dalam komentar ke posting blog - ini bahasa yang sangat sederhana) akan menerima sintaks yang ditunjukkan di sini. (Ada interpreter Fractran lain dengan sintaksis lain, misalnya beberapa akan menulis program ini sebagai3 2 , atau bahkan menggunakan 3dan 2sebagai argumen baris perintah, yang akan menghasilkan skor 0 + 3 byte. Saya ragu mungkin untuk melakukan lebih baik daripada 3 dalam penerjemah yang sudah ada sebelumnya.)

Penjelasan

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

sumber
10
Bicara tentang alat yang tepat untuk pekerjaan itu ..
Kevin Cruijssen
23
"Jangan memungut solusi sepele yang hanya menggunakan builtin sederhana." Nah, dalam hal ini: Mengetahui bahwa ada bahasa "Fractran" yang memiliki satu builtin yang menyelesaikan tugas khusus ini dengan sendirinya mengesankan.
Stewie Griffin
3
Golf kode SO terkait (pra-PPCG): Tulis juru bahasa Fractran .
hobbs
1
@AnderBiguri: Kemungkinan mencari bahasa lengkap Turing yang sangat sederhana / mudah diimplementasikan. Fractran benar-benar elegan saat Turing pergi; kebanyakan memiliki lebih banyak tepi kasar, kasing khusus, atau detail yang dapat diubah tanpa membuat perbedaan besar.
3
@AnderBiguri Sepertinya itu keluar dari studinya tentang dugaan Collatz; ia membuktikan bahwa generalisasi Collatz setara dengan Fractran dan bahwa Fractran adalah Turing-lengkap, oleh karena itu Collatz yang digeneralisasi tidak dapat diputuskan.
hobbs
21

Python 2 , 28 byte

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

Cobalah online!

Membagi angka secara rekursif dengan 2 dan mengalikan hasilnya dengan 3, asalkan angkanya genap. Angka ganjil kembali sendiri.

Alt 32 byte:

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

Cobalah online . Memiliki beberapa kesalahan float. Konstanta adalahlog_2(3)-1 .

Menggunakan (n&-n)untuk menemukan kekuatan-of-2 faktor terbesar n, yang bertobat 3**kuntuk 2**kdengan menaikkan ke kekuatan log_2(3)-1.

Tidak
sumber
Bagus ini solusi saya sebenarnya!
Wheat Wizard
@WheatWizard Me juga, aha!
Graviton
18

05AB1E , 4 byte

Ò1~P

Cobalah online!

Bagaimana itu bekerja

Ò     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.
Dennis
sumber
Ini mengalahkan Jelly dengan 1 byte hanya karena faktorisasi utama hanya satu byte di sini :(
HyperNeutrino
5
@HyperNeutrino: Saya perhatikan itu juga: "mengapa Dennis menggunakan 05AB1E? Oh, algoritma yang sama, nama yang lebih pendek." Jadi saya harus pergi dan menemukan bahasa di mana saya bisa melakukannya dalam byte lebih sedikit, melalui penggunaan set yang lebih tepat dari builtin.
14

Haskell, 24 23 byte

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

Bagi dengan dua dan kalikan dengan 3 hingga trik aneh di Haskell.

Cobalah online!

Alternatif dengan lambda alih-alih fungsi pointfree dan dengan jumlah byte yang sama:

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

Sunting: @ ais523 menyimpan satu byte dalam versi asli dan @ Ørjan Johansen satu di versi alternatif, sehingga kedua versi memiliki panjang yang sama. Terima kasih!

nimi
sumber
3
Versi lambda dapat disingkat menjadi odd`until`\x->div(x*3)2.
Ørjan Johansen
2
Versi asli juga dapat dipersingkat satu byte melalui penggunaan $untuk mengganti sepasang tanda kurung: Coba online!
@ ØrjanJohansen: ah, bagus! Terima kasih.
nimi
@ ais523: Bagaimana saya bisa melewatkan yang itu, Terima kasih!
nimi
2
Saya pikir Anda lupa menghapus sepasang dari ()versi lambda
CAD97
8

JavaScript (ES6), 19 byte

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

Sementara input dapat dibagi dua, dikalikan dengan 1,5, yang setara dengan membaginya dengan 2 dan mengalikannya dengan 3.

Produksi ETH
sumber
2
x*3/2memiliki bytecount yang sama
Leaky Nun
1
f=biasanya tidak diperlukan untuk js.
Christoph
3
@Christoph Terima kasih, tetapi untuk menyebut dirinya f(x*1.5)perlu memiliki nama f, maka mengapa f=disertakan.
ETHproduksi
@ ETHproductions Uhm ... tentu saja! Saya melewatkan itu. Apakah ada meta tentang bagaimana sebenarnya kode panggilan itu?
Christoph
2
@Christoph Ini adalah postingan meta yang relevan.
ETHproduksi
8

Brain-Flak , 76 byte

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

Cobalah online!

Penjelasan

Program ini bekerja dengan membagi angka dengan dua dan tiga kali lipat hingga mendapat satu dari sisa divisi. Kemudian berhenti berputar dan menggandakan dan menambahkan satu ke nomor terakhir.

Penjelasan lebih rinci akhirnya ...

0 '
sumber
> Segera hadir ...
Wheat Wizard
7

Mathematica, 22 19 byte

Terima kasih kepada lanlock4 untuk menghemat 3 byte!

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

Fungsi murni yang melakukan penggantian berulang kali, satu faktor 2 sekaligus. Bekerja pada semua bilangan bulat positif kurang dari 2.565.537 .

Greg Martin
sumber
Apakah akan x_?EvenQberhasil x_/;EvenQ@x?
Bukan pohon
1
Anda sepenuhnya benar, terima kasih!
Greg Martin
6

MATL , 7 , 6 byte

Yf1Z|p

Cobalah online!

1 byte disimpan berkat pengamatan jenius Dennis

Cara terbaik untuk menjelaskan ini adalah dengan menunjukkan tumpukan di berbagai titik.

Yf  % Prime factors

[2 2 2 3]

1Z| % Bitwise OR with 1

[3 3 3 3]

p   % Product

81

Solusi alternatif:

Yfto~+p
DJMcMayhem
sumber
Bagus! Saya punya Yf3H$X>puntuk 8 byte
Luis Mendo
6

05AB1E , 6 5 byte

Menyimpan satu byte, terima kasih kepada Adnan .

ÒDÈ+P

Cobalah online!

Penjelasan

Ò       # 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
sumber
2
ÒDÈ+Pharus menyimpan byte
Adnan
@ Adnan: Terima kasih!
Emigna
6

Alice , 9 byte

2/S 3
o@i

Cobalah online!

Alice memiliki built-in untuk mengganti pembagi nomor dengan yang lain. Saya tidak berpikir saya akan benar-benar memanfaatkannya begitu cepat ...

Menggunakan poin kode karakter untuk I / O, ini menjadi 6 bytes: I23SO@.

Penjelasan

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.
Martin Ender
sumber
1
Obsesi Anda dikonfirmasi secara resmi.
Leaky Nun
4

Jelly , 8 5 byte

Æ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

Cobalah online!

-3 byte berkat petunjuk dari @Dennis!

HyperNeutrino
sumber
2
Petunjuk: 2 adalah satu-satunya bilangan prima bahkan dan terkecil.
Dennis
@ Dennisu begitu. Ya, dapatkan sekarang. Terima kasih! :)
HyperNeutrino
Selamat telah mempelajari Jelly.
Leaky Nun
@ LeakyNun Terima kasih! Dan terima kasih telah mengajarkannya kepada saya. :)
HyperNeutrino
Selamat atas jawaban ini!
Erik the Outgolfer
4

Pyth - 14 10 9 byte

*^1.5/PQ2

Menghitung jumlah 2 dalam faktorisasi utama (/ PQ2). Mengalikan input dengan 1,5 ^ (# of 2s)

Cobalah

Maria
sumber
Pendekatan yang menarik - terlalu buruk itu tidak sesingkat solusi Pyth yang ada.
Buah Esolanging
@ Challenger5 Saya tidak melihat solusi Pyth lainnya di sini.
Maria
1
Oh oke kalau begitu. Ini adalah pendekatan yang lebih menarik daripada yang biasa untuk tantangan ini.
Buah Esolanging
4

Segi enam , 112 91 byte

Ukuran kisi 6 (91 byte)

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

Versi ringkas

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

Ukuran kisi 7 (112 byte)

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

Cobalah online!

Versi Ringkas:

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

Versi Ungolfed untuk keterbacaan yang lebih baik:

Tidak disatukan

Perkiraan Tata Letak Memori

masukkan deskripsi gambar di sini

Gray Path (inisialisasi memori)

?     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

Entri loop

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

Green Path (nilainya masih dapat dibagi 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"

Jalur Merah (nilai tidak lagi dapat dibagi 2)

} = & " ~ & ' Drag what's left of "Input" along to "Multiplier"
*             Multiply "Multiplier" with "Temp 2"
! @           Output result, exit program
Manfred Radlwimmer
sumber
1
Selamat datang di PPCG! :)
Martin Ender
@ MartinEnder Terima kasih, bahasa yang bagus btw. :)
Manfred Radlwimmer
1
Terima kasih telah menggunakannya! :) Tidak bisakah Anda menyederhanakan tata letak memori (dan dengan demikian jumlah gerakan yang perlu Anda lakukan) jika Anda menghitung %2dan :2keduanya ke tepi "modulo"? (Jadi Anda bisa menyingkirkan dua tepi teratas.) Dan kemudian, dapatkah Anda memasang cabang "pengali" ke tepi "modulo" alih-alih tepi "pembagi" sehingga Anda memerlukan lebih sedikit gerakan setelah setiap cabang? (Anda bahkan dapat memutar bagian itu, sehingga "hasil" atau "temp 2" menyentuh "modulo" yang berarti Anda hanya perlu menyalin hasil akhir satu kali sebelum dapat menghitung produk.)
Martin Ender
@MartinEnder Uhhhm mungkin. Saya masih menyiasati bagian "Penderitaan" dari bahasa itu jadi untuk sekarang saya mungkin akan tetap membuat grid lebih kecil tanpa menyentuh logika ^^
Manfred Radlwimmer
3

Brachylog , 7 byte

~×₂×₃↰|

Cobalah online!

Bagaimana itu bekerja

~×₂×₃↰|      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
Biarawati Bocor
sumber
Terkait .
2

J , 11 byte

[:*/q:+2=q:

Cobalah online!

[: cap (placeholder untuk memanggil kata kerja berikutnya secara monadik)

*/ produk dari

q: faktor utama

+ plus (yaitu dengan satu menambahkan di mana)

2 dua

= sama dengan (masing-masing)

q: faktor utama

Adm
sumber
Saya pikir Anda menemukan [:menjijikkan.
Leaky Nun
@ LeakyNun ya, tapi aku tidak sepintar Conor O'Brien .
Adám
2

J , 15 12 10 byte

(+2&=)&.q:

Cobalah online!Pekerjaan yang mirip dengan di bawah ini, hanya memiliki logika berbeda tentang penggantian2 dengan 3.

15 byte

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

Cobalah online!

Penjelasan

(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
Conor O'Brien
sumber
Huh, Anda mengganti algoritme saat saya menulis milik saya. Sekarang kita menggunakan hal yang sama.
Adám
@ Adám Oh, haha. Jawaban bagus! Saya tidak bisa menolak kesempatan untuk menggunakan di rollsini. :)
Conor O'Brien
Sebenarnya saya mungkin dapat menyimpan lebih banyak byte ... sunting menyelamatkan beberapa: D
Conor O'Brien
Lucu Anda menyebutnya Roll, saya menyebutnya Di Bawah. Berharap untuk segera masuk ke APL.
Adm
@ Adám Haha itu sebenarnya disebut di bawah. Saya mendapat istilah bingung
Conor O'Brien
2

Pyth , 9 byte

Output integer \ o /

*F+1.|R1P

Suite uji .

Bagaimana itu bekerja

*F+1.|R1P
        P   prime factorization
    .|R1    bitwise OR each element with 1
*F+1        product
Biarawati Bocor
sumber
2

Japt , 19 16 10 9 7 bytes

k ®w3Ã×

Cobalah online!

Penjelasan

 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
Luke
sumber
Hah, JS diikat dengan Japt. Pertanda pasti ada solusi yang jauh lebih pendek ;-)
ETHproduk
Petunjuk: ×adalah jalan pintas untuk r@X*Y}1(atau hanya r*1), yang mungkin berguna. Ada juga XwYyang mana Math.max(X,Y).
ETHproduk
Terima kasih, meskipun solusi rekursif benar-benar adalah yang terpendek.
Luke
Yang bagus! Saya pikir Anda dapat melakukannya k m_w3Ã×untuk menghemat satu byte. Juga, m_bisa disingkat menjadi ®.
Oliver
2

PHP, 36 Bytes

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

Cobalah online!

Jörg Hülsermann
sumber
1
for($a=$argn;!1&$a;)$a*=3/2;echo$a;penggantian nama $argnmenghemat satu byte.
Christoph
2

CJam, 10 9 byte

rimf1f|:*

Sangat sederhana.

Penjelasan:

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
Buah Esolanging
sumber
2

Hexagony , 28 27 26 byte

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

Cobalah online!

Ditata:

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

Ini pada dasarnya berjalan:

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

Pada titik ini adalah latihan tentang betapa menyiksanya saya bisa mendapatkan jalur loop untuk meminimalkan byte.

Jo King
sumber
Ya ampun, saya tidak memikirkan itu
Manfred Radlwimmer
1
@ManfredRadlwimmer Jangan khawatir, mengkode apa pun di Hexagony adalah sebuah pencapaian tersendiri
Jo King
1

Japt , 7 byte

k mw3 ×

Cobalah online!

Penjelasan

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
Produksi ETH
sumber
1

R, 42 byte

Jumlah byte yang tepat dalam sebuah jawaban.

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

Cukup mudah, menggunakan gmppaket untuk membuat faktor x, menggantikan 2s dengan 3s, dan mengembalikan produk.

JAD
sumber
1

Befunge-93 , 20 byte

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

Cobalah online!

& - 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
sumber
17 byte
Jo King
1

Perl 6 , 14 byte

{1.5**.lsb*$_}

lsb mengembalikan posisi bit paling tidak signifikan, dihitung dari kanan. Yaitu, berapa banyak angka nol yang tertinggal dalam representasi biner, yang sama dengan jumlah faktor 2. Jadi naikkan 3/2 menjadi kekuatan itu dan kita selesai.

say {$_*1.5**.lsb}(24);
> 81
Phil H
sumber
0

Sebenarnya , 9 byte

w⌠i1|ⁿ⌡Mπ

Cobalah online!

Penjelasan:

w⌠i1|ⁿ⌡Mπ
w          factor into [prime, exponent] pairs
 ⌠i1|ⁿ⌡M   for each pair:
  i          flatten
   1|        prime | 1 (bitwise OR)
     ⁿ       raise to exponent
        π  product
Mego
sumber