Hi! I’m Peter!


Blog


  • My Favorite Sequences: A289523

    This the second post in a recurring series, My Favorite Sequences. 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.

    https://twitter.com/PeterKagey/status/1375960530863628290

    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\). The size of the points is proportional to \(\log(A261865(n))\) and the points are colored so that the values are redder when \(A261865(n)\) is small.

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

  • Richard Guy’s Partition Sequence

    Neil Sloane is the founder of the On-Line Encyclopedia of Integer Sequences (OEIS). Every year or so, he gives a talk at Rutgers in which he discusses some of his favorite recent sequences. In 2017, he spent some time talking about a 1971 letter that he got from Richard Guy, and some questions that went along with it. In response to the talk, I investigated the letter and was able to sort out Richard’s 45-year-old idea, and correct and compute some more terms of his sequence.

    Richard Guy and his sequences

    Richard Guy was a remarkable mathematician who lived to the remarkable age of 103 years, 5 months, and 9 days! His life was filled with friendships and collaborations with many of the giants of recreational math: folks like John Conway, Paul Erdős, Martin Gardner, Donald Knuth, and Neil Sloane. But what I love most about Richard is how much joy and wonder he found in math. (Well, that and his life-long infatuation with his wife Louise.)

    Richard guy mountaineering at age 98 with a photo of his late wife, Louise.

    [I’m] an amateur [mathematician], I mean I’m not a professional mathematician. I’m an amateur in the more genuine sense of the word in that I love mathematics and I would like everybody in the world to like mathematics.

    Richard Guy in Fascinating Mathematical People: Interviews and Memoirs

    Richard’s letter to Neil

    In January 2017, Neil Sloane gave a talk at Doron Zeilberger’s Experimental Mathematics Seminar, and about six minutes in, Neil discusses a letter that Richard sent to him at Cornell—which was the forwarded to Bell Labs—in June 1971.

    Richard Guy’s 1971 letter to Neil Sloane.

    When I was working on the book, the 1973 Handbook of Integer Sequences, I would get letters from Richard Guy from all over the world. As he traveled around, he would collect sequences and send them to me.

    Neil Sloane, Rutgers Experimental Mathematics Seminar

    At 11:30, Neil discusses “sequence I” from Richard’s letter, which he added to the OEIS as sequence A279197:

    Number of self-conjugate inseparable solutions of \(X + Y = 2Z\) (integer, disjoint triples from \(\{1,2,3,\dots,3n\}\)).

    Neil mentioned in the seminar that he didn’t really know exactly what the definition meant. With some sleuthing and programming, I was able to make sense of the definition, write a Haskell program, correct the 7th term, and extend the sequence by a bit. The solutions for \(A279197(1)\) through \(A279197(10)\) are listed in a file I uploaded to the OEIS, and Fausto A. C. Cariboni was able to extend the sequence even further, submitting terms \(A279197(11)\)–\(A279197(17)\).

    How the sequence works.

    The idea here is to partition \(\{1,2,3,\dots,3n\}\) into length-3 arithmetic progressions, \(\bigl\{\{X_i,Z_i,Y_i\}\bigr\}_{i=1}^{n}\). And in particular, we want them to be inseparable and self-conjugate.

    An inseparable partition is one whose “smallest” subsets are not a solution for a smaller case. For example, if \(n=3\), then the partition \[\bigl\{ \{1,3,5\}, \{2,4,6\}, \{7,8,9\} \bigr\}\] is separable, because if the subset \(\bigl\{ \{1,3,5\}, \{2,4,6\} \bigr\}\) is a solution to the \(n=2\) case.

    A self-conjugate partition is one in which swapping each \(i\) with each \(3n+1-i\) gets back to what we started with. For example, \(\bigl\{\{1,3,5\}, \{2,4,6\}\bigr\}\) is self-congugate, because if we replace the \(1\) with a \(6\) and the \(2\) with a \(5\), and the \(i\) with a \(7-i\), then we get the same set: \(\bigl\{\{6,4,2\}, \{5,3,1\} \bigr\}\)

    (1,3,5),  (2,7,12), (4,9,14),  (6,8,10),  (11,13,15)
    (1,3,5),  (2,8,14), (4,7,10),  (6,9,12),  (11,13,15)
    (1,5,9),  (2,3,4),  (6,8,10),  (7,11,15), (12,13,14)
    (1,5,9),  (2,4,6),  (3,8,13),  (7,11,15), (10,12,14)
    (1,6,11), (2,3,4),  (5,10,15), (7,8,9),   (12,13,14)
    (1,6,11), (2,7,12), (3,8,13),  (4,9,14),  (5,10,15)
    (1,7,13), (2,4,6),  (3,9,15),  (5,8,11),  (10,12,14)
    (1,7,13), (2,8,14), (3,9,15),  (4,5,6),   (10,11,12)
    (1,8,15), (2,3,4),  (5,6,7),   (9,10,11), (12,13,14)
    (1,8,15), (2,4,6),  (3,5,7),   (9,11,13), (10,12,14)
    (1,8,15), (2,4,6),  (3,7,11),  (5,9,13),  (10,12,14)
    Each line shows one of the \(A279197(5) = 11\) inseparable, self-conjugate partitions of \(\{1,2,\dots,15\}\).

    Generalizing Richard Guy’s idea

    Of course, it’s natural to wonder about the separable solutions, or what happens if the self-conjugate restriction is dropped. In exploring these cases, I found four cases already in the OEIS, and I computed five more: A282615A282619.

    SeparableInseparableEither
    Self-conjugateA282615A279197 A282616
    Non-self-conjugateA282618A282617 A282619
    EitherA279199A202705 A104429
    Table of sequences counting the ways of partitioning a set into length-3 arithmetic progressions, subject to various restrictions.

    Generalizing further

    There are lots of other generalizations that might be interesting to explore. Here’s a quick list:

    • Look at partitions of \(\{1,2,\dots,kn\}\) into \(n\) parts, all of which are an arithmetic sequence of length \(k\).
    • Count partitions of \(\{1,2,\dots,n\}\) into any number of parts of (un)equal size in a way that is (non-)self-conjugate and/or (in)separable.
    • Consider at partitions of \(\{1,2,\dots,3n\}\) into \(n\) parts, all of which are an arithmetic sequence of length \(3\), and whose diagram is “non-crossing”, that is, none of the line segments overlap anywhere. (See the 6th and 11th cases in the example for \(A279197(6) = 11\).)

    If explore any generalizations of this problem on your own, if you’d like to explore together, or if you have an anecdotes about Richard Guy that you’d like to share, let me know on Twitter!