Back to search

South Dakota State University

Solving the Inherited Perfect Square Problem

Abstract

dc:description.abstract

For a long time, people have been baffled by trying to solve the “Perfect Square Problem". From it, more problems are inherited. The inherited perfect square problem in this paper is one example. It is stated as follows: Given any integer N, try to find positive integer A and B, such that both A2 + B2 and A2 + (B - NA) 2 are perfect squares. In this paper, two different approaches for solving the problem are introduced. The first one is the Forward-Algorithm, which takes advantage of logical common thinking and modifes Dahlquist's algorithm to demonstrate A and B. Hence, the Forward-Algorithm is easy to understand. By running its program, all solutions, if one exists, can be obtained, including the smallest one. The second approach is the Backward-Algorithm, which is based on the method of infinite descent and a revision of Dahlquist's algorithm. Hence, there is a great deal of mathematics involved. The Backward-Algorithm will not guarantee that we find the smallest solution or all solutions when a solution does exist. The time complexity of the Forward-Algorithm and the Backward-Algorithm is also discussed. The Backward-Algorithm is strongly preferred from the point of time complexity.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis - University Access Only
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ding, Lijie

Identifiers

dc:identifier.*
Repository record dc:identifier
https://openprairie.sdstate.edu/etd2/296

Chain of custody

source
Harvested from
South Dakota State University
Base URL
openprairie.sdstate.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ding, Lijie. Solving the Inherited Perfect Square Problem. Thesis - University Access Only thesis, https://openprairie.sdstate.edu/etd2/296