Ersetzen Sie zwei durch drei

36

Wenn eine positive ganze Zahl n gegeben ist, schreibe einen Code, um seine Primfaktorisierung zu nehmen und alle seine Faktoren von 2durch zu ersetzen 3.

Beispielsweise

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

Dies ist Codegolf, daher besteht das Ziel darin, die Byteanzahl Ihrer Antwort zu minimieren.

Testfälle

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 Weizen-Assistent
quelle

Antworten:

63

Fractran , 3 Bytes

3/2

Fractran hat buchstäblich nur ein eingebautes, aber es tut genau das, wonach diese Aufgabe verlangt. (Es ist auch Turing-komplett für sich.)

Die Sprache hat nicht wirklich eine standardisierte Syntax oder einen standardisierten Interpreter. Dieser Interpreter (in einem Kommentar zu einem Blog-Beitrag - es ist eine sehr einfache Sprache) akzeptiert die hier gezeigte Syntax. (Es gibt andere Fractran-Interpreter mit anderen Syntaxen, z. B. würden einige dieses Programm als 3 2oder sogar unter Verwendung von 3und 2als Befehlszeilenargumente schreiben , was zu einer Bewertung von 0 + 3 Bytes führen würde bereits vorhandener Dolmetscher.)

Erläuterung

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

quelle
10
Sprechen Sie über das richtige Werkzeug für den Job ..
Kevin Cruijssen
23
"Werben Sie nicht für triviale Lösungen, die nur eine einfache integrierte Funktion verwenden." Nun, in diesem Fall: Zu wissen, dass es eine Sprache "Fractran" gibt, die eine einzige eingebaute Sprache hat, die diese spezifische Aufgabe löst, ist an sich schon beeindruckend.
Stewie Griffin
3
Verwandte SO-Code Golf (Pre-PPCG): Schreiben Sie einen Fractran-Interpreter .
Hobbs
1
@AnderBiguri: Sucht wahrscheinlich nach einer Turing-vollständigen Sprache, die sehr einfach / leicht zu implementieren ist. Fractran ist wirklich elegant wie Turing Tarpits gehen; Die meisten haben viel mehr Ecken und Kanten, Sonderfälle oder Details, die geändert werden können, ohne einen großen Unterschied zu machen.
3
@AnderBiguri Es sieht so aus, als stamme es aus seinen Studien über die Collatz-Vermutung. er hat bewiesen, dass eine Verallgemeinerung von Collatz gleichbedeutend mit Fractran ist und dass Fractran vollständig ist, weshalb verallgemeinerte Collatz unentscheidbar sind.
Hobbs
21

Python 2 , 28 Bytes

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

Probieren Sie es online!

Teilen Sie die Zahl rekursiv durch 2 und multiplizieren Sie das Ergebnis mit 3, solange die Zahl gerade ist. Ungerade Zahlen geben sich selbst zurück.

32 Byte alt:

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

Probieren Sie es online aus . Hat einen Float-Fehler. Die Konstante ist log_2(3)-1.

Verwendet (n&-n), um den größten Faktor der Zweierpotenz zu finden n, zu dem konvertiert wird 3**k, 2**kindem er auf die Potenz von erhöht wird log_2(3)-1.

xnor
quelle
Schön, das ist genau meine Lösung!
Weizen-Assistent
@ WheatWizard Ich auch, aha!
Graviton
18

05AB1E , 4 Bytes

Ò1~P

Probieren Sie es online!

Wie es funktioniert

Ò     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
quelle
Dies schlägt Jelly um 1 Byte, nur weil die Primfaktorisierung hier nur ein Byte ist :(
HyperNeutrino
5
@HyperNeutrino: Ich habe das auch bemerkt: "Warum benutzt Dennis 05AB1E? Oh, identischer Algorithmus, kürzere eingebaute Namen". Also musste ich nach einer Sprache suchen, in der ich es mit noch weniger Bytes und einer noch angemesseneren Anzahl von eingebauten Sprachen schaffen konnte.
14

Haskell, 24 23 Bytes

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

Die Division durch zwei und multiplizieren mit 3 bis ungerade Trick in Haskell.

Probieren Sie es online!

Alternative mit Lambda anstelle einer Pointfree-Funktion und gleicher Byteanzahl:

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

Bearbeiten: @ ais523 hat ein Byte in der Originalversion und @ Ørjan Johansen ein Byte in der Alternativversion gespeichert, sodass beide Versionen immer noch die gleiche Länge haben. Vielen Dank!

nimi
quelle
3
Die Lambda-Version kann auf gekürzt werden odd`until`\x->div(x*3)2.
Ørjan Johansen
2
Die Originalversion kann auch um ein Byte gekürzt werden, indem $ein Klammerpaar ersetzt wird: Probieren Sie es online aus!
@ ØrjanJohansen: ah, schön! Vielen Dank.
nimi
@ ais523: Wie hätte ich das verpassen können, Danke!
nimi
2
Ich glaube, Sie haben vergessen, ein Paar ()aus der Lambda-Version zu entfernen
CAD97
8

JavaScript (ES6), 19 Byte

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

Während die Eingabe durch zwei teilbar ist, multipliziert man sie mit 1,5, was einer Division durch 2 und einer Multiplikation mit 3 entspricht.

ETHproductions
quelle
2
x*3/2hat das gleiche bytecount
Leaky Nun
1
f=wird normalerweise nicht für js benötigt.
Christoph
3
@Christoph Danke, aber um sich selbst zu nennen f(x*1.5), muss es den Namen haben f, weshalb das f=enthalten ist.
ETHproductions
@ETHproductions Ähm ... natürlich! Das habe ich vermisst. Gibt es Metas, wie der aufrufende Code genau aussieht?
Christoph
2
@Christoph Hier ist der relevante Meta-Post.
ETHproductions
8

Brain-Flak , 76 Bytes

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

Probieren Sie es online!

Erläuterung

Bei diesem Programm wird die Zahl durch zwei geteilt und verdreifacht, bis der Rest der Teilung eins ergibt. Dann stoppt es die Schleife und verdoppelt sich und addiert eins zur endgültigen Zahl.

Ausführlichere Erklärung schließlich ...

0 '
quelle
> Demnächst ...
Wheat Wizard
7

Mathematica, 22 19 Bytes

Danke an lanlock4 für das Speichern von 3 Bytes!

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

Reine Funktion, die den Austausch wiederholt, jeweils um den Faktor 2. Funktioniert mit allen positiven ganzen Zahlen unter 2 65537 .

Greg Martin
quelle
Würde x_?EvenQarbeiten statt x_/;EvenQ@x?
Kein Baum
1
Du hast vollkommen recht, danke!
Greg Martin
6

MATL , 7 , 6 Bytes

Yf1Z|p

Probieren Sie es online!

1 Byte gespart dank Dennis 'genialer Beobachtung

Der beste Weg, dies zu erklären, besteht darin, den Stapel an verschiedenen Stellen zu zeigen.

Yf  % Prime factors

[2 2 2 3]

1Z| % Bitwise OR with 1

[3 3 3 3]

p   % Product

81

Alternative Lösung:

Yfto~+p
DJMcMayhem
quelle
Nett! Ich hatte Yf3H$X>pfür 8 Bytes
Luis Mendo
6

05AB1E , 6 5 Bytes

Dank Adnan ein Byte gespeichert .

ÒDÈ+P

Probieren Sie es online!

Erläuterung

Ò       # 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
quelle
2
ÒDÈ+Psollte ein Byte speichern
Adnan
@Adnan: Danke!
Emigna
6

Alice , 9 Bytes

2/S 3
o@i

Probieren Sie es online!

Alice hat eine eingebaute, um einen Teiler einer Zahl durch eine andere zu ersetzen. Ich hätte nicht gedacht, dass ich so bald davon Gebrauch machen könnte ...

Mit Hilfe der Codepunkte der Zeichen für I / O, wird auf 6 Bytes: I23SO@.

Erläuterung

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
quelle
1
Ihre Besessenheit ist offiziell bestätigt.
Undichte Nonne
4

Gelee , 8 5 Bytes

Æ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

Probieren Sie es online!

-3 Bytes dank eines Hinweises von @Dennis!

HyperNeutrino
quelle
2
Hinweis: 2 ist sowohl die einzige gerade als auch die kleinste Primzahl.
Dennis
@ Tennis Ich verstehe. Ja, jetzt verstanden. Vielen Dank! :)
HyperNeutrino
Herzlichen Glückwunsch zum Lernen von Jelly.
Undichte Nonne
@LeakyNun Danke! Und danke, dass du es mir beigebracht hast. :)
HyperNeutrino
Herzlichen Glückwunsch zu dieser Antwort!
Erik der Outgolfer
4

Pyth - 14 10 9 Bytes

*^1.5/PQ2

Zählt die Anzahl der 2s in der Primfaktorisierung (/ PQ2). Multipliziert die Eingabe mit 1,5 ^ (# von 2s)

Versuch es

Maria
quelle
Interessanter Ansatz - schade, dass er nicht so kurz ist wie die vorhandene Pyth-Lösung.
Esolanging Fruit
@ Challenger5 Ich sehe hier keine andere Pyth-Lösung.
Maria
1
Oh, na dann. Es ist ein interessanterer Ansatz als der typische für diese Herausforderung.
Esolanging Fruit
4

Hexagony , 112 91 Bytes

Rastergröße 6 (91 Bytes)

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

Kompakte Version

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

Rastergröße 7 (112 Bytes)

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

Probieren Sie es online!

Kompakte Version:

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

Ungolfed Version für bessere Lesbarkeit:

Ungolfed

Ungefähre Speicheranordnung

Bildbeschreibung hier eingeben

Gray Path (Speicherinitialisierung)

?     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

Loop-Eintrag

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

Grüner Pfad (Wert ist noch durch 2 teilbar)

} } {     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"

Roter Pfad (Wert ist nicht mehr teilbar durch 2)

} = & " ~ & ' Drag what's left of "Input" along to "Multiplier"
*             Multiply "Multiplier" with "Temp 2"
! @           Output result, exit program
Manfred Radlwimmer
quelle
1
Willkommen bei PPCG! :)
Martin Ender
@ MartinEnder Danke, tolle Sprache übrigens. :)
Manfred Radlwimmer
1
Danke, dass du es benutzt! :) Kannst du nicht das Speicherlayout (und damit den Bewegungsumfang, den du machen musst) vereinfachen, wenn du %2und :2beides in die "Modulo" -Kante hineinrechnest? (Sie können also einfach die beiden oberen Kanten loswerden.) Und könnten Sie dann den "Multiplikator" -Zweig an der "Modulo" -Kante anstelle der "Divisor" -Kante anbringen, sodass Sie nach jeder Verzweigung weniger Bewegung benötigen? (Möglicherweise können Sie diesen Bereich sogar drehen, sodass "result" oder "temp 2" "modulo" berührt. Dies bedeutet, dass Sie das Endergebnis nur einmal kopieren müssen, bevor Sie das Produkt berechnen können.)
Martin Ender
@ MartinEnder Uhhhm wahrscheinlich. Ich komme immer noch mit dem "Agony"
-Teil
3

Brachylog , 7 Bytes

~×₂×₃↰|

Probieren Sie es online!

Wie es funktioniert

~×₂×₃↰|      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
Undichte Nonne
quelle
Verwandte .
2

J , 11 Bytes

[:*/q:+2=q:

Probieren Sie es online!

[: cap (Platzhalter, um das nächste Verb monadisch aufzurufen)

*/ das Produkt von

q: die Primfaktoren

+ plus (dh mit einem hinzugefügten wo)

2 zwei

= ist gleich

q: die Primfaktoren

Adam
quelle
Ich fand dich [:ekelhaft.
Undichte Nonne
@LeakyNun, aber ich war nicht so schlau wie Conor O'Brien .
Adám
2

J , 15 12 10 Bytes

(+2&=)&.q:

Probieren Sie es online! Funktioniert ähnlich wie unten, hat nur eine andere Logik bezüglich des Ersetzens von 2mit 3.

15 Bytes

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

Probieren Sie es online!

Erläuterung

(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
quelle
Du hast den Algorithmus gewechselt, als ich meinen geschrieben habe. Jetzt verwenden wir das gleiche.
Adám
@Adam Oh, haha. Gute Antwort! Ich konnte der Gelegenheit nicht widerstehen, sie rollhier zu nutzen . :)
Conor O'Brien
Eigentlich kann ich vielleicht noch ein paar Bytes speichern ... edit save some : D
Conor O'Brien
Lustig, dass du es Roll nennst, ich nenne es Under. Ich hoffe, es bald in APL zu bekommen.
Adám
@ Adám Haha es heißt eigentlich unter. Ich habe die Bedingungen verwirrt
Conor O'Brien
2

Pyth , 9 Bytes

Ganzzahlige Ausgabe \ o /

*F+1.|R1P

Testsuite .

Wie es funktioniert

*F+1.|R1P
        P   prime factorization
    .|R1    bitwise OR each element with 1
*F+1        product
Undichte Nonne
quelle
2

Japt , 19 16 10 9 7 Bytes

k ®w3Ã×

Probieren Sie es online!

Erläuterung

 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
quelle
Hah, JS ist mit Japt verbunden. Ein sicheres Zeichen, dass es eine viel kürzere Lösung gibt ;-)
ETHproductions
Hinweise: ×ist eine Abkürzung für r@X*Y}1(oder nur r*1), die sich als nützlich erweisen könnte. Es gibt auch XwYwelche Math.max(X,Y).
ETHproductions
Danke, obwohl die rekursive Lösung wirklich die kürzeste ist.
Luke
Schön! Ich denke, Sie können tun k m_w3Ã×, um ein Byte zu speichern. Auch m_kann auf gekürzt werden ®.
Oliver
2

PHP, 36 Bytes

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

Probieren Sie es online!

Jörg Hülsermann
quelle
1
for($a=$argn;!1&$a;)$a*=3/2;echo$a;Durch das Umbenennen wird $argnein einzelnes Byte gespeichert.
Christoph
2

CJam, 10 9 Bytes

rimf1f|:*

Ganz einfach.

Erläuterung:

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

Hexagony , 28 27 26 Bytes

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

Probieren Sie es online!

Ausgelegt:

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

Dies läuft im Grunde:

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

An dieser Stelle wird gezeigt, wie schwierig es ist, den Loop-Pfad zu finden, um Bytes zu minimieren.

Scherzen
quelle
Verdammt, daran habe ich nicht gedacht
Manfred Radlwimmer
1
@ManfredRadlwimmer Keine Sorge, das Codieren von Inhalten in Hexagony ist eine Leistung für sich
Jo King
1

Japt , 7 Bytes

k mw3 ×

Probieren Sie es online!

Erläuterung

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

R, 42 Bytes

Die einzig richtige Anzahl von Bytes in einer Antwort.

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

Ziemlich einfach, verwendet das gmpPaket zum Faktorisieren x, ersetzt 2s durch 3s und gibt das Produkt zurück.

JAD
quelle
1

Befunge-93 , 20 Bytes

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

Probieren Sie es 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
quelle
17 Bytes
Jo King
1

Perl 6 , 14 Bytes

{1.5**.lsb*$_}

lsb gibt die Position des niedrigstwertigen Bits zurück, von rechts gezählt. Das heißt, wie viele nachgestellte Nullen in der Binärdarstellung sind, was der Anzahl der Faktoren von 2 entspricht. Erhöhen Sie also 3/2 auf diese Potenz, und wir sind fertig.

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

Eigentlich 9 Bytes

w⌠i1|ⁿ⌡Mπ

Probieren Sie es online!

Erläuterung:

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
quelle