A Fast Algorithm for Determining the Existence and Value of Integer Roots of N

Details A Fast Algorithm for Determining the Existence and Value of Integer Roots of N A Fast Algorithm for Determining the Existence and Value of Integer Roots of N

2010-03-28

arxiv.org/abs/1003.5390v1

Mathematics

Number Theory

12 pages, 8 figures

Scientific paper

We show that all perfect odd integer squares not divisible by 3, can be usefully written as sqrt(N) = a + 18p, where the constant a is determined by the basic properties of N. The equation can be solved deterministically by an efficient four step algorithm that is solely based on integer arithmetic. There is no required multiplication or division by multiple digit integers, nor does the algorithm need a seed value. It finds the integer p when N is a perfect square, and certifies N as a non-square when the algorithm terminates without a solution. The number of iterations scales approximately as log(sqrt(N)/2) for square roots. The paper also outlines how one of the methods discussed for squares can be extended to finding an arbitrary root of N. Finally, we present a rule that distinguishes products of twin primes from squares.

Affiliated with

Also associated with

No associations

Rating

A Fast Algorithm for Determining the Existence and Value of Integer Roots of N does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Fast Algorithm for Determining the Existence and Value of Integer Roots of N, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Fast Algorithm for Determining the Existence and Value of Integer Roots of N will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-127840