My Favorite Sequences: A289523

This the second post in what will be a recurring series, My Favorite OEIS Sequences. Click here for the first post.

(If you like this sort of thing, check out the Integer Sequence Review from The Aperiodical!)

A289523: Packing Circles of Increasing Area

A plot of the circles in A289523.

In July 2017, I added a mathematically-silly-but-visually-fun sequence, A289523. The sequence works like this: place a circle of area \(\pi\) centered at \((1,1)\), then place a circle of area \(2\pi\) centered at \((2,a(2))\) where \(a(2) = 4\), the least positive integer such that the circle does not overlap with the first circle. Next, place a circle of area \(3\pi\) centered at \((3,a(3))\) where \(a(3) = 7\) is the least positive integer such that the circle does not overlap with the first two circle. Continue this pattern ad infinitum, creating the earliest infinite sequence of positive integers such that no two circles overlap with any others, and a circle centered at \((k, a(k))\) has area \(k\pi\).

I haven’t done much mathematical analysis on this problem, but it would be interesting to see if it’s possible to compute (or put some bounds on) the packing density of the convex hull of the circles. Also, a glance at a plot of the points suggests that the sequence is bounded above by a linear function—is this the case?

The sequence begins 1, 4, 7, 1, 11, 16, 5, 21, 27, 34, 10, 1, 41, 17, 49, 25, 57, 6, 33, 66, 43, 14, ....

Finding an upper bound

The scatter plot of A289523 suggests that the centers of the circles have a linear upper bound. This is to be expected! The areas of the circles increase linearly, and the packing density is (presumably) nonzero.

What is the slope of the upper bound? And what is the packing density of these circles in the limit?

A scatter plot of A289523.

Related Construction

At the end of March, I posted a related puzzle, “Placing Circles Along a Square Spiral”, on Code Golf Stack Exchange. For the post, I made a few animated GIFs that explain the construction and tweeted about them.

Impressively, Code Golf Stack Exchange users tsh, Arnauld, and A username each wrote (deliberately terse) Javascript code that computes the placement of these circles.

In fact, they compute something strictly harder! In the challenge, after laying down all of these circles (in blue), the challenge instructed them to go back to the start and greedily fill the gaps with (red) circles of increasing area. Next, they laid down a third (yellow) generation in the same fashion, and fourth (cyan) generation, and so on.

An animation illustrating successive generations of circles on a square spiral.

Related questions

  • What is the packing density of the first (blue) generation?
  • What is the packing density of the \(k\)-th generation?
  • How many “steps” away from the origin is the smallest circle in the \(k\)-th generation?
  • Do an infinite number of blue circles touch? Do an infinite number of any circles touch? Which ones?
  • How far can a circle be from its neighbors? Which circles are maximally far from their neighbors?
  • How does this work if the path the circles follow is not the spiral? Can different paths have significantly different packing densities?

If you have thoughts or ideas about any of this—or if you just want to make animated GIFs together—leave a comment or let me know on Twitter, @PeterKagey!

My Favorite Sequences: A261865

This is the first installment in a new series, “My Favorite Sequences”. In this series, I will write about sequences from the On-Line Encyclopedia of Integer Sequences that I’ve authored or spent a lot of time thinking about.

I’ve been contributing to the On-Line Encyclopedia of Integer Sequences since I was an undergraduate. In December 2013, I submitted sequence A233421 based on problem A2 from the 2013 Putnam Exam—which is itself based on “Ron Graham’s Sequence” (A006255)—a surprising bijection from the natural numbers to the non-primes. As of today, I’ve authored over 475 sequences based on puzzles that I’ve heard about and problems that I’ve dreamed up.

A261865: Multiples of square roots

(This problem is closely related to Problem 13 in my Open Problems Collection.)

In September 2015, I submitted sequence A261865:

\(A261865(n)\) is the least integer \(k\) such that some multiple of \(\sqrt k\) falls in the interval \((n, n+1)\).

An illustration of the first dozen terms of A261865

For example, \(A261865(3) = 3\) because there is no multiple of \(\sqrt 1\) in \((3,4)\) (since \(3 \sqrt{1} \leq 3\) and \(4 \sqrt{1} \geq 4\)); there is no multiple of \(\sqrt{2}\) in \((3,4)\) (since \(2 \sqrt{2} \leq 3\) and \(3 \sqrt 2 \geq 4\)); but there is a multiple of \(\sqrt 3\) in \((3,4)\), namely \(2\sqrt 3\).

As indicated in the picture, the sequence begins $$\color{blue}{ 2,2,3,2,2},\color{red}{3},\color{blue}{2,2,2},\color{red}{3},\color{blue}{2,2},\color{red}{3},\color{blue}{2,2,2},\color{red}{3},\color{blue}{2,2},\color{red}{3},\color{blue}{2,2},\color{magenta}{7},\dots.$$

A scatterplot of \(A261865(n)\). Notice the records at \(A261865(184)=38\) and \(A261865(8091)=43\).

A conjecture about density

As the example illustrates, \(1\) does not appear in the sequence. And almost by definition, asymptotically \(1/\sqrt 2\) of the values are \(2\)s.

Let’s denote the asymptotic density of terms that are equal to \(n\) by \(d_n\). It’s easy to check that \(d_1 = 0\), (because multiples of \(\sqrt 1\) are never between any integers) and \(d_2 = 1/\sqrt 2\), because multiples of \(\sqrt 2\) are always inserted. I conjecture in Problem 13 of my Open Problem Collection that $$a_n = \begin{cases}\displaystyle\frac{1}{\sqrt n}\left(1 – \sum_{i=1}^{n-1} a_i\right) & n \text{ is squarefree}\\[5mm] 0 & \text{otherwise}\end{cases}$$

If this conjecture is true, then the following table gives approximate densities.

\(i\)\(d_i\)
\(1\)\(d_1 = 0\%\)
\(2\)\(d_2 = 70.7\%\)
\(3\)\(d_3 = 16.9\%\)
\(4\)\(d_4 = 0\%\)
\(5\)\(d_5 = 5.54\%\)
\(6\)\(d_6 = 2.79\%\)
\(7\)\(d_7 = 1.53\%\)
\(10\)\(d_{10} = 0.797\%\)
\(11\)\(d_{11} = 0.519\% \)
\(399\)\(d_{399} = 3.53 \times 10^{-11} \%\)

This was computed with the Mathematica code:

d[i_] := (d[i] = If[
  SquareFreeQ[i], 
  N[(1 - Sum[d[j], {j, 2, i - 1}])/Sqrt[i], 50], 
  0
])

Finding Large Values

I’m interested in values of \(n\) such that \(A261865(n)\) is large, and I reckon that there are clever ways to construct these, perhaps by looking at some Diophantine approximations of \(\sqrt{2}, \sqrt{3}, \sqrt{5}, \sqrt{6}, \dots\). In February, I posted a challenge on Code Golf Stack Exchange to have folks compete in writing programs that can quickly find large values of \(A261865(n)\).

Impressively, Noodle9’s C++ program won the challenge. In under a minute, this program found that the input \(n=1001313673399\) makes \(A261865\) particularly large: \(A261865(1001313673399) = 399\). Within the time limit, no other programs could find a value of \(n\) that makes \(A261865(n)\) larger.

\(n\)Order of magnitude\(A261865(n)\)Time
1 \(1 \times 10^{0}\)2(0s)
3 \(3 \times 10^{0}\)3 (0s)
23 \(2.3 \times 10^{1}\)7 (0s)
30 \(3.0 \times 10^{1}\)15 (0s)
184 \(1.84 \times 10^{2}\)38 (0s)
8091 \(8.091 \times 10^{3}\)43 (0s)
16060 \(1.606 \times 10^{4}\)46 (0s)
16907 \(1.691 \times 10^{4}\)58 (0s)
20993 \(2.099 \times 10^{4}\)61 (0s)
26286 \(2.629 \times 10^{4}\)97 (0s)
130375 \(1.304 \times 10^{5}\)118 (0s)
169819 \(1.698 \times 10^{5}\)127 (0s)
2135662 \(2.136 \times 10^{6}\)130 (0s)
2345213 \(2.345 \times 10^{6}\)187 (0s)
46272966 \(4.627 \times 10^{7}\)193 (1s)
222125822 \(2.221 \times 10^{8}\)210 (5.2s)
237941698 \(2.379 \times 10^{8}\)217 (5.7s)
257240414 \(2.572 \times 10^{8}\)227 (6.2s)
1205703469 \(1.206 \times 10^{9}\)267 (31s)
1558293414 \(1.558 \times 10^{9}\)299 (41.8s)
4641799364 \(4.642 \times 10^{9}\)303 (2.1m)
6600656102 \(6.601 \times 10^{9}\)323 (3m)
11145613453 \(1.115 \times 10^{10}\)335 (5.2m)
20641456345 \(2.064 \times 10^{10}\)354 (9.8m)
47964301877 \(4.796 \times 10^{10}\)358 (22.9m)
105991039757 \(1.06 \times 10^{11}\)385 (52m)
119034690206 \(1.19 \times 10^{11}\)397 (59.1m)
734197670865 \(7.342 \times 10^{11}\)455 (6.4h)
931392113477 \(9.314 \times 10^{11}\)501 (8.4h)
1560674332481 \(1.561 \times 10^{12}\)505 (14.2h)
A table of record values as computed by Code Golf Stack Exchange user Neil. The first 16 values agree with Jon E. Schoenfield’s computations that were added to the OEIS in September 2015

Related Ideas

Sequence \(A327953(n)\) counts the number of positive integers \(k\) such that there is some integer \(\alpha^{(n)}_k > 2\) where \(\alpha^{(n)}_k\sqrt{k} \in (n, n+1)\). It appears to grow roughly linearly like \(A327953(n) \sim 1.3n\), but I don’t know how to prove this.

  • Take any function \(f\colon\mathbb N \rightarrow \mathbb R\) that is positive, has positive first derivative, and has negative second derivative. Then, what is the least \(k\) such that some multiple of \(f(k)\) is in \((n,n+1)\)?
  • For example, what is the least integer \(k \geq 3\) such that there is a multiple of \(\ln(k)\) in \((n, n+1)\)?
  • What is the least \(k \in \mathbb N\) such that there exists \(m \in \mathbb N\) with \(k2^{1/m} \in (n,n+1)\)?
  • What is the least \(m \in \mathbb N\) such that there exists \(k \in \mathbb N\) with \(k2^{1/m} \in (n,n+1)\)?
  • A343205 is the auxiliary sequence that gives the value \(m\) such that \(m\sqrt{A261865(n)} \in (n, n+1)\). Does this sequence have an infinite limit inferior?
Scatterplot of A343205, generated in Mathematica. If the main conjecture is true, then this is not bounded below by \(\alpha n\) for any positive value of \(\alpha\).

If you can answer any of these questions, or if you spend time thinking about this, please let me know on Twitter, @PeterKagey!