-5
\$\begingroup\$

Foreword

This is my first prompt submitted to Code Golf. If you have any suggestions on how to make the prompt more interesting, please let me know. This was a problem that I recently had to solve, and found it to be quite challenging. I'm curious how it could be accomplished in other languages. If anyone wants to see an example of it working in Swift, please let me know.

Challenge

Write the shortest function f(x), measured in bytes of code, that outputs the Collatz-Terras orbit of a starting number x + 10^(1500) - 3^(1499), where x is an arbitrary-length unsigned integer 0 or higher. The function may call other functions as needed. See further requirements below.

Objective winning criteria

The program or function written using the shortest length of code (not counting dependencies/runtimes etc.) will win. Deadline is Oct. 31, 2022, at 3:01 PST.

Affordances

You may provide code for a full executable if that's the only way to meet the requirements stated herein.

If your chosen programming language does not natively support arbitrary-sized integers, you may list a third-party dependency to import (e.g. "BigInt" or similar) for your language to support these very large numbers without it counting against your golf score.

Detailed Requirements

Your program/function must give output and status updates as it computes, in the following format:

  • each time the orbit "drops below" the starting number, x + 10^(1500) - 3^(1499) (i.e. when the the calculation yields a number smaller than the starting number following a number larger than the starting number) the function should output "dropped below original x after n turns" where n is how many numbers were in the orbit before the number that dropped below x
  • if the orbit goes back above and below the original number multiple times, each time it again drops below the original x, "dropped below original x after n turns" should be stated stated, where n is cumulative from the beginning
  • the status updates should be provided at the beginning and each time 1000 more numbers get added to the orbit via the algorithm like so: "orbit count: 0", then "orbit count: 1000", then "orbit count: 2000", etc., each on a new line, so the user knows the program has not crashed
  • once the algorithm is finished computing the full orbit, it should print the orbit to stdout or console (etc.) as an array in the format shown below in the example output; the array should include the first number all the way to the last number, 1

Additional requirements: the algorithm must not crash or get killed off by the operating system and must support orbit lengths of at least 26,000 cycles. How to avoid crashing, and how to perform the task in available memory, is the main hurdle of this challenge. It should be performable on a computer with 64 GB of RAM and 100 GB free disk space. If you lack these computing resources, I will personally verify the result and post a video to YouTube proving it works.

Criteria of the required algorithm:

The algorithm must calculate a Collatz-Terras "orbit", which is the sequences of numbers produced by applying the following rules, starting with the initial number input as text:

  • for an even number, apply (3x+1)/2 to get the next number in the orbit
  • for an odd number, apply x/2 to get the next number in the orbit
  • when the orbit reaches the number 1, the program stops and outputs the full orbit up to that point, including 1 and the starting number

The limit on the size of n should only be the physical limitations of the host machine. Your program should be able to handle n from zero up to 10^100.

Sample Output

Output for f(0) can be found here.

Full text of first few outputs from lowest starting number, e.g. where n=0:

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999983976373076290994055527199978713191702252517585025161701355165427499618901026068213766941244727174294425738541350807136464340281991942711944556808394172235372990429821342274340134593422669493056495101875076075121064036435192372552198025399838366118794089801126865133034324613337694832886502285674921909127309815984700696258009587109273386849065683682902528225002098169465678651033437594606894996240470284056210517574452804361346791265349847168972453615247972522869970097389978686957633520283341006136789657238421765633960340973665918054709754913944564955211404628395523034730267762545419380315732415753182484660612894717205535410093203816054737901784686072839755080728868286861299305050306865126810006677225855723333...
orbit count: 0
dropped below original x after 2 turns
orbit count: 1000
orbit count: 2000
orbit count: 3000
orbit count: 4000
orbit count: 5000
orbit count: 6000
orbit count: 7000
orbit count: 8000
orbit count: 9000
orbit count: 10000
orbit count: 11000
orbit count: 12000
orbit count: 13000
orbit count: 14000
orbit count: 15000
orbit count: 16000
orbit count: 17000
orbit count: 18000
orbit count: 19000
orbit count: 20000
orbit count: 21000
orbit count: 22000
orbit count: 23000
fell to one: true
orbit (excluding 3x + 1's before dividing by 2): [999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999983976373076290994055527199978713191702252517585025161701355165427499618901026068213766941244727174294425738541350807136464340281991942711944556808394172235372990429821342274340134593422669493056495101875076075121064036435192372552198025399838366118794089801126865133034324613337694832886502285674921909127309815984700696258009587109273386849065683682902528225002098169465678651033437594606894996240470284056210517574452804361346791265349847168972453615247972522869970097389978686957633520283341006136789657238421765633960340973665918054709754913944564955211404628395523034730267762545419380315732415753182484660612894717205535410093203816054737901784686072839755080728868286861299305050306865126810006677225855723333, 1499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999975964559614436491083290799968069787553378776377537742552032748141249428351539102320650411867090761441638607812026210704696510422987914067916835212591258353059485644732013411510201890134004239584742652812614112681596054652788558828297038099757549178191134701690297699551486920006542249329753428512382863690964723977051044387014380663910080273598525524353792337503147254198517976550156391910342494360705426084315776361679206542020186898024770753458680422871958784304955146084968030436450280425011509205184485857632648450940511460498877082064632370916847432817106942593284552095401643818129070473598623629773726990919342075808303115139805724082106852677029109259632621093302430291948957575460297690215010015838783585000, 749999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999987982279807218245541645399984034893776689388188768871276016374070624714175769551160325205933545380720819303906013105352348255211493957033958417606295629176529742822366006705755100945067002119792371326406307056340798027326394279414148519049878774589095567350845148849775743460003271124664876714256191431845482361988525522193507190331955040136799262762176896168751573627099258988275078195955171247180352713042157888180839603271010093449012385376729340211435979392152477573042484015218225140212505754602592242928816324225470255730249438541032316185458423716408553471296642276047700821909064535236799311814886863495459671037904151557569902862041053426338514554629816310546651215145974478787730148845107505007919391792500, 
... (see full output file linked above for the rest)

Good luck.

\$\endgroup\$
1
  • \$\begingroup\$ This challenge is perfectly valid, and well written. However, what I (and probably all the downvoters) have against this challenge is that it simply has too much fluff on top of the actual task: to compute the orbits. It is simply too uninteresting to give status updates, and it will cost a lot in code. The fact that it must go within memory constraints adds another block, as here we can submit answers as long as we can prove it gives the desired output within finite time and infinite memory. \$\endgroup\$
    – Seggan
    Sep 22 at 20:49

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.