14
\$\begingroup\$

Consider compass-and-straightedge construction, where you can construct new points from existing ones by examining intersections of straight lines and circles constructed with one of the following two options:

  • Draw the unique infinitely long straight line passing through points \$(x, y)\$ and \$(x', y')\$
  • Draw the unique circle centered on \$(x, y)\$ that passes through the distinct point \$(x', y')\$

We begin with two points, typically \$(0, 0)\$ and \$(1, 0)\$, but any two distinct points suffice. If we draw all possible lines and circles using these two points, how many total points do we end up with?

Spoiler: 6, shown below.

Two circles with a horizontal line passing through them both. There are 6 points labeled A through F at all intersection points

If we now repeat this procedure - drawing every line between two points and every circle determined by two existing points - and then add the newly constructed points to our set, we end up with 203 total points. We can then do this again, and again, and so on to form a sequence that begins $$2, 6, 203, 1723816861$$

This is A333944, added to OEIS after this Math.SE question was asked about the 4th term in the sequence. Note that, as of writing, only \$4\$ terms exist in the sequence on OEIS.

Unsurprisingly, your task is to output this sequence. This is a standard challenge, meaning that you may complete one of the following options, using \$0\$ or \$1\$ indexing of your choice (if applicable):

  • Take an integer \$n\$ and output the \$n\$th term in the sequence
  • Take an integer \$n\$ and output the first \$n\$ terms in the sequence
  • Output the sequence indefinitely, in ascending order

This is , so the shortest code in bytes in each language wins.

In the linked Math.SE question, the answer provides some Haskell code which completes this task. Unsurpsingly, it is highly ungolfed, and very slow, taking approximately \$6\$ days to find the fourth term in the sequence. I offer a 1000 rep bounty (\$2 \times 500\$ rep bounties) for the first answer which can find and verify the 5th term in the sequence. The rough upper bound given in the linked question suggests that it is no larger than \$10^{314}\$.

Improve this question
\$\endgroup\$
8
  • \$\begingroup\$ Sandbox \$\endgroup\$ Commented Dec 9, 2023 at 5:47
  • \$\begingroup\$ How 5th term is far smaller than 4th term 4th power? \$\endgroup\$ Commented Jan 2, 2024 at 10:55
  • \$\begingroup\$ @l4m2 As explained in the linked Math.SE, the upper bound is around \$18^n2^{4^n}\$ for each \$n\$ \$\endgroup\$ Commented Jan 2, 2024 at 16:10
  • \$\begingroup\$ \$n=5, 18^n 2^{4^n} = 3.4 \times 10^{314}\$ \$\endgroup\$ Commented Jan 2, 2024 at 17:33
  • \$\begingroup\$ @l4m2 Thanks, must have miscalculated \$\endgroup\$ Commented Jan 2, 2024 at 19:26

1 Answer 1

Reset to default
5
\$\begingroup\$

Python+sympy, 247 bytes

from sympy import*
from itertools import*
c,C,p=combinations,Circle,{a:=Point(0,1),a*2}
while[l:=set()]:
 print(len(p))
 for a,b in c(p,2):l|={Line(a,b),C(a,d:=abs(a-b)),C(b,d)}
 for a in c(l,2):p|={i for i in intersection(*a)if type(i)is Point2D}

Unfortunately, the challenge is quite trivial with sympy. I do have another solution without using modules, which should theoretically work, but doesn't due to rounding errors. Might post that later when fixed.
Extremely slow ofc.

Attempt This Online! (modified code to work on ATO)

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.