

A066730


Numbers with everincreasing minimalsquaredeniers.


1



2, 3, 12, 21, 60, 184, 280, 364, 1456, 3124, 5236, 17185, 25249, 49504, 233776, 364144, 775369, 3864169, 8794864
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

The Jacobi of modular reductions of a number is often used by a bignum library to give a quick (negative) answer to the question of whether an integer is an exact square. This sequence gives the cutoffs for everincreasing numbers of required modular tests, on the assumption that one is avoiding a brute force squareroot/square/compare. All terms to 8794864 found by Jack Brennen.


LINKS

Table of n, a(n) for n=0..18.
J. Brennen, discussion about issquare() tests without use of sqrt() on Caldwell's 'primenumbers' list


EXAMPLE

2 is 'squaredenied' by 3, as 2 is not a quadratic residue mod 3 3 is squaredenied by 2^2=4, but not by any lower prime power (2 or 3) 12 has 5 as its minimal squaredenier (0 mod 2, 0 mod 3, 0 mod 4 all QRs) 21 has 2^3=8 as its minimal squaredenier. (note that 24 has 7 as its minimal squaredenier, the first number with that property, but it is larger than 21)


CROSSREFS

Sequence in context: A096632 A124261 A018883 * A077755 A061268 A122604
Adjacent sequences: A066727 A066728 A066729 * A066731 A066732 A066733


KEYWORD

more,nonn


AUTHOR

Phil Carmody, Jan 15 2002


STATUS

approved



