Curtis Bright's
NSERC Undergraduate Student Research Award
Date: Summer 2007
Summary: I studied the paper On Obláth's Problem by Alexandru Gica and Laurentiu Panaitopol. In this paper they find all perfect squares that are near-repdigits, i.e., when written in decimal every digit except one is the same. The analysis used to solve the more complicated cases was somewhat ad-hoc, so my goal was to write a computer program which could perform the analysis automatically, as well as solve the problem to bases other than 10 and for more general types of numbers.
To this end, I studied how to solve Diophantine equations of the form ax2+c=dbn, a generalization of the Ramanujan-Nagell equation x2+7=2n. In Maple I implemented a congruence-based method that was based on the solving of the generalized Pell equation y2−Dz2=N after making the substitutions y=ax and z=bk (for cases n=2k and n=2k+1). I explain this algorithm and use it to solve the Ramanujan-Nagell equation in my article Solving Ramanujan's Square Equation Computationally.
It turned out that there were extra complexities associated with most other bases. However, the automated program was to find all square repdigits (with proof that no more exist) for bases 2, 4, 6, 10, 12, 28 and 42; as well as all square near-repdigits for bases 2, 4, 6, 10 and 28, and some results on a more general form of near-repdigit (all digits the same except for n consecutive differing digits).
Downloads
Maple Code:
pellsolve - returns the minimal positive solution (
x,
y) to the Pell equation
x2−
Dy2=1 (where
D>0 is not a perfect square) using the PQa algorithm
Maple Code:
genpellsolve - returns a set containing all fundmental solutions (
x,
y) to the generalized Pell equation
x2−
Dy2=
N (where
D>0 is not a perfect square) using brute-force search between bounds on
yMaple Code:
genpellsolvealt - returns a set containing all minimal positive solutions (
x,
y) to the generalized Pell equation
x2−
Dy2=
N (where
D>0 is not a perfect square and 0<
N2<
D) using the PQa algorithm
Maple Code:
calcperiod - returns the period and pre-period of a linear recurrence
Xi =
a1Xi−1+
a2Xi−2+∙∙∙+
akXi−k+
a modulo
m with initial conditions
X0,
X1,...,
Xk−1; it takes input
x as the list
X0,
X1,...,
Xk−1 and
a as the list
a1,
a2,...,
ak,
a (this recurrence is in fact significantly more general than required)
Maple Code:
intersector - returns the residues which occur in the periods of both {
bi mod
m} and {
s⋅
Yi mod
m}, where (
Yi) is the recurrence
Yi=2
px⋅
Yi−1−
Yi−2 with initial conditions
Y0=
fy,
Y1=
fx⋅
py+
fy⋅
px; for example to reproduce the result in my article call intersector(2, 3, 2, 1, 2, 1, 1966336)
References
[1] E. Cohen, On the Ramanujan-Nagell Equation and Its Generalizations, Number Theory: Proceedings of the First Conference of the Canadian Number Theory Association (1990), 81–92.
[2] A. Gica and L. Panaitopol, On Obláth's Problem,
Journal of Integer Sequences 6 (2003),
article 03.3.5.
[3] M. Mignotte, On the Automatic Resolution of Certain Diophantine Equations, EUROSAM 84 Proceedings, Lecture Notes In Computer Science 174 (1984), 378–385.
[4] M. Mignotte, Une nouvelle résolution de l'équation x2+7=2n, Rendiconti del Seminariodella Facoltà di Scienze dell'Università di Cagliari 54 (1984), 41–43.
[5] R. Mollin, Fundamental Number Theory with Applications (1998), 249, 298–301, 338–339.
[6] T. Nagell, Løsning til oppgave nr 2, 1943, s. 29, Norsk Mathematisk Tidsskrift 30 (1948), 62–64.
[7] T. Nagell, The Diophantine Equation x2+7=2n, Arkiv för Matematik 4 (1961), 185–187.
[8] S. Ramanujan, Question 464, Journal of the Indian Mathematical Society 5 (1913), 120.