samcarter
> This is part of the Summer of Code 2022 series, see https://topanswers.xyz/tex?q=2059 for more information

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:


Triangle 	  	T(n)=n(n+1)/2 	  	1, 3, 6, 10, 15, ...
Pentagonal 	  	P(n)=n(3n−1)/2 	  	1, 5, 12, 22, 35, ...
Hexagonal 	  	H(n)=n(2n−1) 	  	1, 6, 15, 28, 45, ...


It can be verified that T(285) = P(165) = H(143) = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

(this programming puzzle is taken from https://projecteuler.net/problem=45, licensed under CC BY-NC-SA 4.0)

![SoC.png](/image?hash=962b29406727a7f6f5afa3e2e0da910d4b6d2448266a02f2e88708d557487924)
frougon
\* This line is not a spoiler. \*

Here are two ways using xint, which performs computations with arbitrarily long integers (among others!). This is however *much slower* than my [first implementation](https://topanswers.xyz/tex?q=2087#a2334) which uses TeX \count registers via expl3 int variables.

# First way: with xint user variables

This is the slowest way: reaching T(55385) = P(31977) = H(27693) = 1533776805 takes about 79 seconds on my computer. All integers are stored in xint user variables.


\documentclass{article}
\usepackage{xintexpr}

\xintdefiifunc T(n) := n*(n+1)/2;
\xintdefiifunc P(n) := n*(3*n-1)/2;
\xintdefiifunc H(n) := n*(2*n-1);

\ExplSyntaxOn

\bool_new:N \l__socix_stop_flag_bool

\cs_new_protected:Npn \socix_find_coincidences:
{
\bool_set_false:N \l__socix_stop_flag_bool
\xintdefiivar n, i, j := 0, 0, 0;

\bool_do_until:Nn \l__socix_stop_flag_bool
{
% \iow_term:x { n~ =~ \xintiieval{n} }
\xintdefiivar nb_matches := 0;
\xintdefiivar valT := T(n);

% Advance i to the smallest value ≥ its current value such that
% P(i) >= T(n).
\bool_do_while:Nn \c_true_bool
{
\xintdefiivar valP := P(i);
\xintiiifLt { \xintiieval{valP} } { \xintiieval{valT} }
{ \xintdefiivar i := i + 1; }
{ \prg_break: }
}
\prg_break_point:

% If P(i) = T(n), increase nb_matches
\xintiiifEq { \xintiieval{valP} } { \xintiieval{valT} }
{ \xintdefiivar nb_matches := nb_matches + 1; }
{ }

% Advance j to the smallest value ≥ its current value such that
% H(j) >= T(n).
\bool_do_while:Nn \c_true_bool
{
\xintdefiivar valH := H(j);
\xintiiifLt { \xintiieval{valH} } { \xintiieval{valT} }
{ \xintdefiivar j := j + 1; }
{ \prg_break: }
}
\prg_break_point:

% If H(j) = T(n), increase nb_matches
\xintiiifEq { \xintiieval{valH} } { \xintiieval{valT} }
{ \xintdefiivar nb_matches := nb_matches + 1; }
{ }

\xintiiifEq { \xintiieval{nb_matches} } { 2 }
{
\par \noindent
\c_math_toggle_token
T(\xintiieval{n}) = P(\xintiieval{i})
= H(\xintiieval{j}) = \xintiieval{valT}
\c_math_toggle_token

% We need to stop somewhere. :-P
\xintiiifLt { \xintiieval{valT} } { 1533776805 }% 57722156241751
{ }
{ \bool_set_true:N \l__socix_stop_flag_bool }
}
{ }

\xintdefiivar n := n + 1;
}
}

\cs_new_eq:NN \socIXFindCoincidences \socix_find_coincidences:

\ExplSyntaxOff

\begin{document}

\socIXFindCoincidences

\end{document}


# Second way: integers stored in expl3 tl vars

This is a bit faster: reaching T(55385) = P(31977) = H(27693) = 1533776805 takes about 50 seconds on my computer. All integers are stored in expl3 tl vars, i.e. parameterless macros.


\documentclass{article}
\usepackage{xintexpr}

\xintdefiifunc T(n) := n*(n+1)/2;
\xintdefiifunc P(n) := n*(3*n-1)/2;
\xintdefiifunc H(n) := n*(2*n-1);

\ExplSyntaxOn

\tl_new:N \l__socix_nb_matches_tl
\tl_new:N \l__socix_n_tl
\tl_new:N \l__socix_i_tl
\tl_new:N \l__socix_j_tl
\tl_new:N \l__socix_valT_tl
\tl_new:N \l__socix_valP_tl
\tl_new:N \l__socix_valH_tl
\bool_new:N \l__socix_stop_flag_bool

\cs_new_protected:Npn \__socix_int_incr:N #1
{
\tl_set:Nx #1 { \xintiieval { #1 + 1 } }
}

\cs_new_protected:Npn \socix_find_coincidences:
{
\bool_set_false:N \l__socix_stop_flag_bool
\clist_map_inline:nn { \l__socix_n_tl, \l__socix_i_tl, \l__socix_j_tl }
{ \tl_set:Nn ##1 { 0 } }

\bool_do_until:Nn \l__socix_stop_flag_bool
{
% \iow_term:x { n~ =~ \l__socix_n_tl }
\tl_set:Nn \l__socix_nb_matches_tl { 0 }
\tl_set:Nx \l__socix_valT_tl { \xintiieval { T(\l__socix_n_tl) } }

% Advance i to the smallest value ≥ its current value such that
% P(i) >= T(n).
\bool_do_while:Nn \c_true_bool
{
\tl_set:Nx \l__socix_valP_tl { \xintiieval { P(\l__socix_i_tl) } }
\xintiiifLt { \l__socix_valP_tl } { \l__socix_valT_tl }
{ \__socix_int_incr:N \l__socix_i_tl }
{ \prg_break: }
}
\prg_break_point:

% If P(i) = T(n), increase nb_matches
\xintiiifEq { \l__socix_valP_tl } { \l__socix_valT_tl }
{ \__socix_int_incr:N \l__socix_nb_matches_tl }
{ }

% Advance j to the smallest value ≥ its current value such that
% H(j) >= T(n).
\bool_do_while:Nn \c_true_bool
{
\tl_set:Nx \l__socix_valH_tl { \xintiieval { H(\l__socix_j_tl) } }
\xintiiifLt { \l__socix_valH_tl } { \l__socix_valT_tl }
{ \__socix_int_incr:N \l__socix_j_tl }
{ \prg_break: }
}
\prg_break_point:

% If H(j) = T(n), increase \l__socix_nb_matches_int
\xintiiifEq { \l__socix_valH_tl } { \l__socix_valT_tl }
{ \__socix_int_incr:N \l__socix_nb_matches_tl }
{ }

\xintiiifEq { \l__socix_nb_matches_tl } { 2 }
{
\par \noindent
\c_math_toggle_token
T(\l__socix_n_tl) = P(\l__socix_i_tl)
= H(\l__socix_j_tl) = \l__socix_valT_tl
\c_math_toggle_token

% We need to stop somewhere. :-P
\xintiiifLt { \l__socix_valT_tl } { 1533776805 }% 57722156241751
{ }
{ \bool_set_true:N \l__socix_stop_flag_bool }
}
{ }

\__socix_int_incr:N \l__socix_n_tl
}
}

\cs_new_eq:NN \socIXFindCoincidences \socix_find_coincidences:

\ExplSyntaxOff

\begin{document}

\socIXFindCoincidences

\end{document}


# Output

Both examples produce the following output:

![image.png](/image?hash=741eb678173709591054cd4d87baa5626b09d48fd0b68c6d9b2de715a3e25151)

# What's next?

As shown by the following Python code, the next line to display is:

T(10744501) = P(6203341) = H(5372251) = 57722156241751


#! /usr/bin/env python3

import sys
from math import sqrt

def T(n):
return int(n*(n+1)/2)

def P(n):
return int(n*(3*n-1)/2)

def H(n):
return int(n*(2*n-1))

def main():
n = i = j = 0

while True:
matches = 0
valT = T(n)

while True:
valP = P(i)
if valP >= valT: break
i += 1

if valP == valT:
matches += 1

while True:
valH = H(j)
if valH >= valT: break
j += 1

if valH == valT:
matches += 1

if matches == 2:
print(f"T({n}) = P({i}) = H({j}) = {valT}")

n += 1

sys.exit(0)

if __name__ == "__main__": main()


The result T(10744501) = P(6203341) = H(5372251) = 57722156241751 is clearly out of reach for standard arithmetic using TeX \count registers, however the xint-based codes posted here should be able to get there given enough time—I expect something on the order of two or three hours with the second code of this answer.
frougon
\* This line is not a spoiler. \*

The following code uses TeX integer arithmetic; it is fast (1.4 second on my computer), but the arithmetic overflow is quite close. It would probably be wise to use another language for this... or, if one *really* wants to do this with TeX, use some package like [xint](https://ctan.org/pkg/xint) that can compute with arbitrarily large integers (see my [other answer](https://topanswers.xyz/tex?q=2087#a2335)).

The algorithm used here exploits the fact that the three sequences are strictly increasing (my other answer has the algorithm implemented in Python, probably easier to read this way—before starting to work with \count registers, I wanted to be sure that the goal was reachable without triggering the dreaded arithmetic overflow! :)).


\documentclass{article}

\ExplSyntaxOn

\int_new:N \l__socix_nb_matches_int
\int_new:N \l__socix_n_int
\int_new:N \l__socix_i_int
\int_new:N \l__socix_j_int
\int_new:N \l__socix_valT_int
\int_new:N \l__socix_valP_int
\int_new:N \l__socix_valH_int
\bool_new:N \l__socix_stop_flag_bool

\cs_new_protected:Npn \socix_find_coincidences:
{
\int_zero:N \l__socix_n_int
\int_zero:N \l__socix_i_int
\int_zero:N \l__socix_j_int
\bool_set_false:N \l__socix_stop_flag_bool

\bool_do_until:Nn \l__socix_stop_flag_bool
{
\int_zero:N \l__socix_nb_matches_int
\int_set:Nn \l__socix_valT_int
{ \l__socix_n_int*(\l__socix_n_int + 1)/2 }

% Advance i to the smallest value ≥ its current value such that
% P(i) >= T(n).
\bool_do_while:Nn \c_true_bool
{
\int_set:Nn \l__socix_valP_int
{ \l__socix_i_int*(3*\l__socix_i_int - 1)/2 }
\int_compare:nNnF { \l__socix_valP_int } < { \l__socix_valT_int }
{ \prg_break: }
\int_incr:N \l__socix_i_int
}
\prg_break_point:

% If P(i) = T(n), increase \l__socix_nb_matches_int
\int_compare:nNnT { \l__socix_valP_int } = { \l__socix_valT_int }
{
\int_incr:N \l__socix_nb_matches_int
}

% Advance j to the smallest value ≥ its current value such that
% H(j) >= T(n).
\bool_do_while:Nn \c_true_bool
{
\int_set:Nn \l__socix_valH_int
{ \l__socix_j_int*(2*\l__socix_j_int - 1) }
\int_compare:nNnF { \l__socix_valH_int } < { \l__socix_valT_int }
{ \prg_break: }
\int_incr:N \l__socix_j_int
}
\prg_break_point:

% If H(j) = T(n), increase \l__socix_nb_matches_int
\int_compare:nNnT { \l__socix_valH_int } = { \l__socix_valT_int }
{
\int_incr:N \l__socix_nb_matches_int
}

\int_compare:nNnT { \l__socix_nb_matches_int } = { 2 }
{
\par \noindent
\c_math_toggle_token
T(\int_use:N \l__socix_n_int) = P(\int_use:N \l__socix_i_int)
= H(\int_use:N \l__socix_j_int) = \int_use:N \l__socix_valT_int
\c_math_toggle_token

% We need to stop somewhere... and preferably before an arithmetic
% overflow. :-P
\int_compare:nNnT { \l__socix_valT_int } > { 1500000000 }
{ \bool_set_true:N \l__socix_stop_flag_bool }
}
\int_incr:N \l__socix_n_int
}
}

\cs_new_eq:NN \socIXFindCoincidences \socix_find_coincidences:

\ExplSyntaxOff

\begin{document}

\socIXFindCoincidences

\end{document}


![image.png](/image?hash=c115eb909b7e5ef5e4de2c3b41ee670fd8aebe0718b9720f657b5581a28d6ad6)