Taxi mir ein paar Nummern

9

Taxicab Numbers oder OEIS A011541 sind die kleinsten Zahlen, die als n verschiedene Summen von zwei positiven gewürfelten ganzen Zahlen für aufeinanderfolgende n dargestellt werden können .

Sie müssen die n- te Taxinummer ausdrucken . Dies sollte theoretisch für jedes n funktionieren .

Da jedoch bisher nur 6 Taxinummern entdeckt wurden, wird es kein n über 6 geben. Die Nummern sind 2, 1729, 87539319, 6963472309248, 48988659276962496, 24153319581254312065344.

Sie dürfen diese Variablen nicht hart codieren, da Ihr Programm theoretisch für ein beliebiges n arbeiten muss .

Morgan Thrapp
quelle
Erfordert dies, dass wir Zahlen beliebiger Länge unterstützen? Wenn wir nur Werte bis zu 2 ^ 32-1 verarbeiten können, das Programm jedoch für größere Werte funktionieren würde , wenn sie nur zulässig wären , ist das in Ordnung?
Ingenieur Toast
Klar, das ist gut für mich. Solange der Algorithmus selbst für eine beliebige Zahl funktioniert, sind Sie gut.
Morgan Thrapp

Antworten:

5

Haskell, 60 Bytes

f n=[k|k<-[0..],n<=sum[1|x<-[1..k],y<-[1..x],x^3+y^3==k]]!!0

Ziemlich einfach. Zählt, auf wie viele Arten eine Zahl kals Summe von zwei Würfeln geschrieben werden kann. Filtert für k's so, dass diese Nummer mindestens ist n, und nimmt die erste.

Eine Methode gleicher Länge mit until:

f n=until(\k->n<=sum[1|x<-[1..k],y<-[1..x],x^3+y^3==k])(+1)0
xnor
quelle
Ihr Programm erzeugt die kleinste Zahl, die aus zwei Würfeln besteht, auf n verschiedene Arten. Das Problem besteht darin, die n-te Zahl zu finden, die eine Summe von zwei Würfeln auf zwei verschiedene Arten ist.
Itai Bar-Natan
1
@ ItaiBar-Natan Es sieht für mich so aus, als würde die Spezifikation nach der kleinsten Zahl fragen, die eine Summe von zwei Würfeln auf n verschiedene Arten ist.
xnor
Hoppla, ich habe das Problem noch einmal gelesen und ich denke, Sie haben Recht. Ich glaube, ich habe es falsch verstanden.
Itai Bar-Natan
6

Taxi, 4758 Bytes

Welche Sprache ist besser, um Taxizahlen zu berechnen, als eine, die Taxis simuliert?
Das ist ein Witz. Es gibt so viele bessere Sprachen. Was ist mit den letzten zwei Tagen meines Lebens passiert?

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l 2 r.Pickup a passenger going to Bird's Bench.Pickup a passenger going to Cyclone.Go to Zoom Zoom:n.Go to Cyclone:w.Pickup a passenger going to Rob's Rest.Pickup a passenger going to Cyclone.Go to Bird's Bench:n 1 r 2 r 1 l.Go to Rob's Rest:n.Go to Cyclone:s 1 l 1 l 2 l.[a]Pickup a passenger going to Firemouth Grill.Pickup a passenger going to The Underground.Go to Zoom Zoom:n.Go to Firemouth Grill:w 3 l 2 l 1 r.Go to The Underground:e 1 l.Switch to plan "b" if no one is waiting.Pickup a passenger going to Cyclone.Go to Cyclone:n 3 l 2 l.Switch to plan "a".[b]Go to Firemouth Grill:s 1 r.[c]Pickup a passenger going to Cyclone.Go to Cyclone:w 1 l 1 r 2 r.Pickup a passenger going to Cyclone.Go to Zoom Zoom:n.Go to Cyclone:w.Pickup a passenger going to Multiplication Station.Pickup a passenger going to Multiplication Station.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:s 1 l 2 r 4 l.Pickup a passenger going to Trunkers.Go to Trunkers:s 1 r 2 l.Go to Firemouth Grill:e 1 l 1 r.Switch to plan "e" if no one is waiting.Switch to plan "c".[e]Go to Trunkers:w 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:w 2 r.Pickup a passenger going to Sunny Skies Park.Go to Sunny Skies Park:n 1 r.[f]Go to Trunkers:s 1 l.Switch to plan "g" if no one is waiting.Pickup a passenger going to Sunny Skies Park.Go to Cyclone:w 2 r.Pickup a passenger going to Cyclone.Go to Zoom Zoom:n.Go to Cyclone:w.Go to Sunny Skies Park:n 1 r.Switch to plan "f".[g]Go to Cyclone:w 2 r.Switch to plan "h" if no one is waiting.Pickup a passenger going to Firemouth Grill.Go to Zoom Zoom:n.Go to Firemouth Grill:w 3 l 2 l 1 r.Go to Trunkers:w 1 l 1 r.Switch to plan "g".[h]Go to Sunny Skies Park:n 1 r.Switch to plan "i" if no one is waiting.Pickup a passenger going to Cyclone.Go to Firemouth Grill:s 1 l 1 l 1 r.Pickup a passenger going to Addition Alley.Go to Cyclone:w 1 l 1 r 2 r.Pickup a passenger going to Addition Alley.Pickup a passenger going to Trunkers.Go to Zoom Zoom:n.Go to Trunkers:w 3 l.Go to Addition Alley:w 2 r 2 r 1 r.Pickup a passenger going to Narrow Path Park.Go to Narrow Path Park:n 1 r 1 l 1 r.Go to Cyclone:w 1 l 1 r 2 l.Switch to plan "h".[i]Go to Trunkers:s 1 l.Pickup a passenger going to Knots Landing.Go to Knots Landing:e 1 r 2 l 5 r.Go to Trunkers:w 1 l 3 r 1 l.Switch to plan "j" if no one is waiting.Go to Firemouth Grill:e 1 l 1 r.Switch to plan "e".[j]0 is waiting at Starchild Numerology.Go to Starchild Numerology:w 1 l 2 l.Pickup a passenger going to Addition Alley.[k]Go to Rob's Rest:w 1 r 2 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:s 1 l 1 l 2 l.Pickup a passenger going to Rob's Rest.Pickup a passenger going to Equal's Corner.Go to Zoom Zoom:n.Go to Rob's Rest:w 2 l 2 r 1 r.Go to Narrow Path Park:s 1 l 1 l 1 r 1 r 2 l 5 l.Switch to plan "o" if no one is waiting.Pickup a passenger going to Equal's Corner.Go to Equal's Corner:w 1 l 1 r 2 l 1 l.Switch to plan "l" if no one is waiting.Pickup a passenger going to Knots Landing.1 is waiting at Starchild Numerology.Switch to plan "m".[l]0 is waiting at Starchild Numerology.[m]Go to Starchild Numerology:n 1 r.Pickup a passenger going to Addition Alley.Go to Addition Alley:w 1 r 3 r 1 r 1 r.Pickup a passenger going to Addition Alley.Go to Knots Landing:n 1 r 2 r 1 l.Go to Starchild Numerology:w 1 l 3 r 1 l 1 l 2 l.Switch to plan "k".[o]0 is waiting at Starchild Numerology.Go to Starchild Numerology:w 1 l 1 r 2 l 1 l 3 l.Pickup a passenger going to Equal's Corner.Go to Equal's Corner:w 1 l.Go to Addition Alley:n 4 r 1 r 1 r.Pickup a passenger going to Equal's Corner.Go to Bird's Bench:n 1 l 1 l 1 l 2 r 1 l.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 r 1 l 2 l.Pickup a passenger going to Bird's Bench.Pickup a passenger going to Equal's Corner.Go to Bird's Bench:n 1 r 2 r 1 l.Go to Equal's Corner:n 1 r 1 r.Switch to plan "p" if no one is waiting.Go to Starchild Numerology:n 1 r.Go to Rob's Rest:w 1 r 2 l 1 r.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 l 1 r 1 r 1 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.Switch to plan "z".[p]1 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 r.Pickup a passenger going to Addition Alley.Go to Rob's Rest:w 1 r 2 l 1 r.Pickup a passenger going to Addition Alley.Go to Addition Alley:s 1 l 1 l 2 r 1 r 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Rob's Rest.Pickup a passenger going to Cyclone.Go to Rob's Rest:n 1 r 2 r 1 r.Go to Cyclone:s 1 l 1 l 2 l.Switch to plan "a".[z]

Probieren Sie es online aus!
Probieren Sie es online aus, aber mit Kommentaren und Zeilenumbrüchen!
Hinweis: TIO kann Eingaben verarbeiten, die 1jedoch 2ein Timeout-Problem verursachen. Ich habe ein kleines Snippet geschrieben, um den Wert zu drucken, der bei jeder Iteration überprüft wird, und es wurde erst erreicht, 137bevor das Zeitlimit überschritten wurde. Wenn jemand, der weiß, was er tut, es über einen Interpreter ausführen könnte (die Homepage verweist auf eine C ++ - Version ), um höhere Werte zu überprüfen, würde ich es begrüßen. Das Ausführen kann sehr lange dauern.

Ungolfed mit Kommentaren:

[ FIND THE NTH TAXI CAB NUMBER ]
[ https://en.wikipedia.org/wiki/Taxicab_number ]
[ Inspired by https://codegolf.stackexchange.com/q/73827/38183 ]

[ A taxi cab number T(n) is the smallest number that can be made from the sum  ]
[ of two positive cubes in n different ways. For example, T(1) = 2 because     ]
[ 2 = 1^3 + 1^3. That is the only way to make 2 by summing positive cubes. No  ]
[ solution exists for 1 so 2 is T(1). T(2) = 1729 = 1^3 + 12^3 = 9^3 + 10^3.   ]
[ This program takes n as input and finds T(n). The (bad) psuedocode is:       ]
[                                                                              ]
[    S = STDIN;  // Use Bird's Bench                                           ]
[    T = STDIN;  // Use Rob's Rest. Saves bytes and T(n) > n is always true.   ]
[    while (true) {                                                            ]
[       // Fill an array (Firemouth Grill) with the numbers 1 through T        ]
[       // This will make it much easier to compute the cubes because a taxi   ]
[       // can only carry three passengers at a time.                          ]
[       for (i = T; i > 0; i--) { A.push(i) }                                  ]
[       // Fill an array (Trunkers) with the cubes of all integers 1 through T ]
[       for (i = T; i > 0; i--) { B.push(i ^ 3) }                              ]
[       // Fill an array (Sunny Skies Park) with each possible sum of cubes    ]
[       while (B(0) != null) {                                                 ]
[          // Make copies of the next value to add to each remaining value     ]
[          C.push(B(0));                                                       ]
[          while (B(0) != null) {                                              ]
[             C.push(C(0));                                                    ]
[             D.push(B(0));                                                    ]
[             B.shift();                                                       ]
[          }                                                                   ]
[          // Store each possible sum with this cube                           ]
[          while (C(0) != null) {                                              ]
[             E.push(C(0) + D(0));                                             ]
[             B.push(D(0));                                                    ]
[             C.shift;                                                         ]
[             D.shift;                                                         ]
[          }                                                                   ]
[       }                                                                      ]
[       // Check each possible sum to see if it equals T                       ]
[       N = 0;                                                                 ]
[       while (D(0) != null) {                                                 ]
[          if (D(0) = T) { N++ }                                               ]
[          D.shift();                                                          ]
[       }                                                                      ]
[       // If we found the desired number of sums, ouput and break             ]
[       // Otherwise, go to the next T and keep going                          ]
[       if (N = S) {                                                           ]
[          print(T);                                                           ]
[          break;                                                              ]
[       } else {                                                               ]
[          T++;                                                                ]
[       }                                                                      ]
[    }                                                                         ]
[                                                                              ]



[ S = STDIN;  // Use Bird's Bench                                         ]
[ T = STDIN;  // Use Rob's Rest. Saves bytes and T(n) > n is always true. ]
Go to Post Office: west 1st left 1st right 1st left.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left 1st left 2nd right.
Pickup a passenger going to Bird's Bench.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north.
Go to Cyclone: west.
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Cyclone.
Go to Bird's Bench: north 1st right 2nd right 1st left.
Go to Rob's Rest: north.


[ // Fill an array (Firemouth Grill) with the numbers 1 through T      ]
[ // This will make it much easier to compute the cubes because a taxi ]
[ //  can only carry three passengers at a time.                       ]
[ for (i = T; i > 0; i--) { A.push(i) }                                ]
Go to Cyclone: south 1st left 1st left 2nd left.
[a]
Pickup a passenger going to Firemouth Grill.
Pickup a passenger going to The Underground.
Go to Zoom Zoom: north.
Go to Firemouth Grill: west 3rd left 2nd left 1st right.
Go to The Underground: east 1st left.
Switch to plan "b" if no one is waiting.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 3rd left 2nd left.
Switch to plan "a".


[b]
[ // Fill an array (Trunkers) with the cubes of all integers 1 through T ]
[ for (i = T; i > 0; i--) { B.push(i ^ 3); }                             ]
Go to Firemouth Grill: south 1st right.
[c]
Pickup a passenger going to Cyclone.
Go to Cyclone: west 1st left 1st right 2nd right.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north.
Go to Cyclone: west.
Pickup a passenger going to Multiplication Station.
Pickup a passenger going to Multiplication Station.
Pickup a passenger going to Multiplication Station.
Go to Multiplication Station: south 1st left 2nd right 4th left.
Pickup a passenger going to Trunkers.
Go to Trunkers: south 1st right 2nd left.
Go to Firemouth Grill: east 1st left 1st right.
Switch to plan "e" if no one is waiting.
Switch to plan "c".


[e]
[ // Fill an array with each possible sum of cubes                ]
[ while (B(0) != null) {                                          ]
[ // Make copies of the next value to add to each remaining value ]
[ C.push(B(0));                                                   ]
[ while (B(0) != null) {                                          ]
[    C.push(C(0));                                                ]
[    D.push(B(0));                                                ]
[    B.shift();                                                   ]
[ }                                                               ]
[ Setup Cyclone with a copy of the first value ]
Go to Trunkers: west 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: west 2nd right.
Pickup a passenger going to Sunny Skies Park.
Go to Sunny Skies Park: north 1st right.

[f]
[ Move any remaining values to Sunny Skies Park, duplicating Cyclone each time ]
Go to Trunkers: south 1st left.
Switch to plan "g" if no one is waiting.
Pickup a passenger going to Sunny Skies Park.
Go to Cyclone: west 2nd right.
Pickup a passenger going to Cyclone.
Go to Zoom Zoom: north.
Go to Cyclone: west.
Go to Sunny Skies Park: north 1st right.
Switch to plan "f".

[g]
[ // Store each possible sum with this cube ]
[ while (C(0) != null) {                    ]
[    E.push(C(0) + D(0));                   ]
[    B.push(D(0));                          ]
[    C.shift;                               ]
[    D.shift;                               ]
[ }                                         ]
[ Move everything at Cyclone to Firemouth Grill ]
Go to Cyclone: west 2nd right.
Switch to plan "h" if no one is waiting.
Pickup a passenger going to Firemouth Grill.
Go to Zoom Zoom: north.
Go to Firemouth Grill: west 3rd left 2nd left 1st right.
Go to Trunkers: west 1st left 1st right.
Switch to plan "g".

[h]
[ Copy Sunny Skies Park to Trunkers and add it to Firemouth Grill ]
Go to Sunny Skies Park: north 1st right.
Switch to plan "i" if no one is waiting.
Pickup a passenger going to Cyclone.
Go to Firemouth Grill: south 1st left 1st left 1st right.
Pickup a passenger going to Addition Alley.
Go to Cyclone: west 1st left 1st right 2nd right.
Pickup a passenger going to Addition Alley.
Pickup a passenger going to Trunkers.
Go to Zoom Zoom: north.
Go to Trunkers: west 3rd left.
Go to Addition Alley: west 2nd right 2nd right 1st right.
Pickup a passenger going to Narrow Path Park.
Go to Narrow Path Park: north 1st right 1st left 1st right.
Go to Cyclone: west 1st left 1st right 2nd left.
Switch to plan "h".

[i]
[ } // End of 'while (B(0) != null)' up near plan "e" ]
Go to Trunkers: south 1st left.
Pickup a passenger going to Knots Landing.
Go to Knots Landing: east 1st right 2nd left 5th right.
Go to Trunkers: west 1st left 3rd right 1st left.
Switch to plan "j" if no one is waiting.
Go to Firemouth Grill: east 1st left 1st right.
Switch to plan "e".


[j]
[ // Check each possible sum to see if it equals T ]
[ N = 0;                                           ]
[ while (D(0) != null) {                           ]
[    if (D(0) = T) { N++; }                        ]
[    D.shift();                                    ]
[ }                                                ]
[ Set N = 0 ]
0 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 1st left 2nd left.
Pickup a passenger going to Addition Alley.

[k]
[ Pickup T ]
Go to Rob's Rest: west 1st right 2nd left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: south 1st left 1st left 2nd left.
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Equal's Corner.
Go to Zoom Zoom: north.
Go to Rob's Rest: west 2nd left 2nd right 1st right.
Go to Narrow Path Park: south 1st left 1st left 1st right 1st right 2nd left 5th left.
Switch to plan "o" if no one is waiting.

[ Check the next value against T ]
Pickup a passenger going to Equal's Corner.
Go to Equal's Corner: west 1st left 1st right 2nd left 1st left.
Switch to plan "l" if no one is waiting.

[ It's a match so N = N + 1 ]
Pickup a passenger going to Knots Landing.
1 is waiting at Starchild Numerology.
Switch to plan "m".

[l]
[ It's not a match so N = N + 0 ]
0 is waiting at Starchild Numerology.

[m]
Go to Starchild Numerology: north 1st right.
Pickup a passenger going to Addition Alley.
Go to Addition Alley: west 1st right 3rd right 1st right 1st right.
Pickup a passenger going to Addition Alley.
Go to Knots Landing: north 1st right 2nd right 1st left.
Go to Starchild Numerology: west 1st left 3rd right 1st left 1st left 2nd left.
Switch to plan "k".


[o]
[ // If we found the desired number of sums, ouput and break ]
[ // Otherwise, go to the next T and keep going              ]
[ if (N = S) {                                               ]
[    print(T);                                               ]
[    break;                                                  ]
[ } else {                                                   ]
[    T++;                                                    ]
[ }                                                          ]
[ T is still going to Equal's Corner so just get rid of it ]
0 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 1st left 1st right 2nd left 1st left 3rd left.
Pickup a passenger going to Equal's Corner.
Go to Equal's Corner: west 1st left.

[ N is still going to Addition Alley so redirect it to Equal's Corner ]
Go to Addition Alley: north 4th right 1st right 1st right.
Pickup a passenger going to Equal's Corner.

[ Compare N = S ]
Go to Bird's Bench: north 1st left 1st left 1st left 2nd right 1st left.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st right 1st left 2nd left.
Pickup a passenger going to Bird's Bench.
Pickup a passenger going to Equal's Corner.
Go to Bird's Bench: north 1st right 2nd right 1st left.
Go to Equal's Corner: north 1st right 1st right.
Switch to plan "p" if no one is waiting.

[ It's a match! The value we want is T, waiting at Rob's Rest. ]
[Go to Rob's Rest:n 3 l 1 r.]
Go to Starchild Numerology: north 1st right.
Go to Rob's Rest: west 1st right 2nd left 1st right.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 1st left 1st right 1st right 1st right.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st left 1st right.
Switch to plan "z".

[p]
[ It's not a match. T = T + 1 and start over. ]
1 is waiting at Starchild Numerology.
Go to Starchild Numerology: north 1st right.
Pickup a passenger going to Addition Alley.
Go to Rob's Rest: west 1st right 2nd left 1st right.
Pickup a passenger going to Addition Alley.
Go to Addition Alley: south 1st left 1st left 2nd right 1st right 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left 1st left.
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Cyclone.
Go to Rob's Rest: north 1st right 2nd right 1st right.
Go to Cyclone: south 1st left 1st left 2nd left.
Switch to plan "a".

[z]
[ Terminate program with 10 less bytes than going back to the Taxi Garage ]
Ingenieur Toast
quelle
Ich liebe es, wie verrückt eine Sprache Taxi ist.
Morgan Thrapp
@MorganThrapp Ich hatte nicht vor in diesen läuft, aber es wurde schnell ein Problem , dass Sie ein Maximum von 6 Integer Arrays speichern können und das ist nur , weil Trunkersund Rounders Pubschön mit ganzen Zahlen spielen. Wenn Sie Dezimalstellen speichern, erhalten Sie nur 4 Arrays. Außerdem werden Firemouth Grilldie Zahlen in zufälliger Reihenfolge erfasst, sodass sie nicht angezeigt werden, wenn Sie die Reihenfolge beibehalten müssen. Wirklich, Sie erhalten nur 2 Warteschlangen und 1 Stapel. Viel Glück.
Ingenieur Toast
Ich würde mich über billige Upvotes beschweren, die für Einsendungen in lustigen Sprachen abgegeben wurden, aber das verdient sowieso eine Upvote.
Esolanging Fruit