Ponder This Challenge - December 2023 - Circles on a triangular grid

This riddle was proposed by Hugo Pfoertner - thanks Hugo!

We consider the infinite grid of equilateral triangles with sides length 1, such that $(0,0)$ is a grid point.

In this grid, we consider all circles passing through at least one grid point. The smallest circle has radius 1, hitting the grid point $(1,0)$ and 5 other grid points.

We are interested in all the circles with non-integer radii. In the following illustration, all the circles are drawn, and a blue mark denotes the intersection point of a circle with a non-integer radius along the positive direction of the x-axis.

For every positive integer $m$, $f(m)$ denotes the number of circles that pass through at least one grid point, with a radius of $x$ such that $m < x < m+1$.

For example, $f(11)=5$ and $f(42)=19$.

Your goal: Find a value of $m$ such that $f(m)=1,000,000$.

Hint: There is such an $m$ which is a base 10 palindrome, but other solutions are accepted as well.

A Bonus "*" will be given for finding **all** the values of $m$ such that $f(m)=1,000,000$.

Solution

• Click here to view the solution

  December 2023 Solution:

  The solutions are 4310930, 4311298, 4312919, 4313134, 4313718

  A very nice solution was given by Karl Mahlburg:

  This was an exercise in Eisenstein integers. In particular, the desired radii are exactly those (rational) integers that occur as the norm N(z) of an Eisenstein integer z = a + b\omega. So f(n) counts the integers m \in (n^2, (n+1)^2) that can be realized as m = N(z).

  It is known (or straightforward) that N(z) = ((2a-b)^2 + 3b^2) / 4. Therefore, a reasonably efficient approach to the problem is to generate and count the set of all sums of the form (x^2 + 3y^2)/4, where x and y have the same parity, looping through all y, and then restricting x so that the final sum will lie in (n^2, (n+1)^2). With some basic cython optimization, calculating f(4000000) takes about 10s.

  I found some further benefits from "parallelization": by calculating the set E as all sums in the range (n^2, (n+k)^2), and then counting the norms in the individual ranges ((n+j)^2, (n+j+1)^2) using sorted search. Batches in the range k=100 got the average time down to 2s per each f(n).

  By cubic reciprocity, there is an alternative characterization of the desired m = N(z), namely, all m such that the power of p is even for any prime divisor p = 2 (mod 3). But factorization is still far too slow to use this at the scale needed for this problem.

Solvers

• *Dan Dima (28/11/2023 10:07 PM IDT)
• Lazar Ilic (29/11/2023 3:15 AM IDT)
• *Alper Halbutogullari (29/11/2023 4:22 AM IDT)
• *Bert Dobbelaere (29/11/2023 9:12 AM IDT)
• *Franciraldo Cavalcante (29/11/2023 4:01 PM IDT)
• *Stéphane Higueret (29/11/2023 6:19 PM IDT)
• *Yan-Wu He (29/11/2023 8:11 PM IDT)
• *Bertram Felgenhauer (29/11/2023 8:32 PM IDT)
• *Richard Gosiorovsky (29/11/2023 9:19 PM IDT)
• Reda Kebbaj (29/11/2023 10:00 PM IDT)
• Giorgos Kalogeropoulos (30/11/2023 12:28 AM IDT)
• David F.H. Dunkley (30/11/2023 1:39 PM IDT)
• *Martin Thorne (1/12/2023 4:06 AM IDT)
• Victor Chang (1/12/2023 6:50 AM IDT)
• *Sanandan Swaminathan (1/12/2023 7:02 AM IDT)
• Maksym Voznyy (1/12/2023 8:17 AM IDT)
• *Julien Pradier (1/12/2023 8:59 AM IDT)
• *Yi Jiang (1/12/2023 9:07 AM IDT)
• Dieter Beckerle (1/12/2023 11:52 AM IDT)
• *Peter Taylor (1/12/2023 12:39 PM IDT)
• *Arthur Vause (1/12/2023 1:46 PM IDT)
• Guillaume Escamocher (1/12/2023 3:14 PM IDT)
• *Dominik Reichl (1/12/2023 6:25 PM IDT)
• *Jeffrey Harris (1/12/2023 7:03 PM IDT)
• *Vladimir Volevich (2/12/2023 1:46 AM IDT)
• Gary M. Gerken (2/12/2023 3:50 PM IDT)
• Daniel Chong Jyh Tar (2/12/2023 3:53 PM IDT)
• Laurence Warne (2/12/2023 8:06 PM IDT)
• *Ivan Lazaric (2/12/2023 9:45 PM IDT)
• Kurt Foster (3/12/2023 12:31 AM IDT)
• *John Tromp (3/12/2023 1:21 AM IDT)
• Christopher Marks (3/12/2023 6:06 AM IDT)
• *Andrew Gauld (3/12/2023 8:19 AM IDT)
• Kang Jin Cho (3/12/2023 7:50 PM IDT)
• *Vamsi Talupula (3/12/2023 8:28 PM IDT)
• *Karl Mahlburg (3/12/2023 8:30 PM IDT)
• *Amos Guler (3/12/2023 10:15 PM IDT)
• *John Spurgeon (3/12/2023 11:29 PM IDT)
• *Tim Walters (4/12/2023 12:10 AM IDT)
• *Thomas Ilsche (4/12/2023 12:47 AM IDT)
• *Maksym Voznyy (4/12/2023 2:44 AM IDT)
• Lorenzo Gianferrari Pini (4/12/2023 8:27 AM IDT)
• *Christopher Marks (4/12/2023 3:47 PM IDT)
• Adrian Neacsu (5/12/2023 1:31 AM IDT)
• Ashfaque Shaikh (5/12/2023 12:50 PM IDT)
• Karl D’Souza (5/12/2023 3:02 PM IDT)
• Clive Tong (5/12/2023 10:46 PM IDT)
• *Marco Bellocchi (5/12/2023 11:51 PM IDT)
• *Guglielmo Sanchini (6/12/2023 3:50 PM IDT)
• *Daniel Bitin (6/12/2023 4:13 PM IDT)
• *Dieter Beckerle (7/12/2023 12:25 PM IDT)
• *Mark Beyleveld (7/12/2023 9:54 PM IDT)
• *Lorenz Reichel (8/12/2023 10:37 AM IDT)
• *Phil Proudman (9/12/2023 3:45 PM IDT)
• Paul "Lorxus" Rapoport (10/12/2023 1:29 AM IDT)
• Evan Semet (10/12/2023 7:52 AM IDT)
• Blaine Hill (10/12/2023 7:55 AM IDT)
• *David Greer (11/12/2023 1:03 PM IDT)
• *Latchezar Christov (11/12/2023 4:21 PM IDT)
• Paul Revenant (11/12/2023 5:42 PM IDT)
• Fabio Michele Negroni (11/12/2023 8:38 PM IDT)
• Pieter Meijer (11/12/2023 10:23 PM IDT)
• Fakih Karademir (12/12/2023 5:26 AM IDT)
• *Andreas Knüpfer (12/12/2023 9:32 PM IDT)
• *John Mandalas & David Yang (12/12/2023 10:30 PM IDT)
• *Nyles Heise (13/12/2023 6:27 AM IDT)
• Prashant Wankhede (13/12/2023 7:27 AM IDT)
• *Fabio Michele Negroni (13/12/2023 7:40 PM IDT)
• *David Dunkley (14/12/2023 11:52 PM IDT)
• *Noam Zaks (15/12/2023 12:59 AM IDT)
• *Paul Revenant (15/12/2023 3:22 PM IDT)
• *Alexander Daryin (15/12/2023 3:29 PM IDT)
• *Harald Bögeholz (15/12/2023 5:24 PM IDT)
• *Ashfaque Shaikh (16/12/2023 7:10 PM IDT)
• Shouky Dan & Tamir Ganor (17/12/2023 1:20 PM IDT)
• *Matt Cristina (19/12/2023 11:55 PM IDT)
• Cameron Ritson (20/12/2023 4:09 AM IDT)
• *Lyes Belhoul (20/12/2023 4:05 PM IDT)
• Arvind Venkatesan (20/12/2023 10:45 PM IDT)
• Michael Liepelt (21/12/2023 12:19 AM IDT)
• Shirish Chinchalkar (22/12/2023 4:11 AM IDT)
• *Wenjie Yang (23/12/2023 12:34 PM IDT)
• *Sergey Koposov (23/12/2023 5:12 PM IDT)
• *Hakan Summakoğlu (25/12/2023 9:31 PM IDT)
• Reiner Martin (27/12/2023 2:37 AM IDT)
• Andrew Scherbakov (27/12/2023 4:35 AM IDT)
• *Daniel Stadtmauer (27/12/2023 8:36 AM IDT)
• Christoph Baumgarten (27/12/2023 12:16 PM IDT)
• *Motty Porat (28/12/2023 2:41 AM IDT)
• Andi Guo & Benjamin Wang & Henry Xian & Isaac Luo (28/12/2023 9:01 PM IDT)
• Hamidreza Bidar (29/12/2023 6:12 PM IDT)
• Jens Leskinen (30/12/2023 3:06 PM IDT)
• *Alex Izvalov (30/12/2023 8:39 PM IDT)
• *Armin Krauss (31/12/2023 1:11 AM IDT)
• *Zoltan Haindrich (31/12/2023 4:15 PM IDT)
• *Oscar Volpatti (31/12/2023 9:30 PM IDT)
• Vaskor Basak (31/12/2023 11:06 PM IDT)
• Radu-Alexandru Todor (1/1/2024 10:40 PM IDT)
• *Daniel Lincke (2/1/2024 1:31 PM IDT)
• Maayan Ehrenberg & Ohad Einav & Nir Rosenfeld & Nadav Rubinstein & Eden Saig & Yonatan Sommer (2/1/2024 3:19 PM IDT)
• Alain Michiels (3/1/2024 11:40 PM IDT)
• Todd Will (3/1/2024 11:55 PM IDT)
• *Li Li (6/1/2024 8:16 AM IDT)