Curtis Bright's NSERC Undergraduate Student Research Award

Date: Summer 2007

Advisor: K. G. Hare

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 `a``x`^{2}+`c`=`d``b`^{n}, a generalization of the Ramanujan-Nagell equation `x`^{2}+7=2^{n}. In Maple I implemented a congruence-based method that was based on the solving of the generalized Pell equation `y`^{2}−`D``z`^{2}=`N` after making the substitutions `y`=`a``x` and `z`=`b`^{k} (for cases `n`=2`k` and `n`=2`k`+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

My article: Solving Ramanujan's Square Equation Computationally.
Noam Elkies has referenced my solution in a talk:

We state several finiteness theorems, outline some of the connections among them, explain how a finiteness proof can be ineffective, and (time permitting) sketch Nagell's proof and an even more elementary one discovered only 12 years ago by C. Bright.

Maple Code: pellsolve - returns the minimal positive solution (`x`,`y`) to the Pell equation `x`^{2}−`D``y`^{2}=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 `x`^{2}−`D``y`^{2}=`N` (where `D`>0 is not a perfect square) using brute-force search between bounds on `y`

Maple Code: genpellsolvealt - returns a set containing all minimal positive solutions (`x`,`y`) to the generalized Pell equation `x`^{2}−`D``y`^{2}=`N` (where `D`>0 is not a perfect square and 0<`N`^{2}<`D`) using the PQa algorithm

Maple Code: calcperiod - returns the period and pre-period of a linear recurrence `X`_{i} = `a`_{1}`X`_{i−1}+`a`_{2}`X`_{i−2}+∙∙∙+`a`_{k}`X`_{i−k}+`a` modulo `m` with initial conditions `X`_{0},`X`_{1},...,`X`_{k−1}; it takes input **x** as the list `X`_{0},`X`_{1},...,`X`_{k−1} and **a** as the list `a`_{1},`a`_{2},...,`a`_{k},`a` (this recurrence is in fact significantly more general than required)

Maple Code: intersector - returns the residues which occur in the periods of both {`b`^{i} mod `m`} and {`s`⋅`Y`_{i} mod `m`}, where (`Y`_{i}) is the recurrence `Y`_{i}=2`px`⋅`Y`_{i−1}−`Y`_{i−2} with initial conditions `Y`_{0}=`fy`, `Y`_{1}=`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 `x`^{2}+7=2^{n}, *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 `x`^{2}+7=2^{n}, *Arkiv för Matematik* **4** (1961), 185–187.

[8] S. Ramanujan, Question 464, *Journal of the Indian Mathematical Society* **5** (1913), 120.

[9] J. Robertson, Solving the generalized Pell equation `x`^{2}−`D``y`^{2}=`N`, online article (2004), http://hometown.aol.com/jpr2718/pell.pdf.

[10] E. Weisstein, Ramanujan's Square Equation, from *MathWorld*--A Wolfram Web Resource, http://mathworld.wolfram.com/RamanujansSquareEquation.html.