This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A066730 Numbers with ever-increasing minimal-square-deniers. 1


%S 2,3,12,21,60,184,280,364,1456,3124,5236,17185,25249,49504,233776,

%T 364144,775369,3864169,8794864

%N Numbers with ever-increasing minimal-square-deniers.

%C 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 ever-increasing numbers of required modular tests, on the assumption that one is avoiding a brute force square-root/square/compare. All terms to 8794864 found by Jack Brennen.

%H J. Brennen, discussion about <a href="http://groups.yahoo.com/group/primenumbers/message/4801">issquare() tests without use of sqrt()</a> on Caldwell's 'primenumbers' list

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

%K more,nonn

%O 0,1

%A _Phil Carmody_, Jan 15 2002

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 20:42 EDT 2019. Contains 328197 sequences. (Running on oeis4.)