Ponder This Challenge - September 2026 - Loeschian Arithmetic Progressions

This puzzle was suggested by Hugo Pfoertner - thanks Hugo!

In a now-famous 2004 article, Ben Green and Terence Tao proved that arbitrarily long arithmetic progressions exist in the primes. This holds true analogously for other sets of numbers if their density is sufficiently high, for example, numbers that are the sum of two squares. There are also enough numbers of the form x² + y² + x*y (with x,y being integers), called "Loesch numbers," that arbitrarily long arithmetic progressions can be found among them as well.

Example: The first Loesch numbers are 0, 1, 3, 4, 7, 9, 12, 13, 16, 19, 21, ..., and the numbers 1, 7, 13, 19 form an arithmetic progression with 4 terms and a difference of 6. This progression can be described by its initial value of 1 and the step size of 6.

Your goal: Find an arithmetic progression of 35 terms from the Loesch numbers such that the end of the progression becomes as small as possible, specifying the starting value and the step size.

A bonus "*" will be given for finding a progression with at least 42 terms, again specified by its starting value and step size (the end of the progression needs not be as small as possible).

An extra bonus "**" will be awarded to the participant(s) who find the progression with the most (>42) terms. The allocation of (**) to participants may change during the submission process.

• Click here to view the solution

  Solution

  The numerical solution for the $n=35$ case is

  a = 219830911
  d = 2709630
  

  The best sequence, with $n=58$, found by Hubert Puszklewicz and later independently by Daniel Bitin, is

  a = 1456385415508399
  d = 2639156742851970
  

  A simpler solution achieving $n=42$ (actually, $n=45$) is

  a = 43799686129 
  d = 8236888110
  

  This is mostly a straight up search problem, relying on clever programming and theoretical tricks to speed up the search (and I do not know the tricks used by the top solvers; my own solution was far worse).

  One example of a theoretical trick is that in our length 35 sequence, $d$ must be divisible by $5610$. Let's see why.

  First of all, a known property of Löschian numbers is that if $p$ is a prime divisor of a Löschian number $n$ such that $p\equiv 2(\text{ mod }3)$, then the power of $p$ in the prime factorization of $n$ must be even, and in particular $p^2 | n$ whenever $p$ is a prime divisor of $n$.

  Now, suppose we have $p\equiv 2(\text{ mod }3)$ such that $p\not{|}d$. Consider the linear modular equation $a+dx\equiv 0(\text{ mod }p)$. Since $p$ and $d$ are relatively prime, this equation has a unique solution, namely $x\equiv-ad^{-1}(\text{ mod }p)$. Hence, looking at the sequence

  $a, a+d, a+2d,\ldots a+id,\ldots$

  We obtain a number divisible by $p$ - and so, by $p^2$ - at least once every $p$ steps. Take the first $2p$ steps, and we obtain $i,j$ such that $a+id\equiv a+jd(\text{ mod }p^2)$, meaning $p^2|(i-j)d$, and since $p\not{|}d$ we have $p^2|i-j$ which is impossible after only the first $2p$ steps. Hence, if we consider a sequence of length 35, and we have $p\equiv 2(\text{ mod }3)$ such that $2p<35$, we must have $p|d$. This criterion holds for $p=2,5,11,17$.

  A simpler argument shows that also $3|d$: Consider $n=x^2+xy+y^2$. By going over all combinations of possible $x,y$ it is clear that $n\equiv 0,1(\text{ mod }3)$, so in a progression of length 3 there are two elements equivalent modulo 3, and the same argument as before shows that $3|d$. Hence $2\cdot 3\cdot 5\cdot 11\cdot 17=5610$ must divide $d$, reducing the search space size.

Solvers

• *Paul Lupascu (1/9/2026 9:45 AM IDT)
• *Alper Halbutogullari (1/9/2026 11:08 AM IDT)
• *Daniel Chong Jyh Tar (1/9/2026 11:30 AM IDT)
• *Lazar Ilic (1/9/2026 1:01 PM IDT)
• *Bertram Felgenhauer (1/9/2026 2:24 PM IDT)
• *George Jiri Spitalsky (1/9/2026 3:40 PM IDT)
• *King Pig (1/9/2026 9:33 PM IDT)
• *Aayaam Panigrahi (1/9/2026 10:11 PM IDT)
• **Daniel Bitin (1/9/2026 11:01 PM IDT)
• *Jean-François Hermant (2/9/2026 12:24 AM IDT)
• Alex Fleischer (2/9/2026 12:57 PM IDT)
• Dan Ismailescu (2/9/2026 2:32 PM IDT)
• *Stéphane Higueret (2/9/2026 8:45 PM IDT)
• *Lawrence Hon (3/9/2026 4:35 AM IDT)
• Hoang Vu (3/9/2026 4:45 AM IDT)
• Rethna Pulikkoonattu (3/9/2026 7:22 AM IDT)
• Guangxi Liu (3/9/2026 9:11 AM IDT)
• Michael Vahle (3/9/2026 2:17 PM IDT)
• *Kang Jin Cho (3/9/2026 4:13 PM IDT)
• *Florian Fischer (4/9/2026 12:35 AM IDT)
• *Nickita Khylkouski (4/9/2026 4:03 AM IDT)
• Franciraldo Cavalcante (4/9/2026 9:26 AM IDT)
• *Henk Waßmann (4/9/2026 11:59 AM IDT)
• *Vladimir Volevich (4/9/2026 2:53 PM IDT)
• *Tamir Ganor & Shouky Dan (4/9/2026 7:18 PM IDT)
• Reda Kebbaj (5/9/2026 2:20 AM IDT)
• Ahmet Yüksel (5/9/2026 12:18 PM IDT)
• *Prashant Wankhede (6/9/2026 5:23 AM IDT)
• *Peyo (6/9/2026 9:14 AM IDT)
• *Nadir S. (7/9/2026 8:35 AM IDT)
• Juergen Koehl (7/9/2026 4:44 PM IDT)
• *Daniel Cahill (7/9/2026 6:26 PM IDT)
• Puvichakravarthy Ramachandran (8/9/2026 5:50 AM IDT)
• Siamak (8/9/2026 3:38 PM IDT)
• Paul Revenant (8/9/2026 5:21 PM IDT)
• Michele Missiroli (8/9/2026 9:38 PM IDT)
• *Rahid Zaman (9/9/2026 2:08 AM IDT)
• Björn Richard Nerbe (9/9/2026 8:21 AM IDT)
• *Liubing Yu (10/9/2026 8:00 PM IDT)
• Ewoud Storm van's Gravesande (10/9/2026 11:15 PM IDT)
• *Emin-Ali CALYAKA (10/9/2026 11:54 PM IDT)
• Dominik Reichl (12/9/2026 5:25 PM IDT)
• *Micah Day-O'Connell (12/9/2026 7:38 PM IDT)
• Naren Swaminathan (12/9/2026 8:17 PM IDT)
• Nicolas Lopez (12/9/2026 9:52 PM IDT)
• Peter Ji (13/9/2026 9:14 PM IDT)
• Karl D’Souza (13/9/2026 11:06 PM IDT)
• Resnina Tathyana (14/9/2026 2:28 AM IDT)
• John Tromp (14/9/2026 9:44 PM IDT)
• Devom Brahmbhatt (15/9/2026 5:37 AM IDT)
• Sanandan Swaminathan (15/9/2026 9:18 AM IDT)
• Joaquim Carrapa (15/9/2026 4:38 PM IDT)
• Ethan Fang (15/9/2026 5:54 PM IDT)
• Amos Guler (16/9/2026 7:22 PM IDT)
• Kevin Schoen (17/9/2026 1:21 AM IDT)
• Abhishek Sekar (17/9/2026 6:03 PM IDT)
• Lei Zhang (18/9/2026 8:48 AM IDT)
• Dan Dima (18/9/2026 3:52 PM IDT)
• *Hubert Puszklewicz (18/9/2026 5:58 PM IDT)
• Karl-Heinz Hofmann (20/9/2026 11:43 AM IDT)
• Gary M. Gerken (20/9/2026 4:51 PM IDT)
• Zach Liu (20/9/2026 9:25 PM IDT)
• Evan Semet (20/9/2026 10:42 PM IDT)
• Dieter Beckerle (21/9/2026 8:01 AM IDT)
• *Achyuth Jayadevan (21/9/2026 10:21 AM IDT)
• Fakih Karademir (21/9/2026 12:41 PM IDT)
• Latchezar Christov (21/9/2026 5:51 PM IDT)
• Shirish Chinchalkar (23/9/2026 2:53 AM IDT)
• Haoyi Zhang (23/9/2026 10:42 AM IDT)
• *Jackson La Vallee (23/9/2026 5:12 PM IDT)
• *Paul Lupascu (1/9/2026 9:45 AM IDT)
• *Alper Halbutogullari (1/9/2026 11:08 AM IDT)
• *Daniel Chong Jyh Tar (1/9/2026 11:30 AM IDT)
• *Lazar Ilic (1/9/2026 1:01 PM IDT)
• *Bertram Felgenhauer (1/9/2026 2:24 PM IDT)
• *George Jiri Spitalsky (1/9/2026 3:40 PM IDT)
• *King Pig (1/9/2026 9:33 PM IDT)
• *Aayaam Panigrahi (1/9/2026 10:11 PM IDT)
• *Daniel Bitin (1/9/2026 11:01 PM IDT)
• *Jean-François Hermant (2/9/2026 12:24 AM IDT)
• Alex Fleischer (2/9/2026 12:57 PM IDT)
• Dan Ismailescu (2/9/2026 2:32 PM IDT)
• *Stéphane Higueret (2/9/2026 8:45 PM IDT)
• *Lawrence Hon (3/9/2026 4:35 AM IDT)
• Hoang Vu (3/9/2026 4:45 AM IDT)
• Rethna Pulikkoonattu (3/9/2026 7:22 AM IDT)
• Guangxi Liu (3/9/2026 9:11 AM IDT)
• Michael Vahle (3/9/2026 2:17 PM IDT)
• *Kang Jin Cho (3/9/2026 4:13 PM IDT)
• *Florian Fischer (4/9/2026 12:35 AM IDT)
• *Nickita Khylkouski (4/9/2026 4:03 AM IDT)
• Franciraldo Cavalcante (4/9/2026 9:26 AM IDT)
• *Henk Waßmann (4/9/2026 11:59 AM IDT)
• *Vladimir Volevich (4/9/2026 2:53 PM IDT)
• *Tamir Ganor & Shouky Dan (4/9/2026 7:18 PM IDT)
• Reda Kebbaj (5/9/2026 2:20 AM IDT)
• Ahmet Yüksel (5/9/2026 12:18 PM IDT)
• *Prashant Wankhede (6/9/2026 5:23 AM IDT)
• *Peyo (6/9/2026 9:14 AM IDT)
• *Nadir S. (7/9/2026 8:35 AM IDT)
• Juergen Koehl (7/9/2026 4:44 PM IDT)
• *Daniel Cahill (7/9/2026 6:26 PM IDT)
• Puvichakravarthy Ramachandran (8/9/2026 5:50 AM IDT)
• Siamak (8/9/2026 3:38 PM IDT)
• Paul Revenant (8/9/2026 5:21 PM IDT)
• Michele Missiroli (8/9/2026 9:38 PM IDT)
• *Rahid Zaman (9/9/2026 2:08 AM IDT)
• Björn Richard Nerbe (9/9/2026 8:21 AM IDT)
• *Liubing Yu (10/9/2026 8:00 PM IDT)
• Ewoud Storm van's Gravesande (10/9/2026 11:15 PM IDT)
• *Emin-Ali CALYAKA (10/9/2026 11:54 PM IDT)
• Dominik Reichl (12/9/2026 5:25 PM IDT)
• *Micah Day-O'Connell (12/9/2026 7:38 PM IDT)
• Naren Swaminathan (12/9/2026 8:17 PM IDT)
• Nicolas Lopez (12/9/2026 9:52 PM IDT)
• Peter Ji (13/9/2026 9:14 PM IDT)
• Karl D’Souza (13/9/2026 11:06 PM IDT)
• Resnina Tathyana (14/9/2026 2:28 AM IDT)
• John Tromp (14/9/2026 9:44 PM IDT)
• Devom Brahmbhatt (15/9/2026 5:37 AM IDT)
• Sanandan Swaminathan (15/9/2026 9:18 AM IDT)
• Joaquim Carrapa (15/9/2026 4:38 PM IDT)
• Ethan Fang (15/9/2026 5:54 PM IDT)
• Amos Guler (16/9/2026 7:22 PM IDT)
• Kevin Schoen (17/9/2026 1:21 AM IDT)
• Abhishek Sekar (17/9/2026 6:03 PM IDT)
• Lei Zhang (18/9/2026 8:48 AM IDT)
• Dan Dima (18/9/2026 3:52 PM IDT)
• **Hubert Puszklewicz (18/9/2026 5:58 PM IDT)
• Karl-Heinz Hofmann (20/9/2026 11:43 AM IDT)
• Gary M. Gerken (20/9/2026 4:51 PM IDT)
• Zach Liu (20/9/2026 9:25 PM IDT)
• Evan Semet (20/9/2026 10:42 PM IDT)
• Dieter Beckerle (21/9/2026 8:01 AM IDT)
• *Achyuth Jayadevan (21/9/2026 10:21 AM IDT)
• Fakih Karademir (21/9/2026 12:41 PM IDT)
• Latchezar Christov (21/9/2026 5:51 PM IDT)
• Shirish Chinchalkar (23/9/2026 2:53 AM IDT)
• Haoyi Zhang (23/9/2026 10:42 AM IDT)
• **Jackson La Vallee (23/9/2026 5:12 PM IDT)
• *Steffen Wolf (23/9/2026 7:18 PM IDT)
• *Jean-René Denoual (24/9/2026 10:57 PM IDT)
• *Aditya Bhoj (25/9/2026 9:27 AM IDT)
• Hakan Summakoğlu (26/9/2026 1:24 AM IDT)
• Klaus Nagel (26/9/2026 4:36 PM IDT)
• Sathi Gnaneswara Reddy (26/9/2026 6:42 PM IDT)
• Stefan Wirth (27/9/2026 4:00 AM IDT)
• Yannick Müller (28/9/2026 4:07 PM IDT)
• Jakub Łopuszański (29/9/2026 8:54 AM IDT)
• *David F.H. Dunkley (30/9/2026 3:18 AM IDT)
• Ankit Chakraborty (30/9/2026 5:30 AM IDT)
• Florian Sikora (30/9/2026 12:18 PM IDT)
• Ujjawal Raj (30/9/2026 7:38 PM IDT)
• Samuel Lamphier (30/9/2026 7:45 PM IDT)
• Bert Dobbelaere (30/9/2026 9:26 PM IDT)
• *John Hayden (1/10/2026 5:32 AM IDT)
• Motty Porat (1/10/2026 4:26 PM IDT)
• Marco Bellocchi (2/10/2026 12:17 AM IDT)
• Radu-Alexandru Todor (2/10/2026 3:07 AM IDT)
• Lorenz Reichel (2/10/2026 3:59 PM IDT)
• Nyles Heise (3/10/2026 11:56 PM IDT)
• *Bowen Cheng (5/10/2026 4:36 AM IDT)
• Arthur Vause (5/10/2026 11:28 PM IDT)
• *Lucas Reymond (7/10/2026 9:43 AM IDT)
• David Greer (7/10/2026 12:40 PM IDT)
• *Alexander Bielik (10/10/2026 8:31 AM IDT)
• Li Li (12/10/2026 11:41 PM IDT)

The ** holders were, in reverse order of appearance with their original, **-worthy, record:

1. Hubert Puszklewicz (58)
2. Jackson La Vallee (57)
3. Daniel Bitin (55)
4. Henk Waßmann (49)
5. Bertram Felgenhauer (45)
6. Paul Lupascu (44)

• n = 58: Hubert Puszklewicz, Daniel Bitin
• n = 57: Jackson La Vallee, Bowen Cheng
• n = 55: Henk Waßmann, Achyuth Jayadevan, Emin-Ali CALYAKA, Jean-François Hermant, Daniel Chong Jyh Tar, Alper Halbutogullari
• n = 51: Alexander Bielik
• n = 50: Bertram Felgenhauer
• n = 48: Peyo, Paul Lupascu
• n = 47: Lawrence Hon, George Jiri Spitalsky, Prashant Wankhede, Tamir Ganor & Shouky Dan
• n = 46: King Pig, Daniel Cahill, Nadir S.
• n = 45: Kang Jin Cho, Lazar Ilic, Vladimir Volevich, Stéphane Higueret, Jean-René Denoual
• n = 44: Aayaam Panigrahi, Lucas Reymond