Puzzle
11 minute read

Ponder This Challenge - August 2023 - Square-triangular numbers

This puzzle was suggested by Michael Brand - thanks Michael!

A square number is a number of the form n2n^2 for some nn.

A triangular number is a number of the form 1+2+3++m1+2+3+\ldots+m for some m.

The number 1225 is both square and triangular: 1225=352=1+2+3++491225=35^2=1+2+3+\ldots +49. Such a number is called square-triangular.

It is easy to see that there are exactly 7 positive square-triangular numbers below 101010^{10}.

Your goal: Find the number of positive square-triangular numbers below 1010010^{100} (googol).

A bonus "*" will be given for finding the number of positive square-triangular numbers below 101010010^{10^{100}} (googolplex).

A "**" will be given for finding the exact solution to the "*" part; a good approximation (5 significant digits) is enough for a "*"

Solution

  • August 2023 Solution:

    The numerical solutions are 66 for googol and 653124034718489245484923772216924660058607596119243405888292084074025349410485980501955062384795 7752

    for googolplex.
    Since this is a very well-known problem, it can be solved by a quick journey to Wikipedia:

    Of course, it can be argued that part of the fun is finding a formula independently without resorting to known results.

    For googol, a formula is enough; for googolplex some manipluation of the formula is required, which results in a complex floating-point computation. A "*" was given for any good approximation resulting from this computation; a "**" was given to those who obtained an exact solution. The most common way to do this is by using an arbitrary precision floating point library such as mpmath:

    One possible way of solving the problem with general prior knowledge in number theory but not specific for square- triangular numbers is by using the method for solving **Pell's equation** after a suitable reduction of the problem to it (the exact derivation is given in Wikipedia).

    Another simple solution requiring only elementary tools in combinatorics is looking in the first few elements on the sequence:

    1,6,35,204,1189,6930,40391,235416,1, 6, 35, 204, 1189, 6930, 40391, 235416, \dots

    And the first and second difference seqeunces:

    1,5,29,169,985,5741,33461,195025,1, 5, 29, 169, 985, 5741, 33461, 195025,\dots

    4,24,140,816,4756,27720,161564,4, 24, 140, 816, 4756, 27720, 161564, \dots

    It can be seen that the second difference sequence is the original sequence multiplied by 4; with little algebra this gives the recurrence relation

    an=6an1an2a_n = 6a_{n-1} - a_{n-2}

    which can be solved to obtain

    an=αnβn42a_n = \frac{\alpha^n-\beta^n}{4\sqrt{2}}

    α=3+22\alpha = 3+2\sqrt{2}

    β=322\beta = 3-2\sqrt{2}

    For googolplex it gives us

    n=10100+log1042αn = \left\lfloor \frac{10^{100}+\log_{10}{4\sqrt{2}}}{\alpha}\right\rfloor

    We end up with a problem in high-precision floating point arithmetic. A common solution many solvers used was to turn to a suitable library, e.g. Python's mpmath.

Solvers

  • **Lazar Ilic (31/7/2023 2:56 PM IDT)
  • Prashant Wankhede (31/7/2023 5:27 PM IDT)
  • *Serino Dario (31/7/2023 5:49 PM IDT)
  • **Kang Jin Cho (31/7/2023 6:13 PM IDT)
  • *Reiner Martin (31/7/2023 7:11 PM IDT)
  • *Lorenzo Gianferrari Pini (31/7/2023 7:27 PM IDT)
  • Fabio Michele Negroni (31/7/2023 7:49 PM IDT)
  • **Evan Semet (31/7/2023 7:59 PM IDT)
  • **Yan-Wu He (31/7/2023 8:42 PM IDT)
  • *Serino Dario (31/7/2023 8:42 PM IDT)
  • **Bert Dobbelaere (31/7/2023 8:43 PM IDT)
  • **Alper Halbutogullari (31/7/2023 11:20 PM IDT)
  • Richard Gosiorovsky (31/7/2023 11:26 PM IDT)
  • Sanandan Swaminathan (31/7/2023 11:44 PM IDT)
  • **David F.H. Dunkley (1/8/2023 12:08 AM IDT)
  • **Hansraj Nahata (1/8/2023 3:19 AM IDT)
  • **Jeffrey Harris (1/8/2023 3:41 AM IDT)
  • **Karl Mahlburg (1/8/2023 4:53 AM IDT)
  • **Hok Leung Nip (1/8/2023 4:54 AM IDT)
  • *Daniel Chong Jyh Tar (1/8/2023 5:06 AM IDT)
  • Gary M. Gerken (1/8/2023 5:17 AM IDT)
  • **Dan Ismailescu (1/8/2023 6:21 AM IDT)
  • **Blaine Hill (1/8/2023 8:14 AM IDT)
  • Alex Fleischer (1/8/2023 8:57 AM IDT)
  • Kandala Viswakanth (1/8/2023 9:38 AM IDT)
  • Hakan Summakoğlu (1/8/2023 11:22 AM IDT)
  • Giogos Kalogeropoulos (1/8/2023 12:57 PM IDT)
  • **Reda Kebbaj (1/8/2023 2:13 PM IDT)
  • Christian Pfaffenzeller (1/8/2023 3:26 PM IDT)
  • *Cameron and John Ritson (1/8/2023 3:39 PM IDT)
  • Thomas Egense (1/8/2023 4:18 PM IDT)
  • **Vladimir Volevich (1/8/2023 5:17 PM IDT)
  • **Armin Krauß (1/8/2023 6:17 PM IDT)
  • Evert van Dijken (1/8/2023 6:44 PM IDT)
  • **Uoti Urpala (1/8/2023 6:46 PM IDT)
  • **José Eduardo Gaboardi de Carvalho (1/8/2023 6:49 PM
  • IDT)
  • Victor Chang (1/8/2023 7:46 PM IDT)
  • *Kindulov Mikhail (1/8/2023 8:02 PM IDT)
  • **Dominik Reichl (1/8/2023 8:50 PM IDT)
  • **Kipp Johnson (1/8/2023 9:34 PM IDT)
  • Michał Franczak (1/8/2023 10:09 PM IDT)
  • Michael Liepelt (1/8/2023 11:02 PM IDT)
  • Jordan Rinder (2/8/2023 1:29 AM IDT)
  • **Andrew Gauld (2/8/2023 2:15 AM IDT)
  • Matt Cristina (2/8/2023 3:21 AM IDT)
  • **Grant Boudreaux (2/8/2023 4:47 AM IDT)
  • Rashid Naim (2/8/2023 5:13 AM IDT)
  • **Xiao Liu (2/8/2023 6:38 AM IDT)
  • Kavi Raj (2/8/2023 7:59 AM IDT)
  • **Marco Bellocchi (2/8/2023 11:29 AM IDT)
  • **Bertram Felgenhauer (2/8/2023 11:31 AM IDT)
  • **Arthur Vause (2/8/2023 1:52 PM IDT)
  • **Luka Mushkudiani (2/8/2023 4:31 PM IDT)
  • Sri Mallikarjun J (2/8/2023 7:50 PM IDT)
  • **Martin Thorne (2/8/2023 7:51 PM IDT)
  • **Latchezar Christov (2/8/2023 10:22 PM IDT)
  • **K S (3/8/2023 12:14 AM IDT)
  • William Cho (3/8/2023 2:20 AM IDT)
  • *Alexander Daryin (3/8/2023 3:30 AM IDT)
  • *Daniel Bitin (3/8/2023 1:31 PM IDT)
  • *Amos Guler (3/8/2023 5:32 PM IDT)
  • Yannick Müller (3/8/2023 6:16 PM IDT)
  • **Guy Daniel Hadas (3/8/2023 7:27 PM IDT)
  • **Diane Pham (3/8/2023 8:18 PM IDT)
  • *Andras Varga (3/8/2023 10:20 PM IDT)
  • **Štěpán Šmíd (4/8/2023 12:17 AM IDT)
  • Abhinav Bana (4/8/2023 4:43 AM IDT)
  • **Dieter Beckerle (4/8/2023 7:55 AM IDT)
  • Daniel Lincke (4/8/2023 10:41 AM IDT)
  • **Asaf Zimmerman (4/8/2023 11:29 AM IDT)
  • **Abdellah Lamkaddem (4/8/2023 1:06 PM IDT)
  • **Franciraldo Cavalcante (4/8/2023 2:01 PM IDT)
  • *Christoph Schmidt (4/8/2023 2:08 PM IDT)
  • Michael Branicky (4/8/2023 8:32 PM IDT)
  • **Erik Hostens (4/8/2023 9:11 PM IDT)
  • Anders Bisbjerg Madsen (4/8/2023 9:27 PM IDT)
  • **Wolfgang Kais (5/8/2023 4:15 AM IDT)
  • **Sanandan Swaminathan (5/8/2023 7:02 AM IDT)
  • *Andreas Knüpfer (5/8/2023 11:34 AM IDT)
  • David Greer (5/8/2023 3:13 PM IDT)
  • *Evert van Dijken (5/8/2023 3:36 PM IDT)
  • **Harald Bögeholz (5/8/2023 8:07 PM IDT)
  • Joaquim Carrapa (5/8/2023 10:20 PM IDT)
  • *Cliff Amundsen (5/8/2023 11:14 PM IDT)
  • **Tim Walters (6/8/2023 12:57 AM IDT)
  • *Sachal Mahajan (6/8/2023 4:17 AM IDT)
  • *Tamir Ganor & Shouky Dan (6/8/2023 11:02 AM IDT)
  • JJ Rabeyrin (6/8/2023 1:45 PM IDT)
  • **Todd Will (6/8/2023 5:58 PM IDT)
  • Rashid Zia (6/8/2023 6:35 PM IDT)
  • **Petro Mudrievskyj (6/8/2023 7:58 PM IDT)
  • **Mark Beyleveld (7/8/2023 5:21 AM IDT)
  • Thomas Egense (7/8/2023 8:40 AM IDT)
  • Ralf Jonas (7/8/2023 3:22 PM IDT)
  • **A. Ramanujan (7/8/2023 5:37 PM IDT)
  • HyeongSik Hwang (7/8/2023 7:13 PM IDT)
  • *Viswanadh Kandala (7/8/2023 8:12 PM IDT)
  • **Nyles Heise (8/8/2023 4:53 AM IDT)
  • Paul Revenant (8/8/2023 7:26 PM IDT)
  • Phil Proudman (9/8/2023 12:54 AM IDT)
  • Stefan Wirth (9/8/2023 1:06 AM IDT)
  • **Maksym Voznyy (9/8/2023 6:14 AM IDT)
  • *Abhinav Bana (9/8/2023 10:37 AM IDT)
  • Dheeraj Reddy (9/8/2023 8:23 PM IDT)
  • **Chris Shannon (10/8/2023 8:40 AM IDT)
  • **Michael Liepelt (10/8/2023 7:50 PM IDT)
  • Roopa Rajaram (11/8/2023 12:59 AM IDT)
  • **Dan Mayer (11/8/2023 2:06 PM IDT)
  • Ismail Farach (11/8/2023 7:03 PM IDT)
  • **Alain Michiels (11/8/2023 7:23 PM IDT)
  • *Omid Gheibi (11/8/2023 9:39 PM IDT)
  • **Lorenz Reichel (11/8/2023 10:24 PM IDT)
  • **Peter Moser (11/8/2023 11:14 PM IDT)
  • Fakih Karademir (12/8/2023 1:29 AM IDT)
  • Jean-Michel Torres (12/8/2023 7:22 PM IDT)
  • Ray Greiss (12/8/2023 9:57 PM IDT)
  • Satya Tamby (13/8/2023 3:13 PM IDT)
  • Laurence Warne (13/8/2023 9:47 PM IDT)
  • **John Tromp (14/8/2023 12:35 AM IDT)
  • Diogo Manuel Cavaco (14/8/2023 11:32 AM IDT)
  • *Shubham Rathi (14/8/2023 11:54 AM IDT)
  • Deep Kankaria (14/8/2023 12:49 PM IDT)
  • **Albert Stadler (14/8/2023 5:43 PM IDT)
  • **Adrian Neacsu (14/8/2023 11:52 PM IDT)
  • Rajesh Sathiyanarayanan (15/8/2023 2:01 PM IDT)
  • **George D. Logan (16/8/2023 4:21 AM IDT)
  • **Katie Liu (16/8/2023 11:04 AM IDT)
  • *Lyes Belhoul (16/8/2023 2:11 PM IDT)
  • **Govind Jujare (16/8/2023 3:55 PM IDT)
  • **Christoph Baumgarten (17/8/2023 11:24 PM IDT)
  • **Lazar Ilic (31/7/2023 2:56 PM IDT)
  • Prashant Wankhede (31/7/2023 5:27 PM IDT)
  • *Serino Dario (31/7/2023 5:49 PM IDT)
  • **Kang Jin Cho (31/7/2023 6:13 PM IDT)
  • *Reiner Martin (31/7/2023 7:11 PM IDT)
  • *Lorenzo Gianferrari Pini (31/7/2023 7:27 PM IDT)
  • Fabio Michele Negroni (31/7/2023 7:49 PM IDT)
  • **Evan Semet (31/7/2023 7:59 PM IDT)
  • **Yan-Wu He (31/7/2023 8:42 PM IDT)
  • *Serino Dario (31/7/2023 8:42 PM IDT)
  • **Bert Dobbelaere (31/7/2023 8:43 PM IDT)
  • **Alper Halbutogullari (31/7/2023 11:20 PM IDT)
  • Richard Gosiorovsky (31/7/2023 11:26 PM IDT)
  • Sanandan Swaminathan (31/7/2023 11:44 PM IDT)
  • **David F.H. Dunkley (1/8/2023 12:08 AM IDT)
  • **Hansraj Nahata (1/8/2023 3:19 AM IDT)
  • **Jeffrey Harris (1/8/2023 3:41 AM IDT)
  • **Karl Mahlburg (1/8/2023 4:53 AM IDT)
  • **Hok Leung Nip (1/8/2023 4:54 AM IDT)
  • *Daniel Chong Jyh Tar (1/8/2023 5:06 AM IDT)
  • Gary M. Gerken (1/8/2023 5:17 AM IDT)
  • **Dan Ismailescu (1/8/2023 6:21 AM IDT)
  • **Blaine Hill (1/8/2023 8:14 AM IDT)
  • Alex Fleischer (1/8/2023 8:57 AM IDT)
  • Kandala Viswakanth (1/8/2023 9:38 AM IDT)
  • Hakan Summakoğlu (1/8/2023 11:22 AM IDT)
  • Giogos Kalogeropoulos (1/8/2023 12:57 PM IDT)
  • **Reda Kebbaj (1/8/2023 2:13 PM IDT)
  • Christian Pfaffenzeller (1/8/2023 3:26 PM IDT)
  • *Cameron and John Ritson (1/8/2023 3:39 PM IDT)
  • Thomas Egense (1/8/2023 4:18 PM IDT)
  • **Vladimir Volevich (1/8/2023 5:17 PM IDT)
  • **Armin Krauß (1/8/2023 6:17 PM IDT)
  • Evert van Dijken (1/8/2023 6:44 PM IDT)
  • **Uoti Urpala (1/8/2023 6:46 PM IDT)
  • **José Eduardo Gaboardi de Carvalho (1/8/2023 6:49 PM
  • IDT)
  • Victor Chang (1/8/2023 7:46 PM IDT)
  • *Kindulov Mikhail (1/8/2023 8:02 PM IDT)
  • **Dominik Reichl (1/8/2023 8:50 PM IDT)
  • **Kipp Johnson (1/8/2023 9:34 PM IDT)
  • Michał Franczak (1/8/2023 10:09 PM IDT)
  • Michael Liepelt (1/8/2023 11:02 PM IDT)
  • Jordan Rinder (2/8/2023 1:29 AM IDT)
  • **Andrew Gauld (2/8/2023 2:15 AM IDT)
  • Matt Cristina (2/8/2023 3:21 AM IDT)
  • **Grant Boudreaux (2/8/2023 4:47 AM IDT)
  • Rashid Naim (2/8/2023 5:13 AM IDT)
  • **Xiao Liu (2/8/2023 6:38 AM IDT)
  • Kavi Raj (2/8/2023 7:59 AM IDT)
  • **Marco Bellocchi (2/8/2023 11:29 AM IDT)
  • **Bertram Felgenhauer (2/8/2023 11:31 AM IDT)
  • **Arthur Vause (2/8/2023 1:52 PM IDT)
  • **Luka Mushkudiani (2/8/2023 4:31 PM IDT)
  • Sri Mallikarjun J (2/8/2023 7:50 PM IDT)
  • **Martin Thorne (2/8/2023 7:51 PM IDT)
  • **Latchezar Christov (2/8/2023 10:22 PM IDT)
  • **K S (3/8/2023 12:14 AM IDT)
  • William Cho (3/8/2023 2:20 AM IDT)
  • *Alexander Daryin (3/8/2023 3:30 AM IDT)
  • *Daniel Bitin (3/8/2023 1:31 PM IDT)
  • *Amos Guler (3/8/2023 5:32 PM IDT)
  • Yannick Müller (3/8/2023 6:16 PM IDT)
  • **Guy Daniel Hadas (3/8/2023 7:27 PM IDT)
  • **Diane Pham (3/8/2023 8:18 PM IDT)
  • *Andras Varga (3/8/2023 10:20 PM IDT)
  • **Štěpán Šmíd (4/8/2023 12:17 AM IDT)
  • Abhinav Bana (4/8/2023 4:43 AM IDT)
  • **Dieter Beckerle (4/8/2023 7:55 AM IDT)
  • Daniel Lincke (4/8/2023 10:41 AM IDT)
  • **Asaf Zimmerman (4/8/2023 11:29 AM IDT)
  • **Abdellah Lamkaddem (4/8/2023 1:06 PM IDT)
  • **Franciraldo Cavalcante (4/8/2023 2:01 PM IDT)
  • *Christoph Schmidt (4/8/2023 2:08 PM IDT)
  • Michael Branicky (4/8/2023 8:32 PM IDT)
  • **Erik Hostens (4/8/2023 9:11 PM IDT)
  • Anders Bisbjerg Madsen (4/8/2023 9:27 PM IDT)
  • **Wolfgang Kais (5/8/2023 4:15 AM IDT)
  • **Sanandan Swaminathan (5/8/2023 7:02 AM IDT)
  • *Andreas Knüpfer (5/8/2023 11:34 AM IDT)
  • David Greer (5/8/2023 3:13 PM IDT)
  • *Evert van Dijken (5/8/2023 3:36 PM IDT)
  • **Harald Bögeholz (5/8/2023 8:07 PM IDT)
  • Joaquim Carrapa (5/8/2023 10:20 PM IDT)
  • *Cliff Amundsen (5/8/2023 11:14 PM IDT)
  • **Tim Walters (6/8/2023 12:57 AM IDT)
  • *Sachal Mahajan (6/8/2023 4:17 AM IDT)
  • *Tamir Ganor & Shouky Dan (6/8/2023 11:02 AM IDT)
  • JJ Rabeyrin (6/8/2023 1:45 PM IDT)
  • **Todd Will (6/8/2023 5:58 PM IDT)
  • Rashid Zia (6/8/2023 6:35 PM IDT)
  • **Petro Mudrievskyj (6/8/2023 7:58 PM IDT)
  • **Mark Beyleveld (7/8/2023 5:21 AM IDT)
  • Thomas Egense (7/8/2023 8:40 AM IDT)
  • Ralf Jonas (7/8/2023 3:22 PM IDT)
  • **A. Ramanujan (7/8/2023 5:37 PM IDT)
  • HyeongSik Hwang (7/8/2023 7:13 PM IDT)
  • *Viswanadh Kandala (7/8/2023 8:12 PM IDT)
  • **Nyles Heise (8/8/2023 4:53 AM IDT)
  • Paul Revenant (8/8/2023 7:26 PM IDT)
  • Phil Proudman (9/8/2023 12:54 AM IDT)
  • Stefan Wirth (9/8/2023 1:06 AM IDT)
  • **Maksym Voznyy (9/8/2023 6:14 AM IDT)
  • *Abhinav Bana (9/8/2023 10:37 AM IDT)
  • Dheeraj Reddy (9/8/2023 8:23 PM IDT)
  • **Chris Shannon (10/8/2023 8:40 AM IDT)
  • **Michael Liepelt (10/8/2023 7:50 PM IDT)
  • Roopa Rajaram (11/8/2023 12:59 AM IDT)
  • **Dan Mayer (11/8/2023 2:06 PM IDT)
  • Ismail Farach (11/8/2023 7:03 PM IDT)
  • **Alain Michiels (11/8/2023 7:23 PM IDT)
  • *Omid Gheibi (11/8/2023 9:39 PM IDT)
  • **Lorenz Reichel (11/8/2023 10:24 PM IDT)
  • **Peter Moser (11/8/2023 11:14 PM IDT)
  • Fakih Karademir (12/8/2023 1:29 AM IDT)
  • Jean-Michel Torres (12/8/2023 7:22 PM IDT)
  • Ray Greiss (12/8/2023 9:57 PM IDT)
  • Satya Tamby (13/8/2023 3:13 PM IDT)
  • Laurence Warne (13/8/2023 9:47 PM IDT)
  • **John Tromp (14/8/2023 12:35 AM IDT)
  • Diogo Manuel Cavaco (14/8/2023 11:32 AM IDT)
  • *Shubham Rathi (14/8/2023 11:54 AM IDT)
  • Deep Kankaria (14/8/2023 12:49 PM IDT)
  • **Albert Stadler (14/8/2023 5:43 PM IDT)
  • **Adrian Neacsu (14/8/2023 11:52 PM IDT)
  • Rajesh Sathiyanarayanan (15/8/2023 2:01 PM IDT)
  • **George D. Logan (16/8/2023 4:21 AM IDT)
  • **Katie Liu (16/8/2023 11:04 AM IDT)
  • *Lyes Belhoul (16/8/2023 2:11 PM IDT)
  • **Govind Jujare (16/8/2023 3:55 PM IDT)
  • **Christoph Baumgarten (17/8/2023 11:24 PM IDT)
  • **Kai Guttmann (18/8/2023 2:22 AM IDT)
  • **Zhang Zhiqiang (18/8/2023 11:24 AM IDT)
  • Chiho Haruta (18/8/2023 11:57 AM IDT)
  • *Stéphane Higueret (19/8/2023 10:49 AM IDT)
  • *Florian Sikora (19/8/2023 1:32 PM IDT)
  • **George D. Logan (19/8/2023 8:02 PM IDT)
  • Anunay Kulshrestha (20/8/2023 4:32 AM IDT)
  • **Max Aehle (20/8/2023 11:49 AM IDT)
  • Kandala Srinivas (20/8/2023 8:24 PM IDT)
  • Soonho You (21/8/2023 5:32 AM IDT)
  • Quentin Higueret (21/8/2023 1:34 PM IDT)
  • Connor McCarthy (21/8/2023 5:17 PM IDT)
  • **Guglielmo Sanchini1 (23/8/2023 6:15 PM IDT)
  • **Govind Jujare (23/8/2023 11:41 PM IDT)
  • **Dan Dima (24/8/2023 11:42 AM IDT)
  • Jose Coelho (24/8/2023 5:11 PM IDT)
  • Michael Tomicich (24/8/2023 8:30 PM IDT)
  • **Erik Wünstel (25/8/2023 12:47 PM IDT)
  • **Simone Foderà (25/8/2023 3:31 PM IDT)
  • **Motty Porat (27/8/2023 12:07 AM IDT)
  • **Carl Löndahl (27/8/2023 12:21 AM IDT)
  • *Julien Vincent Pradier (28/8/2023 8:38 PM IDT)
  • **Teawoo Kim (28/8/2023 10:40 PM IDT)
  • *Dario Filatrella (29/8/2023 7:34 PM IDT)
  • Rayan Swidan (29/8/2023 11:08 PM IDT)
  • Shiva Sud (30/8/2023 12:08 AM IDT)
  • **Daniel Copeland (30/8/2023 7:23 PM IDT)
  • *Matt Crawford (30/8/2023 10:07 PM IDT)
  • **Kay Lee (31/8/2023 5:22 AM IDT)
  • *Hengfeng Tian (31/8/2023 7:44 AM IDT)
  • **Evan Hur (31/8/2023 10:13 PM IDT)
  • **Hugo Pfoertner (31/8/2023 11:13 PM IDT)
  • **Radu-Alexandru Todor (1/9/2023 3:15 AM IDT)
  • Sakai Jun (3/9/2023 2:11 PM IDT)
  • **Muralidhar Seshadri (4/9/2023 9:04 AM IDT)
  • **Fabio Filatrella (4/9/2023 11:43 AM IDT)
  • **Nathan Salo (4/9/2023 11:57 PM IDT)
  • **Li Li (5/9/2023 2:55 AM IDT)
  • **Vaskor Basak and Kermit Rose (5/9/2023 3:35 AM IDT)

Related posts